Cây tìm kiếm nhị phân (BST) là cấu trúc được dạy như hiện thân của "tra cứu O(log n)": mỗi lần so sánh bỏ đi một nửa cây, nên n phần tử chỉ tốn chừng log n bước. Nghe gọn gàng và đúng — cho tới khi ta hỏi câu mà bài big-O đã dạy phải hỏi: đúng với đầu vào nào? Bài này dựng một BST thật, đo chiều cao và thời gian tra cứu khi khóa vào theo hai thứ tự khác nhau — và thấy chữ "O(log n)" gắn với BST là một lời hứa có điều kiện, điều kiện mà dữ liệu thật rất hay phá vỡ.
O(log n) của BST là một lời hứa có điều kiện
Nhắc lại cấu trúc: mỗi node giữ một khóa, con bên trái nhỏ hơn node, con bên phải lớn hơn. Tra một khóa thì bắt đầu ở gốc, so sánh, rẽ trái nếu nhỏ hơn và rẽ phải nếu lớn hơn, cứ thế đi xuống. Số bước tra bằng độ sâu của khóa trong cây, và bước tệ nhất bằng chiều cao cây. Nên toàn bộ câu chuyện hiệu năng của BST nằm ở một con số: cây cao bao nhiêu.
Và chiều cao không phải thuộc tính cố định của cây — nó do thứ tự chèn quyết định. Cùng một tập khóa, chèn vào theo thứ tự khác nhau cho ra hình dạng khác hẳn. Chèn sao cho cây xòe đều hai bên thì chiều cao chừng log n và tra nhanh. Nhưng nếu các khóa vào theo thứ tự đã sắp tăng dần, thì mỗi khóa mới đều lớn hơn mọi khóa đã có, luôn rẽ phải, và cây mọc thành một nhánh phải dài ngoằng — một xâu, đúng bằng một danh sách liên kết. Lúc đó chiều cao bằng n và tra cứu về O(n). BST không tự bảo đảm gì cả; nó O(log n) khi cân, O(n) khi lệch. Tôi đo xem khoảng cách giữa hai thái cực đó lớn tới đâu.
Đo: chiều cao và thời gian tra khi đổi thứ tự chèn
Tôi viết một chương trình C (gcc -O2), lấy n = 40.000 khóa phân biệt, chèn vào BST theo hai thứ tự: ngẫu nhiên (xáo trộn trước khi chèn) và tăng dần (chèn 0, 1, 2, ... theo đúng thứ tự). Với mỗi cây tôi đo chiều cao và độ sâu trung bình, rồi đo thời gian tra cứu trung bình bằng cách tra hàng triệu khóa ngẫu nhiên có thật, đếm luôn số node đi qua mỗi lần. Chèn và tra đều viết lặp (không đệ quy) — vì cây thoái hóa cao 40.000 tầng sẽ làm tràn ngăn xếp nếu đệ quy, một cái bẫy đáng nhớ riêng.
Chiều cao (với log2 40000 = 16):
chèn ngẫu nhiên : chiều cao 34 độ sâu trung bình 18,6
chèn tăng dần : chiều cao 40000 độ sâu trung bình 20000,5
Thời gian tra cứu (nano giây mỗi lần, và số node đi qua):
BST chèn ngẫu nhiên : 51 ns 18,6 node
BST chèn tăng dần : 32672 ns 20002 node
Con số nói thẳng: cây chèn ngẫu nhiên cao 34, đúng cỡ 2·log2 n như lý thuyết cây ngẫu nhiên dự đoán, và tra một khóa mất 51 nano giây. Cây chèn tăng dần cao 40.000 — bằng đúng số khóa, tức nó là một xâu — và tra một khóa mất 32.672 nano giây, tức 640 lần chậm hơn. Con số 20002 node đi qua mỗi lần tra là dấu vết không thể chối: mỗi lần tra phải lê qua nửa cái xâu, y hệt một vòng lặp quét tuyến tính. "Cây nhị phân" ở đây không nhị phân gì cả; nó là danh sách liên kết đội lốt cây.
Một lần tôi đo hớ: "cây nhị phân" không tự làm gì nhanh
Cú hớ đầu tiên là cái tôi vừa đo ở trên, và tôi thú nhận đã suýt bỏ qua. Tôi vào bài định viết "BST cho tra cứu O(log n)" như một sự thật hiển nhiên — vì nó là cây nhị phân, mỗi bước chia đôi, còn gì phải bàn. Nhưng "chia đôi" chỉ đúng khi cây cân, và không có gì trong BST thường bắt nó cân. Khi tôi thử đúng cái đầu vào mà thực tế đẻ ra nhiều nhất — khóa đã sắp — cây sụp thành xâu và tra chậm 640 lần. Đây không phải ca hiếm học thuật: id tự tăng, timestamp, dữ liệu vừa import từ một file đã sort, khóa đọc tuần tự từ một chỉ mục — tất cả đều "đã sắp", và tất cả đều dựng cho bạn một cái xâu nếu bạn đổ thẳng vào một BST thường.
Cú hớ thứ hai bất ngờ hơn, và tôi đo ra ngược với dự đoán của mình. Tôi thêm một phép so: tìm nhị phân trên một mảng đã sắp cùng n phần tử. Tôi chắc mẩm mảng sẽ thắng cây ngẫu nhiên đậm, vì mảng nằm liền một khối bộ nhớ (thân thiện cache), còn cây phải nhảy theo con trỏ (mỗi bước một node ở địa chỉ ngẫu nhiên, dễ trượt cache — pointer-chasing). Đo ra: tìm nhị phân trên mảng 52 ns, cây ngẫu nhiên 51 ns — ngang nhau. Vì sao lợi thế cache của mảng không hiện ra? Vì tìm nhị phân cũng nhảy lung tung: nó nhảy tới giữa, rồi giữa của nửa, mỗi bước tới một chỗ xa — không hề tuần tự, nên cũng trượt cache. Thêm nữa mỗi so sánh của tìm nhị phân là một rẽ nhánh gần như 50-50, CPU đoán sai liên tục (như bài tìm tuyến tính và nhị phân đã đo). Hai bất lợi đó xóa sạch cái lợi "nằm liền khối". Bài học kép: "nhị phân" trong tên gọi không tự làm cho tra cứu nhanh — hình dạng thật của cây (do thứ tự chèn) mới quyết định, và ngay cả hình dạng đẹp cũng không tự nhanh hơn một mảng vì cả hai đều trả giá cache và đoán nhánh như nhau.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, và cấp bách nhất: đừng đổ khóa đã sắp vào một BST thường. Đây là một trong những cái bẫy hiệu năng âm thầm nhất, vì nó qua được mọi test bạn viết. Test thường dùng dữ liệu ngẫu nhiên, cây xòe đẹp, mọi thứ O(log n), xanh hết. Rồi production nạp dữ liệu thật — đã sort theo id, theo thời gian — cây thành xâu, và thao tác vốn log n giờ là n, chậm dần theo kích thước mà không có một dòng lỗi nào. Nếu bạn phải nạp dữ liệu đã sắp vào cây, hãy xáo trộn trước khi chèn, hoặc dùng cây tự cân bằng (chủ đề bài sau).
Hệ quả thứ hai: luôn đo chiều cao cây thật, đừng tin nhãn O(log n) dán trên cấu trúc. Big-O của BST là O(chiều cao), và chiều cao là biến số, không phải hằng. Nếu bạn đang dùng một cây trong hệ thống thật và nghi ngờ hiệu năng, đo chiều cao của nó: nếu nó gần log n thì cây khỏe, nếu nó gần n thì cây đã thoái hóa và bạn đang chạy một danh sách liên kết đắt tiền. Con số đó nói cho bạn sự thật mà ký hiệu tiệm cận giấu đi.
Hệ quả thứ ba là bài học đo lường bao trùm: một cấu trúc "tốt về mặt tiệm cận" vẫn phải hỏi hằng số và hình dạng đầu vào. Con số mang theo: BST chèn ngẫu nhiên cao 34, tra 51ns; cùng dữ liệu chèn tăng dần thì cao 40000, tra 32672ns — chậm 640 lần, đúng bằng quét tuyến tính; và một mảng nhị phân đẹp về cache cũng chỉ 52ns, không nhanh hơn cây cân bằng, vì tìm nhị phân cũng trượt cache và đoán nhánh sai. Cây nhị phân là một ý tưởng hay, nhưng cái tên không phải một lời bảo đảm — thứ tự chèn và phần cứng bên dưới mới viết nên con số cuối cùng.
Thử ba mươi giây
Nhìn vào cách dữ liệu chảy vào cấu trúc tra cứu của bạn và hỏi một câu: khóa vào có đã được sắp không? Nếu bạn đọc bản ghi theo id tăng dần, theo timestamp, hay từ một file đã sort rồi chèn từng cái vào một cây tìm kiếm tự cài, thì gần như chắc chắn bạn đang dựng một cái xâu chứ không phải một cái cây — và bạn sẽ không thấy điều đó cho tới khi dữ liệu đủ lớn để chậm rõ. Cách thử nhanh nhất: đếm chiều cao cây sau khi nạp xong (một hàm đệ quy nhỏ, hoặc lặp), rồi so với log2(n). Bằng nhau cỡ vài lần thì ổn; lệch tới cỡ n thì bạn vừa tìm ra thủ phạm. Và nếu bạn định thay cây bằng "mảng nhị phân cho nhanh vì cache", hãy đo cả hai trước — rất có thể chúng ngang nhau, và cái bạn thật sự cần là chữa cái cây, không phải đổi sang mảng.
