Microsoft MVP성태의 닷넷 이야기
.NET Framework: 555. List<T>의 Resize 메서드 구현 [링크 복사], [링크+제목 복사],
조회: 22844
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일

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번 유형은 마이크로소프트가 내부적으로 해줬을 때 가장 성능이 빠르고 현실적으로 사용할 수 있으므로 외부 개발자 입장에서는 고려하지 않는 것이 좋습니다.

(첨부 파일은 위의 테스트 코드를 포함합니다.)




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]







[최초 등록일: ]
[최종 수정일: 6/27/2021]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 



2016-03-09 04시56분
[초록물꼬기] 와우.. T array 는 기본적으로 ICollection<T> 를 구현하는걸 이용하셨네요.

Resize 는 기본 element 를 지정할 수 있는데 Resize2 는 디폴트로만 초기화가 되는 점이 있긴 하지만..
본 목적이 c++ 의 resize 처럼 하는거라면 크게 문제가 되지 않네요.
굳이 초기화를 한다면 함수 안에서

T[] t = new T[count - size]
for(int i=0; i<count - size; i++)
    t[i] = element;

이런걸 해준다 해도 디폴트 초기화때보다 성능 하락은 1.6배정도밖에 안일어나고
여전히 Resize 보다는 3배정도 빠르네요.


마이크로 소프트에서 Resize3 과 같은 메소드를 제공한다면
private 인 _size 만 바꿔준다고 할 경우 처음 언급해주셨던 System.ArgumentOutOfRangeException 이 또 발생하지 않을까요?
_size 를 바꾸고나서 _items 를 처리 해야할 것 같은데..
결국 가장 좋은 구현은 정성태님께서 제시하신대로 ICollection 을 구현하는 최소단위의 자료구조를 만들어서 넣는 방법이 아닐지
조심스레 생각해봅니다..!

밤중에 좋은 지식 잘 얻어갑니다. ^^
[guest]
2016-03-10 12시02분
물론 Resize3의 경우 _size만 변경한다면 System.ArgumentOutOfRangeException 예외가 발생하겠지만, 그 전에 Capacity 속성에 새로운 크기를 넣어 공간 확보를 해두기 때문에 안전하게 구현됩니다.
정성태

... 106  107  108  109  110  111  112  [113]  114  115  116  117  118  119  120  ...
NoWriterDateCnt.TitleFile(s)
11136정성태1/20/201720680오류 유형: 375. Hyper-V 내에 구성한 Active Directory 환경의 시간 구성 방법 - 두 번째 이야기
11135정성태1/20/201721572Windows: 134. Windows Server 2016의 작업 표시줄에 있는 시계가 사라졌다면? [1]
11134정성태1/20/201729274.NET Framework: 636. System.Threading.Timer를 이용해 타이머 작업을 할 때 유의할 점 [5]파일 다운로드1
11133정성태1/20/201725342.NET Framework: 635. C# 개발자를 위한 Win32 DLL export 함수의 호출 규약 (2) - x86 환경의 __fastcall [1]파일 다운로드1
11132정성태1/19/201737079.NET Framework: 634. C# 개발자를 위한 Win32 DLL export 함수의 호출 규약 (1) - x86 환경에서의 __cdecl, __stdcall에 대한 Name mangling [1]파일 다운로드1
11131정성태1/13/201725721.NET Framework: 633. C# - IL 코드 분석을 위한 팁 [2]
11130정성태1/11/201726519.NET Framework: 632. x86 실행 환경에서 SECURITY_ATTRIBUTES 구조체를 CreateEvent에 전달할 때 예외 발생파일 다운로드1
11129정성태1/11/201730535.NET Framework: 631. async/await에 대한 "There Is No Thread" 글의 부가 설명 [9]파일 다운로드1
11128정성태1/9/201724224.NET Framework: 630. C# - Interlocked.CompareExchange 사용 예제 [3]파일 다운로드1
11127정성태1/8/201724906기타: 63. (개발자를 위한) Visual Studio의 "with MSDN" 라이선스 설명
11126정성태1/7/201729586기타: 62. Edge 웹 브라우저의 즐겨찾기(Favorites)를 편집/백업/복원하는 방법 [1]파일 다운로드1
11125정성태1/7/201726348개발 환경 구성: 310. IIS - appcmd.exe를 이용해 특정 페이지에 클라이언트 측 인증서를 제출하도록 설정하는 방법
11124정성태1/4/201729742개발 환경 구성: 309. 3년짜리 유효 기간을 제공하는 StartSSL [2]
11123정성태1/3/201725132.NET Framework: 629. .NET Core의 dotnet.exe CLI 명령어 확장 방법 [1]
11122정성태1/3/201723692.NET Framework: 628. TransactionScope에 사용자 정의 트랜잭션을 참여시키는 방법 [2]파일 다운로드1
11121정성태1/1/201721635개발 환경 구성: 308. "ASP.NET Core Web Application (.NET Core)"와 "ASP.NET Core Web Application (.NET Framework)" 차이점
11120정성태12/25/201629094개발 환경 구성: 307. ASP.NET Core Web Application을 IIS에서 호스팅하는 방법
11119정성태12/23/201650254개발 환경 구성: 306. Visual Studio Code에서 Python 개발 환경 구성 [2]
11118정성태12/22/201638555오류 유형: 374. Python 64비트 설치 시 0x80070659 오류 발생 [3]
11117정성태12/21/201624239웹: 35. nopCommerce 예제 사이트 구성 방법
11116정성태12/21/201626305디버깅 기술: 84. NopCommerce의 Autofac 부하(CPU, Memory) [2]
11115정성태12/21/201629349Windows: 133. 윈도우 서버 2016에서 플래시가 동작하지 않는 경우 [2]
11114정성태12/19/201640834Windows: 132. 역슬래시(backslash) 문자가 왜 통화 표기 문자(한글인 경우 "\")로 보일까요? [2]
11113정성태12/6/201621975오류 유형: 373. ICOMAdminCatalog::GetCollection에서 CO_E_ISOLEVELMISMATCH(0x8004E02F) 오류 발생파일 다운로드1
11112정성태11/23/201627105오류 유형: 372. MySQL 서비스가 올라오지 않는 경우 - Error 1067
11111정성태11/23/201635804.NET Framework: 627. C++로 만든 DLL을 C#에서 사용하기 [2]
... 106  107  108  109  110  111  112  [113]  114  115  116  117  118  119  120  ...