Khi cần một tập chuỗi — một từ điển, một danh sách khóa, một bộ tên người dùng — có hai lựa chọn kinh điển: một bảng băm, hoặc một trie (cây tiền tố). Trie thường được giới thiệu như cấu trúc "đúng" cho chuỗi: tra một chuỗi dài L mất O(L) không phụ thuộc số khóa, nghe hấp dẫn hơn hẳn băm. Tôi vào bài với niềm tin trie sẽ thắng bảng băm ở cả tốc độ lẫn bộ nhớ. Đo xong, tôi phải viết lại gần như toàn bộ kết luận.
Trie: mỗi cạnh một ký tự
Một trie lưu tập chuỗi dưới dạng cây, trong đó mỗi cạnh là một ký tự. Đường đi từ gốc xuống một nút chính là một tiền tố; nếu nút đó được đánh dấu "kết thúc", tiền tố ấy là một khóa hoàn chỉnh. Các khóa chung tiền tố tự động dùng chung phần đường đi đầu — "cat", "car", "card" cùng đi qua nhánh c → a. Tra một chuỗi dài L là đi đúng L bước từ gốc, mỗi bước rẽ theo một ký tự: O(L), và quan trọng là không phụ thuộc tập có bao nhiêu khóa — dù một nghìn hay một tỉ khóa, tra "card" vẫn chỉ đi 4 bước.
Nghe như luôn thắng bảng băm. Nhưng hãy nhìn kỹ: bảng băm tra một chuỗi cũng là O(L). Nó đọc cả L ký tự để tính mã băm, rồi so chuỗi một lần ở xô tương ứng. Cả hai đều O(L) — nên "trie tra O(L)" không phải một lợi thế so với băm như tôi tưởng. Sự khác biệt thật nằm ở chỗ khác: cách chúng chạm bộ nhớ.
Đo: tra chính xác, bảng băm nhanh hơn 3,4 lần
Tôi dựng 200.000 khóa chuỗi ngẫu nhiên (dài 4–10 ký tự), nạp vào cả một trie 26 nhánh lẫn một bảng băm, rồi tra 5 triệu lần các khóa có thật:
Tra chính xác 5 triệu lần (khóa có thật):
trie (đi L nút, nhảy con trỏ) : 342 ms
bảng băm (1 lượt băm + so) : 100 ms -> băm nhanh hơn 3,4 lần
Bảng băm nhanh hơn 3,4 lần, ngược hẳn kỳ vọng của tôi. Lý do là mẫu truy cập bộ nhớ. Bảng băm đọc chuỗi tuần tự một mạch (thân thiện cache và bộ nạp trước), tính một mã băm, rồi nhảy tới đúng một chỗ trong bảng. Trie thì nhảy con trỏ từ nút này sang nút khác theo từng ký tự: mỗi bước đọc một nút nằm ở một vùng nhớ khác hẳn, và với một trie lớn phân tán khắp heap, mỗi cú nhảy dễ là một lần trượt cache phải xuống RAM. Bốn ký tự là bốn cú nhảy, bốn lần có thể trượt — trong khi băm chỉ một cú nhảy sau khi đọc chuỗi liền mạch. Đây đúng là cái giá của con trỏ mà bài dự đoán nhánh và bài cache đã đo ở dạng khác: đi theo con trỏ rải rác luôn đắt hơn đọc tuần tự.
Đo hớ về bộ nhớ: trie tốn gấp 40 lần
Định kiến thứ hai của tôi là "trie tiết kiệm bộ nhớ vì chia sẻ tiền tố". Tôi đếm số nút trie thật sự cấp phát và so với kích thước bảng băm:
Bộ nhớ cho 200.000 khóa (chưa kể bản thân chuỗi):
trie : 778.077 nút × 216 byte = 168 MB
bảng băm : 524.288 ô × 8 byte = 4,2 MB -> trie tốn gấp 40 lần
Trie tốn gấp 40 lần bộ nhớ. Mỗi nút trie 26 nhánh giữ 26 con trỏ (208 byte) cộng một cờ — nhưng phần lớn 26 ô đó rỗng, vì với khóa ngẫu nhiên rất ít nút có nhiều hơn một hai nhánh thật. Ta trả tiền cho 26 ô ở mỗi nút mà dùng chỉ vài ô. Với khóa ngẫu nhiên, các khóa gần như không chia sẻ tiền tố, nên "lợi thế chia sẻ" gần như bằng không, còn phí 26-con-trỏ-mỗi-nút thì trả đủ. Bảng băm thì gọn: một mảng con trỏ, mỗi khóa một ô.
Cần thành thật về điều kiện: khóa ngẫu nhiên là trường hợp xấu nhất cho bộ nhớ trie. Một từ điển thật (nhiều từ chung gốc, chung tiền tố) sẽ chia sẻ nhiều hơn và trie đỡ tốn hơn con số 40 lần này; các biến thể như trie nén (radix tree) hay dùng map thưa thay 26 con trỏ cũng giảm mạnh. Nhưng kết luận định tính vẫn đứng: trie không tự động tiết kiệm bộ nhớ, và trong nhiều trường hợp còn tốn hơn băm nhiều.
Vậy trie thắng ở đâu: tiền tố
Nếu băm nhanh hơn và gọn hơn cho tra chính xác, thì trie tồn tại để làm gì? Câu trả lời là thứ băm không làm được: truy vấn theo tiền tố. Tôi đo việc đếm mọi khóa bắt đầu bằng một tiền tố cho trước, cho 2.000 tiền tố:
Đếm mọi khóa có tiền tố (2 ký tự), 2.000 tiền tố:
trie (xuống nút tiền tố + duyệt nhánh) : 85 ms
bảng băm (phải quét CẢ bảng) : 2739 ms -> trie nhanh 32 lần
Trie nhanh hơn 32 lần. Với trie, mọi khóa có tiền tố "ab" đều nằm trong một cây con duy nhất: đi hai bước tới nút "ab", rồi duyệt cây con đó — chỉ chạm đúng những khóa liên quan. Bảng băm thì bó tay: mã băm của "abc" và "abd" hoàn toàn không liên quan nhau (băm cố tình xóa mọi cấu trúc, kể cả tiền tố), nên cách duy nhất để tìm mọi khóa có tiền tố "ab" là quét toàn bộ bảng và so từng khóa. Đây là điểm mấu chốt: trie giữ được thứ tự và cấu trúc tiền tố mà băm ném đi để đổi lấy tốc độ tra điểm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: chọn cấu trúc theo câu hỏi bạn sẽ hỏi, không theo kiểu dữ liệu. "Tôi có tập chuỗi" chưa đủ để chọn — phải hỏi tiếp: tôi tra chính xác (có/không), hay tôi hỏi tiền tố (mọi từ bắt đầu bằng...)? Nếu chỉ tra chính xác, bảng băm nhanh hơn và gọn hơn, dùng nó. Nếu cần tiền tố — autocomplete, gợi ý tìm kiếm, định tuyến IP theo tiền tố dài nhất, khớp từ điển — trie (hay biến thể của nó) là lựa chọn đúng, và khoảng cách 32 lần là lý do.
Hệ quả thứ hai: "cấu trúc chuyên dụng" không có nghĩa "nhanh hơn ở mọi mặt". Trie chuyên cho chuỗi, nhưng nó thua băm ở tra điểm và tốn bộ nhớ hơn nhiều — nó chỉ thắng ở đúng thao tác nó được thiết kế cho (tiền tố). Một cấu trúc chuyên dụng đổi hiệu năng phổ quát lấy hiệu năng vượt trội ở một chiều; biết chiều đó là chiều nào mới chọn đúng. Đây cùng tinh thần với việc chọn cấu trúc theo độ phức tạp thật đã bàn.
Hệ quả thứ ba là bài học đo lường của cả sê-ri, ở dạng cụ thể: O(L) của trie và O(L) của băm bằng nhau trên giấy, nhưng hằng số ẩn — cache-miss do nhảy con trỏ — làm chúng khác nhau 3,4 lần trên đồng hồ. Con số mang theo: cho tra chuỗi chính xác, bảng băm nhanh hơn trie 3,4 lần và tốn ít bộ nhớ hơn 40 lần (trie nhảy con trỏ từng ký tự = cache-miss, và 26 con trỏ mỗi nút phần lớn rỗng); nhưng cho truy vấn tiền tố, trie nhanh hơn 32 lần vì băm phải quét cả bảng — lợi thật của trie là tiền tố, không phải tốc độ tra. Big-O giống nhau không có nghĩa hiệu năng giống nhau, và "chuyên dụng" không có nghĩa "luôn tốt hơn".
Thử ba mươi giây
Mở Python và so hai cách trên một danh sách vài chục nghìn từ (ví dụ /usr/share/dict/words nếu máy bạn có). Với một set, thử "cat" in words — tức thì; rồi thử tìm mọi từ bắt đầu bằng "pre": bạn buộc phải viết [w for w in words if w.startswith("pre")], một vòng quét toàn bộ tập. Cảm nhận sự khác biệt: cái đầu chạm một chỗ, cái sau chạm mọi phần tử. Đó chính là khoảng cách 32 lần trong bài, và là lý do khi bạn cần gợi ý theo tiền tố (thanh tìm kiếm, gõ tắt), người ta dựng một trie thay vì lọc một tập — không phải vì trie "xịn hơn", mà vì nó trả lời đúng câu hỏi tiền tố mà tập không trả lời nổi.
