List<T>의 Resize 메서드 구현
사실, .NET Framework의 BCL을 만드는 실력이라면... 적어도 C/C++ 정도는 자유롭게 다루지 않을까... 하는 기대를 하는 것이 무리는 아닙니다. 그렇다면 C/C++의 vector<>가 제공하는 resize를 알 법도 하고... 그렇다면 당연히 List<>에 구현했을 법도 한데... 이상하게 이 메서드는 없습니다.
이 메서드가 은근히 필요할 때가 있는데요. 예를 들어, n 개의 요소를 동적으로 확보하고 임의의 위치를 액세스하고 싶은 경우가 있습니다.
List<int> list = new List<int>();
list[39] = 39; // System.ArgumentOutOfRangeException 예외 발생
C/C++의 vector는 이럴 때 resize(n); 메서드를 호출하고 조정된 크기 내의 인덱스(n - 1)를 임의로 접근하는 것이 가능합니다.
검색해 보면, 다음의 글이 나오는데요.
is there in C# a method for List<T> like resize in c++ for vector<T>
; http://stackoverflow.com/questions/12231569/is-there-in-c-sharp-a-method-for-listt-like-resize-in-c-for-vectort
그리고 그 해법으로 Jon Hanna에 의해 다음의 코드가 답변으로 제시됩니다.
public static class ListExtras
{
public static void Resize<T>(this List<T> list, int size, T element = default(T))
{
int count = list.Count;
if (size < count)
{
list.RemoveRange(size, count - size);
}
else if (size > count)
{
if (size > list.Capacity) // Optimization
list.Capacity = size;
list.AddRange(Enumerable.Repeat(element, size - count));
}
}
}
근데... 이 코드가 참... 애매합니다. 더 할당해야 하는 경우 AddRange를 하고 있는데, 이것은 내부적으로 MoveNext와 List<>.Insert 메서드를 반복하는 동작으로 바뀝니다. 즉, 성능이 걱정된다는 것인데, 여기서 재미있는 점은, AddRange 메서드가 첫 번째 인자를 IEnumerable<T> 타입을 받긴 하지만, 내부적으로 ICollection<T>로 변환 여부를 체크하고 가능한 경우 Array.Copy(To) 메서드를 사용하는 배려가 되어 있다는 점입니다.
public void AddRange(IEnumerable<T> collection)
{
this.InsertRange(this._size, collection);
}
public void InsertRange(int index, IEnumerable<T> collection)
{
// ...[생략]...
ICollection<T> is2 = collection as ICollection<T>;
if (is2 != null)
{ // ICollection<T>로 변환이 가능하면, Array.Copy(To)로 처리
int count = is2.Count;
if (count > 0)
{
this.EnsureCapacity(this._size + count);
// ...[생략]...
T[] array = new T[count];
is2.CopyTo(array, 0);
array.CopyTo(this._items, index);
// ...[생략]...
this._size += count;
}
}
else
{
// ICollection<T>로 변환이 안되면, IEnumerable 고유의 복사 작업 진행
using (IEnumerator<T> enumerator = collection.GetEnumerator())
{
while (enumerator.MoveNext())
{
this.Insert(index++, enumerator.Current);
}
}
}
this._version++;
}
따라서, Resize 메서드를 이런 식으로 구현하는 것도 생각해 볼 수 있습니다.
public static void Resize2<T>(this List<T> list, int size)
{
int count = list.Count;
if (size < count)
{
list.RemoveRange(size, count - size);
}
else if (size > count)
{
if (size > list.Capacity)
{
list.Capacity = size;
}
list.AddRange(new T[size - count]);
}
}
성능 측정을 해보면,
private static void CalcTime1(int count)
{
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < count; i++)
{
List list = new List();
list.Resize(50);
}
sw.Stop();
Console.WriteLine("Enum-Resize: " + sw.ElapsedTicks);
}
private static void CalcTime2(int count)
{
Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = 0; i < count; i++)
{
List list = new List();
list.Resize2(50);
}
sw.Stop();
Console.WriteLine("New-Resize: " + sw.ElapsedTicks);
}
CalcTime1(1);
CalcTime2(1);
CalcTime1(10000);
CalcTime2(10000);
// 출력 결과
Enum-Resize: 8929
New-Resize: 2059
Enum-Resize: 22026
New-Resize: 5902
수치상으로는 4배 정도로 new T[]로 추가한 것이 더 빨랐습니다. 역시 일일이 MoveNext하며 추가하는 것보다 Array.Copy(To)로 메모리 복사를 한 것이 더 빠를 수밖에 없습니다.
단지, ElapsedTicks로 잰 것이고 10,000번이라는 연속 횟수를 감안했을 때 일반적인 거의 모든 프로그램에서는 new T[]로 구현했다고 해서 딱히 성능 향상을 기대하는 것은 무리일 듯 합니다.
어찌 보면 가장 좋은 구현은, 마이크로소프트에서 다음과 같은 resize 메서드를 제공해 주는 것입니다.
public static void Resize3<T>(this List<T> list, int size)
{
int count = list.Count;
if (size < count)
{
list.RemoveRange(size, count - size);
}
else if (size > count)
{
if (size > list.Capacity)
{
list.Capacity = size;
}
list._size = size; // private 필드인 _size의 값을 조정
}
}
물론 위의 구현을 현재에도 .NET Reflection을 이용해 구현할 수는 있습니다.
Type type = typeof(List<int>);
FieldInfo fieldInfo = type.GetField("_size", BindingFlags.NonPublic | BindingFlags.Instance);
public static void Resize3<T>(this List<T> list, FieldInfo fieldInfo, int size)
{
int count = list.Count;
if (size < count)
{
list.RemoveRange(size, count - size);
}
else if (size > count)
{
if (size > list.Capacity)
{
list.Capacity = size;
}
fieldInfo.SetValue(list, size);
}
}
하지만 Reflection이니만큼 성능이 new T[]로 했던 경우에 비해 조금 느립니다. 그 외에도, 위의 방법에는 치명적인 단점이 있습니다. 바로 List 타입이 제네릭이기 때문에 반드시 FieldInfo에 대한 정보를 구할 때 인스턴스 타입이 동일하게 지정된 제네릭 타입을 얻어와야 한다는 점입니다.
Type type = typeof(List<>); // 이렇게 얻으면 안됨!
Type type = typeof(List<int>); // List<int>인 경우에만 해당!
따라서, Resize 3번 유형은 마이크로소프트가 내부적으로 해줬을 때 가장 성능이 빠르고 현실적으로 사용할 수 있으므로 외부 개발자 입장에서는 고려하지 않는 것이 좋습니다.
(
첨부 파일은 위의 테스트 코드를 포함합니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]