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