Microsoft MVP성태의 닷넷 이야기
.NET Framework: 118. 2진 검색을 이용한 리스트 정렬 삽입 [링크 복사], [링크+제목 복사],
조회: 16960
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일


2진 검색을 이용한 리스트 정렬 삽입


가끔은, 원본 리스트 자체를 정렬된 상태로 유지하고 싶을 때가 있습니다. 예를 들어, 리스트에 새로운 아이템이 추가되는 순간부터 정렬이 되어 있기를 바라는 것인데요.

이런 경우에 사용할 수 있는 BCL 타입이라면 SortedList를 예로 들 수 있습니다. 하지만, 이름에서와는 달리 이 데이터 타입은 List가 아닌 "Dictionary"이기 때문에 Key를 유지해야 하고 또한 Key가 중복되어 삽입되면 오류가 발생합니다. 제가 원하는 것은, 새로운 항목이 들어갈 때부터 자신이 있어야 할 위치를 찾아서 들어가야 하고 키 값은 중복될 수 있다는 정도입니다.

처음에는 prototype으로 단순히 List 전체를 열람하면서 처음부터 비교하면서 자신이 위치할 적절한 위치를 찾아서 IList.Insert(int index, T item); 메서드를 호출하도록 했는데, 기왕 할 거 2진 검색으로 위치를 찾아서 넣도록 해보는 것이 좋겠다 싶어서 고치기 시작했습니다. 그러나, ... 세상은 넓기 때문에 "날로 먹을 수" 있지 않을까 싶어서 구글링을 해봤는데,,, 이것 역시 의외로 자료가 없더군요. 2진 "정렬"을 하는 예제는 많지만, 2진 검색을 해서 "위치"를 반환해 주는 예제는 없었습니다.

그나마 발견한 것이 아래의 것이었지만,

C# Binary Search 
; http://www.ontheblog.net/CMS/Home/tabid/36/EntryID/33/Default.aspx

버그가 좀 있더군요. ^^; 해당 버그를 댓글에서 "Miroslav Spassov"라는 사람이 지적하고 해결책을 내놓았는데... ^^; 그것조차도 버그가 있었습니다. 암튼, 그것을 조금 다듬어서 만들어 봤고 결과는 첨부된 파일에 예제와 함께 실어 놓았습니다.

간단하게, IList의 확장 메서드로 정의했습니다.

public static class ListExtension
{
    public static void SortedAdd<T>(this IList<T> list, T item) 
        where T : IComparable
    {
     ... [중간 생략]...
    }
}

따라서, 아래와 같이 기존 IList 타입을 사용하면 됩니다.

for (i = 0; i < arrayCount; i++)
{
    int number = rand.Next(0, randRange);

    temp = new MyEntityT();
    temp.Name = number + ": Test";
    temp.Age = number;

    list.SortedAdd(temp);
}

물론, 위에서 사용된 MyEntityT라는 타입은 IComparable 인터페이스를 구현해 두어야 합니다. 그건 그다지 어려운 부분이 아니기 때문에 생략.

마지막으로, 빼놓을 수 없는 성능 비교! SortedAdd는 정렬을 하면서 삽입을 하기 때문에, 정렬하지 않고 삽입한 후 한 번에 정렬하는 List.Sort 와 비교를 한 결과는 아래와 같습니다.

SortedAdd 항목을 모두 Add 후, 한번에 Sort
100개 0 0
1,000개 0 0
10,000개 46 32
100,000개 4180 375

10,000개 정도까지는 그나마 좀 봐줄 수 있을 것 같습니다. 물론, 이렇게 정렬된 상태에서 항목 하나를 더 추가해 보면 어떨까요? SortedAdd는 0이 나왔지만, 추가 후 정렬하는 방식에서는 218이 나왔습니다. 바로 제가 원하는 결과였습니다. ^^




참고로, WinForm의 경우에는 아래와 같이 데이터 바인딩 기능과 결합시키는 예도 있습니다.

Implementing a Sortable BindingList Very, Very Quickly
; http://www.codeproject.com/KB/linq/bindinglist_sortable.aspx

WPF의 경우에는 정렬만 고려되었던 WinForm 데이터 바인딩보다 좀 더 유연하게 filtering, grouping까지 추가한 ICollectionView 인터페이스를 도입하였고. (시간 관계상,,, 오늘은 여기까지만!)



