Microsoft MVP성태의 닷넷 이야기
.NET Framework: 118. 2진 검색을 이용한 리스트 정렬 삽입 [링크 복사], [링크+제목 복사],
조회: 16962
글쓴 사람
정성태 (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)
13046정성태5/5/20227168.NET Framework: 2002. C# XingAPI - ACF 파일을 이용한 퀀트 종목 찾기(t1857)
13045정성태5/5/20227166.NET Framework: 2001. C# XingAPI - 주식 종목에 따른 PBR, PER, ROE 구하는 방법(t3341 예제)
13044정성태5/4/20226600오류 유형: 808. error : clang++ exited with code 127
13043정성태5/3/20226273오류 유형: 807. C# - 닷넷 응용 프로그램에서 Informix DB 사용 시 오류 메시지 정리
13042정성태5/3/20226700.NET Framework: 2000. C# - 닷넷 응용 프로그램에서 Informix DB 사용 방법파일 다운로드1
13041정성태4/28/20227009개발 환경 구성: 642. Informix 데이터베이스 docker 환경 구성
13040정성태4/27/20227452VC++: 156. 비주얼 스튜디오 - Linux C/C++ 프로젝트에서 openssl 링크하는 방법
13039정성태4/27/20228298.NET Framework: 1999. C# - Playwright를 이용한 간단한 브라우저 제어 실습
13038정성태4/26/20226050오류 유형: 806. twine 실행 시 ConfigParser.ParsingError: File contains parsing errors: /root/.pypirc
13037정성태4/25/20226475.NET Framework: 1998. Azure Functions를 사용한 간단한 실습
13036정성태4/24/20227308.NET Framework: 1997. C# - nano 시간을 가져오는 방법 [2]
13035정성태4/22/20227865Windows: 204. Windows 10부터 바뀐 QueryPerformanceFrequency, QueryPerformanceCounter
13034정성태4/21/20227170.NET Framework: 1996. C# XingAPI - 주식 종목에 따른 PBR, PER, ROE, ROA 구하는 방법(t3320, t8430 예제)파일 다운로드1
13033정성태4/18/20227736.NET Framework: 1195. C# - Thread.Yield와 Thread.Sleep(0)의 차이점(?)
13032정성태4/17/20227457오류 유형: 805. Github의 50MB 파일 크기 제한 - warning: GH001: Large files detected. You may want to try Git Large File Storage
13031정성태4/15/20227063.NET Framework: 1194. C# - IdealProcessor와 ProcessorAffinity의 차이점
13030정성태4/15/20226694오류 유형: 804. 정규 표현식 오류 - Quantifier {x,y} following nothing.
13029정성태4/14/20227082Windows: 203. iisreset 후에도 이전에 설정한 전역 환경 변수가 w3wp.exe에 적용되는 문제
13028정성태4/13/20227048.NET Framework: 1193. (appsettings.json처럼) web.config의 Debug/Release에 따른 설정 적용
13027정성태4/12/20227284.NET Framework: 1192. C# - 환경 변수의 변화를 알리는 WM_SETTINGCHANGE Win32 메시지 사용법파일 다운로드1
13026정성태4/11/20228837.NET Framework: 1191. C 언어로 작성된 FFmpeg Examples의 C# 포팅 전체 소스 코드 [3]
13025정성태4/11/20228159.NET Framework: 1190. C# - ffmpeg(FFmpeg.AutoGen)를 이용한 vaapi_encode.c, vaapi_transcode.c 예제 포팅
13024정성태4/7/20226631.NET Framework: 1189. C# - 런타임 환경에 따라 달라진 AppDomain.GetCurrentThreadId 메서드
13023정성태4/6/20226957.NET Framework: 1188. C# - ffmpeg(FFmpeg.AutoGen)를 이용한 transcoding.c 예제 포팅 [3]
13022정성태3/31/20226905Windows: 202. 윈도우 11 업그레이드 - "PC Health Check"를 통과했지만 여전히 업그레이드가 안 되는 경우 해결책
13021정성태3/31/20227069Windows: 201. Windows - INF 파일을 이용한 장치 제거 방법
... 16  17  18  19  20  21  22  23  [24]  25  26  27  28  29  30  ...