Microsoft MVP성태의 닷넷 이야기
.NET Framework: 118. 2진 검색을 이용한 리스트 정렬 삽입 [링크 복사], [링크+제목 복사],
조회: 21463
글쓴 사람
정성태 (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

비밀번호

댓글 작성자
 




... 31  32  33  34  35  36  37  38  39  40  41  42  43  [44]  45  ...
NoWriterDateCnt.TitleFile(s)
12825정성태9/3/202115239개발 환경 구성: 603. GoLand - WSL 환경과 연동
12824정성태9/2/202124496오류 유형: 760. 파이썬 tensorflow - Dst tensor is not initialized. 오류 메시지
12823정성태9/2/202113383스크립트: 26. 파이썬 - PyCharm을 이용한 fork 디버그 방법
12822정성태9/1/202118523오류 유형: 759. 파이썬 tensorflow - ValueError: Shapes (...) and (...) are incompatible [2]
12821정성태9/1/202114445.NET Framework: 1112. C# - .NET 6부터 공개된 ISpanFormattable 사용법
12820정성태9/1/202114843VC++: 147. Golang - try/catch에 대응하는 panic/recover [1]파일 다운로드1
12819정성태8/31/202115242.NET Framework: 1111. C# - FormattableString 타입
12818정성태8/31/202113675Windows: 198. 윈도우 - 작업 관리자에서 (tensorflow 등으로 인한) GPU 연산 부하 보는 방법
12817정성태8/31/202117386스크립트: 25. 파이썬 - 윈도우 환경에서 directml을 이용한 tensorflow의 AMD GPU 사용 방법
12816정성태8/30/202122709스크립트: 24. 파이썬 - tensorflow 2.6 NVidia GPU 사용 방법 [2]
12815정성태8/30/202115194개발 환경 구성: 602. WSL 2 - docker-desktop-data, docker-desktop (%LOCALAPPDATA%\Docker\wsl\data\ext4.vhdx) 파일을 다른 디렉터리로 옮기는 방법
12814정성태8/30/202119269.NET Framework: 1110. C# 11 - 인터페이스 내에 정적 추상 메서드 정의 가능 (DIM for Static Members) [2]파일 다운로드1
12813정성태8/29/202116468.NET Framework: 1109. C# 10 - (11) Lambda 개선파일 다운로드1
12812정성태8/28/202115873.NET Framework: 1108. C# 10 - (10) 개선된 #line 지시자
12811정성태8/27/202115795Linux: 44. 윈도우 개발자를 위한 리눅스 fork 동작 방식 설명 (파이썬 코드)
12810정성태8/27/202114694.NET Framework: 1107. .NET Core/5+에서 동적 컴파일한 C# 코드를 (Breakpoint도 활용하며) 디버깅하는 방법 - #line 지시자파일 다운로드1
12809정성태8/26/202114999.NET Framework: 1106. .NET Core/5+에서 C# 코드를 동적으로 컴파일/사용하는 방법 [1]파일 다운로드1
12808정성태8/25/202116233오류 유형: 758. go: ...: missing go.sum entry; to add it: go mod download ...
12807정성태8/25/202116938.NET Framework: 1105. C# 10 - (9) 비동기 메서드가 사용할 AsyncMethodBuilder 선택 가능파일 다운로드1
12806정성태8/24/202113605개발 환경 구성: 601. PyCharm - 다중 프로세스 디버깅 방법
12805정성태8/24/202115365.NET Framework: 1104. C# 10 - (8) 분해 구문에서 기존 변수의 재사용 가능파일 다운로드1
12804정성태8/24/202115815.NET Framework: 1103. C# 10 - (7) Source Generator V2 APIs
12803정성태8/23/202116286개발 환경 구성: 600. pip cache 디렉터리 옮기는 방법
12802정성태8/23/202116548.NET Framework: 1102. .NET Conf Mini 21.08 - WinUI 3 따라해 보기 [1]
12801정성태8/23/202116118.NET Framework: 1101. C# 10 - (6) record class 타입의 ToString 메서드를 sealed 처리 허용파일 다운로드1
12800정성태8/22/202116516개발 환경 구성: 599. PyCharm - (반대로) 원격 프로세스가 PyCharm에 디버그 연결하는 방법
... 31  32  33  34  35  36  37  38  39  40  41  42  43  [44]  45  ...