성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
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'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>2의 30승 이상의 원소를 갖는 경우 버그가 발생하는 이진 검색(Binary Search) 코드</h1> <p> 요 며칠 전에 재미있는 트윗을 하나 봤습니다. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 세상의 거의 모든 이진 검색, 머지 소트 구현에 버그가 있다고. 수십년 동안 잘 써왔지만, 요즘 들어 원소 개수가 10억개 넘는 경우 등이 생기면서 오동작이 발생한다는 얘기. ; <a target='tab' href='https://twitter.com/roh0sun/status/757199922470858753'>https://twitter.com/roh0sun/status/757199922470858753</a> Nearly All Binary Searches and Mergesorts Are Broken (2006) ; <a target='tab' href='https://twitter.com/roh0sun/status/757199922470858753'>https://twitter.com/roh0sun/status/757199922470858753</a> [Google Research Blog] Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken ; <a target='tab' href='https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html'>https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html</a> </pre> <br /> 2006년도의 글인데, 그러니까 대부분의 이진 검색 코드에서 중간 위치를 결정하는 코드가 다음과 같이 되어 있을 텐데요.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > int mid = (low + high) / 2; </pre> <br /> low, high 변수의 타입이 signed integer이고 각각의 값이 2의 30승을 넘으면 오버플로우가 발생하게 됩니다. 따라서 mid의 값이 정상적인 값을 갖지 못하는 버그입니다. 이런 현상이 발생하는 경우는 (low + high)의 값이 Int32.MaxValue 이상이 되어야 하는데, 원소의 수가 2<sup>30</sup>(1,073,741,823)개만 되어도 그렇게 됩니다. 왜냐하면 이진 검색의 특성상 우측으로 계속 재귀 호출이 되다 보면 low가 high의 값에 접근하기 때문입니다.<br /> <br /> 어쨌든 ^^ 구글다운 글입니다. 10억개의 데이터 정도는 우스울 테니.<br /> <br /> 블로그에서는 이를 완화하기 위해 다음의 코드를 제시합니다. (물론 완화입니다. 구글 정도되면 10억이나 20억이나 큰 차이는 없을 듯!)<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > int mid = low + ((high - low) / 2); (또는) mid = ((unsigned int)low + (unsigned int)high)) >> 1; </pre> <br /> 참고로, C#의 이진 검색 코드인 Array.BinarySearch 메서드를 보면 내부의 중간 위치 구하는 코드가 다음과 같이 되어 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > private static int GetMedian(int low, int hi) { return (low + ((hi - low) >> 1)); } </pre> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
7822
(왼쪽의 숫자를 입력해야 합니다.)