[2015-04-16 내용추가]
//sysnetblobaccount.blob.core.windows.net/sysnetimages/sort_image.gif



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







[최초 등록일: ]
[최종 수정일: 7/10/2021]

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

비밀번호

댓글 작성자
 




... 16  17  [18]  19  20  21  22  23  24  25  26  27  28  29  30  ...
NoWriterDateCnt.TitleFile(s)
13197정성태12/17/20224574.NET Framework: 2079. .NET Core/5+ 환경에서 XmlSerializer 사용 시 System.IO.FileNotFoundException 예외 발생하는 경우파일 다운로드1
13196정성태12/16/20224789.NET Framework: 2078. .NET Core/5+를 위한 SGen(Microsoft.XmlSerializer.Generator) 사용법
13195정성태12/15/20225255개발 환경 구성: 655. docker - bridge 네트워크 모드에서 컨테이너 간 통신 시 --link 옵션 권장 이유
13194정성태12/14/20225347오류 유형: 833. warning C4747: Calling managed 'DllMain': Managed code may not be run under loader lock파일 다운로드1
13193정성태12/14/20225464오류 유형: 832. error C7681: two-phase name lookup is not supported for C++/CLI or C++/CX; use /Zc:twoPhase-
13192정성태12/13/20225532Linux: 55. 리눅스 - bash shell에서 실수 연산
13191정성태12/11/20226436.NET Framework: 2077. C# - 직접 만들어 보는 SynchronizationContext파일 다운로드1
13190정성태12/9/20226931.NET Framework: 2076. C# - SynchronizationContext 기본 사용법파일 다운로드1
13189정성태12/9/20227784오류 유형: 831. Visual Studio - Windows Forms 디자이너의 도구 상자에 컨트롤이 보이지 않는 문제
13188정성태12/9/20226360.NET Framework: 2075. C# - 직접 만들어 보는 TaskScheduler 실습 (SingleThreadTaskScheduler)파일 다운로드1
13187정성태12/8/20226292개발 환경 구성: 654. openssl - CA로부터 인증받은 새로운 인증서를 생성하는 방법 (2)
13186정성태12/6/20224855오류 유형: 831. The framework 'Microsoft.AspNetCore.App', version '...' was not found.
13185정성태12/6/20225813개발 환경 구성: 653. Windows 환경에서의 Hello World x64 어셈블리 예제 (NASM 버전)
13184정성태12/5/20225008개발 환경 구성: 652. ml64.exe와 link.exe x64 실행 환경 구성
13183정성태12/4/20225006오류 유형: 830. MASM + CRT 함수를 사용하는 경우 발생하는 컴파일 오류 정리
13182정성태12/4/20225755Windows: 217. Windows 환경에서의 Hello World x64 어셈블리 예제 (MASM 버전)
13181정성태12/3/20225133Linux: 54. 리눅스/WSL - hello world 어셈블리 코드 x86/x64 (nasm)
13180정성태12/2/20225209.NET Framework: 2074. C# - 스택 메모리에 대한 여유 공간 확인하는 방법파일 다운로드1
13179정성태12/2/20224537Windows: 216. Windows 11 - 22H2 업데이트 이후 Terminal 대신 cmd 창이 뜨는 경우
13178정성태12/1/20225080Windows: 215. Win32 API 금지된 함수 - IsBadXxxPtr 유의 함수들이 안전하지 않은 이유파일 다운로드1
13177정성태11/30/20225799오류 유형: 829. uwsgi 설치 시 fatal error: Python.h: No such file or directory
13176정성태11/29/20224637오류 유형: 828. gunicorn - ModuleNotFoundError: No module named 'flask'
13175정성태11/29/20226469오류 유형: 827. Python - ImportError: cannot import name 'html5lib' from 'pip._vendor'
13174정성태11/28/20224906.NET Framework: 2073. C# - VMMap처럼 스택 메모리의 reserve/guard/commit 상태 출력파일 다운로드1
13173정성태11/27/20225679.NET Framework: 2072. 닷넷 응용 프로그램의 스레드 스택 크기 변경
13172정성태11/25/20225395.NET Framework: 2071. 닷넷에서 ESP/RSP 레지스터 값을 구하는 방법파일 다운로드1
... 16  17  [18]  19  20  21  22  23  24  25  26  27  28  29  30  ...