Tra thành viên: quét tuyến tính thắng ở n=8, còn nhị phân O(log n) không bao giờ nhanh nhất

Hỏi "phương tiện nào nhanh nhất" mà không nói quãng đường thì không có câu trả lời. Sang phòng bên cạnh, đi bộ nhanh hơn gọi taxi — vì thời gian chờ xe lớn hơn cả quãng đi. Sang tỉnh khác, ô tô thắng. Xuyên lục địa, máy bay. Và nếu tình cờ có sẵn một đường trượt thẳng tới đích, nó đè bẹp tất cả. "Nhanh nhất" không phải thuộc tính của phương tiện; nó là kết quả của cặp phương tiện × quãng đường. Bốn mươi bốn bài của sê-ri này, rút lại, chỉ nói đúng một điều đó về cấu trúc dữ liệu — và bài kết khép vòng bằng bài toán đơn giản nhất: "phần tử x có trong tập không?", đo bốn cách ở nhiều quy mô.

Một bài toán, bốn lời đáp

Tra thành viên một tập số nguyên là bài toán nền tảng, và có ít nhất bốn cách quen thuộc. Quét tuyến tính: giữ một mảng, duyệt từng phần tử — O(n). Mảng sắp + nhị phân: sắp mảng rồi tìm nhị phân — O(log n). Bảng băm: băm khóa vào xô — O(1) trung bình. Bitset: nếu khóa nằm trong một miền bị chặn, một bit cho mỗi giá trị — O(1) với hằng số cực nhỏ.

Nếu chỉ nhìn ký hiệu big-O, bảng xếp hạng rõ ràng: quét O(n) tệ nhất, nhị phân O(log n) khá, hash và bitset O(1) tốt nhất. Ai học thuật toán cũng sẽ gạt quét tuyến tính đi và chọn một trong nhóm "logarit hoặc hằng số". Tôi đo trong container gcc:13 (ARM), và bảng xếp hạng thật khác hẳn.

Đo: kẻ thắng đổi theo quy mô

Tôi đo thời gian mỗi truy vấn (ns) của cả bốn cách, với tập từ 8 tới 50.000 phần tử, khóa trong miền 2²⁰ (để bitset dùng được, cố định 128 KB):

Tra thành viên, ns mỗi truy vấn (lấy min):
  n      | quét O(n) | nhị phân | hash O(1) | bitset
      8  |     2,5   |    8,5   |    6,6    |   1,1
     64  |    16,8   |   17,8   |    6,7    |   0,4
    512  |   130,8   |   30,5   |    6,8    |   0,4
  4.096  |   998,8   |   44,1   |    6,9    |   0,4
 50.000  | 11.788,9  |   61,3   |    5,4    |   0,4

Đọc theo hàng, ba điều bất ngờ hiện ra. Ở n = 8, quét tuyến tính nhanh nhất trong nhóm so sánh — 2,5 ns, nhanh hơn cả nhị phân (8,5) lẫn hash (6,6). Tám phần tử nằm gọn trong một dòng cache, CPU quét một mạch và đoán nhánh chuẩn, trong khi hash phải tính hàm băm và nhị phân phải nhảy lung tung — chi phí cố định của chúng lớn hơn cả việc quét tám số, đúng như thời gian chờ taxi để đi sang phòng bên. Đây đúng bài học hằng số ẩn và điểm giao mà sê-ri mở màn.

Ở n lớn, hash thắng và giữ ~5-7 ns bất kể n (đúng O(1)), trong khi quét bùng lên 11.789 ns ở n = 50.000 — chậm hơn hash hơn hai nghìn lần. Và nhị phân O(log n) không bao giờ là kẻ nhanh nhất: ở n nhỏ nó thua quét, ở n lớn nó thua hash, luôn kẹt giữa. Cái "lựa chọn thông minh O(log n)" mà big-O gợi ý hóa ra là lựa chọn không bao giờ đúng trong bài toán này — vì mỗi bước nhị phân là một cú nhảy kém thân thiện cache, đắt hơn nhiều so với con số log n gợi ý.

Cú vấp cuối: và bitset đè bẹp tất cả

Còn cột cuối. Bitset thắng mọi hàng — 0,4 ns, gần như miễn phí. Nếu bạn biết miền khóa (ở đây mọi khóa trong [0, 2²⁰)), một phép kiểm tra bit đơn lẻ nhanh hơn hash chục lần và nhanh hơn quét ở n = 50.000 tới hơn hai mươi bảy nghìn lần. Đây là chỗ vấp cuối cùng của tôi, và nó tóm gọn cả sê-ri: tôi đã định so bốn cấu trúc "công bằng" theo big-O, nhưng câu hỏi quyết định không nằm trong big-O — nó là "bạn có biết gì thêm về dữ liệu không". Biết miền khóa bị chặn mở khóa một cấu trúc mà big-O của ba cái kia không nói tới — đúng cái đường trượt thẳng tới đích.

