Chuyện về midpoint trong Binary Search và....bug
Bạn đã tự tin mình hiểu và tính midpoint của Binary Search chuẩn chưa?
Nếu bạn nào quên hoặc chưa biết Binary Search là gì có thể xem đoạn code dưới đây
https://gist.github.com/KhoaVanNguyen/5284ae2c0b9e8d8745c4370f1af5d996
Một câu chuyện có thật là Jon Bentley - tác giả của quyển sách lập trình nổi tiếng Programming Pearls. Sau 20 năm sách xuất bản mới có người tìm ra được bug trong đoạn code này?
Vậy bug ở đâu?
Dựa vào tiêu đề của bài này, bạn đã có thể đoán ra bug nằm ở:
dòng 14
midPoint \= lowerBound + ( upperBound - lowerBound ) / 2
Có lẽ một số bạn học Binary Search gần đây, một số thầy giáo đã sửa chỗ này lại nhưng không giải thích tại sao phải là
midPoint \= lowerBound + ( upperBound - lowerBound ) / 2
mặc dù giá trị của midPoint vẫn không thay đổi mấy?
Nguyên nhân
Ngắn gọn lỗi này là do tràn dữ liệu. Việc bạn cộng lowerBound và upperBound
lowerBound + upperBound
như thế này có thể tràn dữ liệu. Bởi vì tổng có thể lớn hơn giá trị cho phép của int là [math] 2^{31} -1 [/math]
Mà nếu tràn dữ liệu thì tổng của 2 số này sẽ là số âm. Mà số âm chia 2 thì lại là số âm nên sẽ gây ra bug.
Ngược lại, khi lấy upperBound - lowerBound sẽ tránh được lỗi này.
Mặc dù theo suy nghĩa bình thường thì cả 2 cách midPoint đều ra một giá trị. Nhưng khi đặt vào ngữ cảnh thuật toán Binary Search ta thấy hậu quả thật gê gớm.
Why?
Vậy tại sao phải mất thời gian lâu như vậy, một đại cao thủ trong võ lâm như Jon Bentley mới phát hiện ra lỗi này?
"Mấy chú nói anh viết sách sai là không đúng. Hồi xưa anh tính midPoint vậy là ổn dồi nha, xài mảng cỡ [math]2^{30} [/math] phần tử vẫn đúng nha " - Jon Bentley - tui lược dịch
Đùa vậy thôi, chứ hồi xưa chính tác giả cũng không ngờ đến trường hợp này, đây mới là nguyên văn của tác giả:
"The first binary search was published in 1946; when was the first correct search published?" -
Trang 68 - Programming Pearls
Bài học rút ra
Bug hồi xưa không có không có nghĩa là bây giờ cũng vậy.
Chính mình nhiều lần lên mạng copy paste đoạn code về y chang từng dấu cách mà vẫn không chạy được. Hay gõ y chang code trong sách vẫn bug. Mà nếu khi code chạy được khi test với những input khác nhau vẫn có bug, hay lúc chạy được lúc không.
Bài học đó là chính là ngay cả từng đoạn code nhỏ nhất cũng rất khó để viết đúng chuẩn, và đa số code trên thế giới này đều rất là phức tạp và không nhỏ tý nào
Dù có "pro" thế nào, như tác giả quyển Programming Pearls cũng mất vài thập kỉ mới có người tìm ra được bug. Vì thế chúng ta phải cẩn thận, code tới đâu hiểu tới đó. Code chạy được không có nghĩa là không có bug!
Bug không tự sinh ra và mất đi - Chỉ chúng ta không thấy mà thôi - Khoa
Reference
http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search
http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search
http://www.csit.parkland.edu/~mbrandyberry/CS1Java/images/Lesson27/
https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://stackoverflow.com/questions/3038392/do-java-arrays-have-a-maximum-size