성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Java - How to use the Foreign Funct...
[정성태] 제가 큰 실수를 했군요. ^^; Delegate를 통한 Bein...
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
[정성태] "props[i].GetValue(props[i])" 코드에서 ...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <br /> <div style='font-family: 맑은 고딕, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>2진 검색을 이용한 리스트 정렬 삽입</div><br /> <br /> 가끔은, 원본 리스트 자체를 정렬된 상태로 유지하고 싶을 때가 있습니다. 예를 들어, 리스트에 새로운 아이템이 추가되는 순간부터 정렬이 되어 있기를 바라는 것인데요.<br /> <br /> 이런 경우에 사용할 수 있는 BCL 타입이라면 SortedList를 예로 들 수 있습니다. 하지만, 이름에서와는 달리 이 데이터 타입은 List가 아닌 "Dictionary"이기 때문에 Key를 유지해야 하고 또한 Key가 중복되어 삽입되면 오류가 발생합니다. 제가 원하는 것은, 새로운 항목이 들어갈 때부터 자신이 있어야 할 위치를 찾아서 들어가야 하고 키 값은 중복될 수 있다는 정도입니다. <br /> <br /> 처음에는 prototype으로 단순히 List 전체를 열람하면서 처음부터 비교하면서 자신이 위치할 적절한 위치를 찾아서 IList.Insert(int index, T item); 메서드를 호출하도록 했는데, 기왕 할 거 2진 검색으로 위치를 찾아서 넣도록 해보는 것이 좋겠다 싶어서 고치기 시작했습니다. 그러나, ... 세상은 넓기 때문에 "날로 먹을 수" 있지 않을까 싶어서 구글링을 해봤는데,,, 이것 역시 의외로 자료가 없더군요. 2진 "정렬"을 하는 예제는 많지만, 2진 검색을 해서 "위치"를 반환해 주는 예제는 없었습니다.<br /> <br /> 그나마 발견한 것이 아래의 것이었지만,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; width: 800px; background-color: #fbedbb; overflow-x: scroll; font-family: Consolas, Verdana;' > C# Binary Search ; <a target='_tab' href='http://www.ontheblog.net/CMS/Home/tabid/36/EntryID/33/Default.aspx'>http://www.ontheblog.net/CMS/Home/tabid/36/EntryID/33/Default.aspx</a> </pre> <br /> 버그가 좀 있더군요. ^^; 해당 버그를 댓글에서 "Miroslav Spassov"라는 사람이 지적하고 해결책을 내놓았는데... ^^; 그것조차도 버그가 있었습니다. 암튼, 그것을 조금 다듬어서 만들어 봤고 <a target='_tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=441&boardid=331301885'>결과는 첨부된 파일에 예제</a>와 함께 실어 놓았습니다.<br /> <br /> 간단하게, IList의 확장 메서드로 정의했습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; width: 800px; background-color: #fbedbb; overflow-x: scroll; font-family: Consolas, Verdana;' > public static class ListExtension { public static void <b style='color: Blue;'>SortedAdd</b><T>(this IList<T> list, T item) <b style='color: Blue;'>where T : IComparable</b> { ... [중간 생략]... } } </pre> <br /> 따라서, 아래와 같이 기존 IList 타입을 사용하면 됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; width: 800px; background-color: #fbedbb; overflow-x: scroll; font-family: Consolas, Verdana;' > for (i = 0; i < arrayCount; i++) { int number = rand.Next(0, randRange); temp = new <b style='color: Blue;'>MyEntityT</b>(); temp.Name = number + ": Test"; temp.Age = number; list.<b style='color: Blue;'>SortedAdd</b>(temp); } </pre> <br /> 물론, 위에서 사용된 MyEntityT라는 타입은 IComparable 인터페이스를 구현해 두어야 합니다. 그건 그다지 어려운 부분이 아니기 때문에 생략.<br /> <br /> 마지막으로, 빼놓을 수 없는 성능 비교! SortedAdd는 정렬을 하면서 삽입을 하기 때문에, 정렬하지 않고 삽입한 후 한 번에 정렬하는 List.Sort 와 비교를 한 결과는 아래와 같습니다.<br /> <br /> <table border="1" cellPadding="2"> <thead> <th></th> <th>SortedAdd</th> <th>항목을 모두 Add 후, 한번에 Sort</th> </thead> <tbody> <tr> <td>100개</td> <td>0</td> <td>0</td> </tr> <tr> <td>1,000개</td> <td>0</td> <td>0</td> </tr> <tr> <td>10,000개</td> <td>46</td> <td>32</td> </tr> <tr> <td>100,000개</td> <td>4180</td> <td>375</td> </tr> </tbody> </table> <br /> 10,000개 정도까지는 그나마 좀 봐줄 수 있을 것 같습니다. 물론, 이렇게 정렬된 상태에서 항목 하나를 더 추가해 보면 어떨까요? SortedAdd는 0이 나왔지만, 추가 후 정렬하는 방식에서는 218이 나왔습니다. 바로 제가 원하는 결과였습니다. ^^<br /> <br /> <hr style='width: 50%' /><br /> <br /> 참고로, WinForm의 경우에는 아래와 같이 데이터 바인딩 기능과 결합시키는 예도 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; width: 800px; background-color: #fbedbb; overflow-x: scroll; font-family: Consolas, Verdana;' > Implementing a Sortable BindingList Very, Very Quickly ; <a target='_tab' href='http://www.codeproject.com/KB/linq/bindinglist_sortable.aspx'>http://www.codeproject.com/KB/linq/bindinglist_sortable.aspx</a> </pre> <br /> WPF의 경우에는 정렬만 고려되었던 WinForm 데이터 바인딩보다 좀 더 유연하게 filtering, grouping까지 추가한 ICollectionView 인터페이스를 도입하였고. (시간 관계상,,, 오늘은 여기까지만!)<br /> <hr style='width: 50%' /><br /> <br /> [2015-04-16 내용추가]<br /> <img alt='/SysWebRes/bbs/sort_image.gif' src='/SysWebRes/bbs/sort_image.gif' /><br /> <br /><br /><hr /><span style='color: Maroon'>[이 토픽에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
6433
(왼쪽의 숫자를 입력해야 합니다.)