Cần thành thật về điều kiện, đúng tinh thần sê-ri: bitset thắng vì miền ở đây đủ nhỏ (128 KB). Nếu khóa là số 64-bit rải rác, bitset cần 2 exabyte — bất khả, và không gian trở thành bức tường. Kẻ thắng lại đổi. Đó chính là điểm: không có "cấu trúc tốt nhất" tồn tại tách khỏi dữ liệu; chỉ có cái hợp với n, mật độ, miền, mẫu truy cập, và phần cứng của bạn.

Cả sê-ri gói trong một bảng

Bảng nhỏ này là toàn bộ bốn mươi lăm bài. Mỗi lý do khiến kẻ thắng lệch khỏi dự đoán big-O là một bài đã đi qua: hằng số ẩn làm quét thắng ở n nhỏ (bài 1); cache làm nhị phân và danh sách liên kết chậm hơn con số lý thuyết (bài 2); điểm giao làm thuật toán "xịn hơn" thua ở quy mô nhỏ (introsort bài 15, suffix array bài 37, Karatsuba bài 40); miền và mật độ mở khóa bitset (bài 34) hay quyết định tỉ lệ nén; đua tranh đặt trần khi song song hóa và không khóa; đánh đổi thời gian–không gian (bài 43) làm merge sort nhanh hơn dù tốn RAM gấp đôi; và tất cả những con số ấy chỉ đáng tin sau khi vượt bốn cái bẫy đo lường. Big-O cho bạn hình dạng đường cong khi n tiến tới vô cùng; nó không cho bạn điểm mà dữ liệu của bạn đang đứng, cũng không cho hằng số, cache, hay miền. Những thứ đó phải đo.

Về đến code hằng ngày

Điều đầu tiên, và là thông điệp của cả sê-ri: đừng chọn cấu trúc dữ liệu bằng cách so ký hiệu O trên giấy — đo trên dữ liệu và máy thật của bạn. Big-O là công cụ tuyệt vời để loại những lựa chọn thảm họa (một thuật toán O(n²) trên n triệu là hỏng, không cần đo). Nhưng giữa các ứng viên hợp lý, kẻ thắng phụ thuộc quy mô thật, mật độ thật, mẫu truy cập thật, và phần cứng thật — những thứ chỉ đồng hồ mới nói được. "Nên dùng cây hay hash?" không có câu trả lời chung; "hãy đo với n và dữ liệu của bạn" thì có.

Điều thứ hai: biết về dữ liệu quý hơn biết thêm một cấu trúc. Cái mở khóa bitset không phải một thuật toán tinh vi, mà là một sự thật về dữ liệu — miền khóa bị chặn. Trước khi tối ưu, hỏi: n thường bao lớn, khóa nằm trong miền nào, truy cập tuần tự hay ngẫu nhiên, đọc nhiều hay ghi nhiều, một luồng hay nhiều luồng. Mỗi câu trả lời cắt bỏ vài lựa chọn và mở ra vài lựa chọn khác, và thường quyết định nhiều hơn cả việc bạn thuộc bao nhiêu cấu trúc.

Và đây là điều đẹp nhất: cái nguyên tắc "đo, đừng đoán" này chính là thứ vận hành mọi hệ thống trưởng thành ở tầng cao, chỉ khác tên. Bộ tối ưu truy vấn của CSDL không chọn kế hoạch bằng lý thuyết — nó thu thống kê (số dòng, độ chọn lọc, phân bố) rồi ước lượng chi phí thật, và một EXPLAIN ANALYZE chính là "đo trên dữ liệu của bạn". JIT của JVM chọn tối ưu theo hồ sơ chạy chứ không theo giả định tĩnh. Và mọi kỹ sư hiệu năng nghiêm túc đều sống bằng profiler, không bằng trực giác. Mẫu số chung, và là câu tạm biệt của sê-ri: big-O là la bàn — nó chỉ hướng (đường cong đi đâu khi n lớn), không chỉ khoảng cách (nhanh chậm thật ở n của bạn); muốn biết khoảng cách, phải đo, trên dữ liệu của mình, đúng cách. Suốt bốn mươi lăm phép đo, cứ mỗi lần trực giác nói "cái này chắc nhanh hơn", một con số lại đứng ra bác — hằng số ẩn, cache, điểm giao, entropy, đua tranh, đánh đổi. Đo, đừng đoán. Cảm ơn bạn đã đi hết chặng đường.

Tự thử trước khi chọn

Lần tới khi bạn định chọn một cấu trúc vì "nó O(log n), tốt hơn O(n)", dừng lại ba mươi giây và hỏi bốn câu: n của tôi thực tế bao lớn? khóa có nằm trong một miền nhỏ không? tôi tra một lần hay hàng triệu lần? dữ liệu vừa cache hay tràn cache? Rồi, nếu có thể, viết mười dòng đo hai ứng viên trên chính dữ liệu của bạn — nhớ quan sát kết quả (volatile), bỏ warmup, lấy trung vị. Rất có thể con số sẽ làm bạn ngạc nhiên, như nó đã làm tôi ngạc nhiên bốn mươi lăm lần. Và đó chính là toàn bộ điều sê-ri này muốn để lại: cái ngạc nhiên ấy chỉ đến khi bạn đo — nên hãy đo, đừng đoán.