앞서 포스팅 한 "뉴욕의 프로그래머" 라는 책에서 언급하고 있는 이야기 중 하나이다.
원래 이것은 조수아 블로흐( Joshua Bloch ) 라는 유명한 소프트웨어 엔지니어가 구글랩 블로그에 올린 글에서 유래하는 이야기이다. 조수아 블로흐는 자바 플랫폼의 유명한 개발자이자 Effective Java (2001년 Jolt Award 수상작) 의 저자이기도 하다. 현재 구글에서 자바 아키텍트로 근무중.
글의 원문 : Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
저자가 카네기멜론 대학의 박사과정에 입학해서, 알고리즘 수업을 듣던 첫날, 존 벤틀리 교수 (Jon Bentley, Programming Pearl 의 저자, 국내에는 "생각하는 프로그래밍" 이란 책으로 번역. ) 가 학생들에서 이진검색을 구현해 보라고 시킨 후에 그중 몇명을 앞에 나와서 발표하라고 했을 때의 충격을 아직도 기억하고 있다고 쓰고 있다. 물론, 당연하게도 ^^, 대부분의 학생들이 구현한 이진검색은 버그가 있었다.
문제는 자바 라이브러리에 기본으로 포함되어 있던 이진검색 조차도 버그가 숨어있었다는 것이다. 아래 글을 읽어보면 왜 20 여년간이나 이 버그가 쉽게 발견되지 않았는지에 대한 설명이 있다. 수십년간 사람들이 아무 문제없이 써오던 대중적인 라이브러리에도 이와같이 숨어있는 버그를 지적하면서 Bug-Free 소프트웨어가 얼마나 힘든 것인지를 말하고 있다.
최근까지 Java.util.Arrays 에 포함되어 기본 라이브러리로 제공되던 바이너리 서치의 코드는 아래와 같다.
자, 이 코드의 어떤 부분에 버그가 있을까..
정답은 아래 라인이다.
만약 low 와 high 가 충분히 큰 숫자라서 이 두수의 합이 integer 의 범위 ( 32 비트의 경우 2,147,483,648 ) 를 넘어서게 되면 결국 Overflow 가 발생하게 된다. 그래서 이 부분에서
mid 값을 배열 a 의 인덱스로 사용한 부분에서 배열의 잘못된 인덱스로 접근하게 되어 생기는 ArrayIndexOutOfBoundsException 에러가 나게 된다.
* 주의사항 : 조수아 벤틀리는 원문에서 두 양수의 합이 Overflow 가 나는 경우 그 결과는 음수가 되어 배열의 인덱스를 음수로 접근하게 되어 ArrayIndexOutOfBoundsException 에러가 난다고 쓰고 있으나, 후에 덧글을 통해서 C99 스펙의 경우 signed integer 의 두 수의 overflow 의 경우 항상 음수가 되는 것은 아닌 undefined 가 된다고 수정하고 있다. 어쨌든 에러는 에러이다... ^^ ;
조수아 벤틀리는 이 라인을 아래와 같이 고치는 것이 좋겠다고 쓰고 있다. ( C / C++ 의 경우 )
참고로 비트연산자 >> 1 은 /2 와 같다. >> 1 과 같이 비트연산으로 계산을 할 경우 /2 보다 조금 더 빠르다. ;)
- 그런데, 조수아 벤틀리가 제시한 저 수정안도 low 와 high 의 값의 합이 unsigned int 의 범위를 넘게 된다면 여전히 Overflow 문제가 생길 수 있다... -_-; 결국 ASSERT 등을 사용해서 인덱스의 범위 내에서만 사용이 가능하도록 제약을 걸거나, Overflow 를 피하려면 여유있게 long long 과 같은 64 비트 변수를 쓰는 것이 보다 안전할 것 같다.
'Contest > Algorithm' 카테고리의 다른 글
| "누워서 읽는 알고리즘" 의 퀴즈 정답... (2) | 2010.06.20 |
|---|---|
| Monty Hall Problem (8) | 2009.09.15 |
| 최대공약수(GCD) 와 최소공배수(LCM) (10) | 2008.10.15 |
| 퀵소트(Quick Sort) 의 시간복잡도(Time Complexity) (14) | 2008.09.12 |
| 소수 구하기 (Finding Primes) 알고리즘 (8) | 2008.01.18 |