Năm bài sắp xếp vừa rồi đều đụng một trần: O(n log n). Đó không phải sự trùng hợp — có một định lý nói rằng mọi thuật toán sắp xếp chỉ dựa vào so sánh cặp khóa không thể nhanh hơn O(n log n). Nghe như một luật vật lý của việc sắp xếp. Nhưng radix và counting sort chạy nhanh hơn thế, O(n) — và bài này đo để thấy chúng làm được bằng cách nào, rồi phát hiện rằng cái "trần" kia không phải luật vật lý, mà chỉ là luật của một trò chơi mà ta có thể từ chối chơi.
Đếm thay vì so sánh
Chìa khóa của cả hai thuật toán: chúng không bao giờ so sánh hai khóa với nhau. Chúng dùng chính giá trị khóa làm chỉ số vào một mảng. Counting sort làm điều đơn giản nhất: duyệt mảng đếm mỗi giá trị xuất hiện bao nhiêu lần, rồi từ bảng đếm đó rải các phần tử thẳng vào vị trí cuối cùng của chúng. Không so sánh gì, chỉ đếm và đặt — O(n + k), với k là miền giá trị. Nhược điểm rõ: nếu k khổng lồ (khóa 32-bit có hơn bốn tỉ giá trị), bảng đếm không kham nổi.
Radix sort (kiểu LSD) giải quyết chuyện k lớn bằng cách sắp theo từng byte của khóa. Nó chạy counting sort trên byte thấp nhất (chỉ 256 giá trị), rồi byte tiếp theo, cho tới byte cao nhất — bốn lượt cho một số 32-bit. Vì counting sort ổn định, sau đủ bốn lượt cả khóa được sắp đúng. Độ phức tạp O(d·(n + 256)), với d = số byte của khóa. Cả hai đều tuyến tính theo n, cùng phá cái trần O(n log n). Câu hỏi tôi mang vào phép đo: phá thật tới đâu, và cái giá là gì?
Đo: radix thắng ở mọi cỡ
Tôi so radix sort (base 256, bốn lượt) với introsort (thuật toán lai nhanh nhất ở bài trước) trên số 32-bit ngẫu nhiên, quét nhiều kích thước:
n introsort radix radix nhanh hơn
1 000 21,9 ns 3,4 ns 6,5 lần
100 000 35,3 ns 3,2 ns 11 lần
1 triệu 42,4 ns 7,5 ns 5,7 lần
10 triệu 49,3 ns 9,3 ns 5,3 lần
(số là nano giây mỗi phần tử). Radix thắng ở mọi kích thước — nhanh hơn 5 tới 11 lần. Và counting sort, khi áp được (khóa trong miền nhỏ), còn ấn tượng hơn: sắp 5 triệu số trong khoảng [0, 1000), counting sort mất 12 mili giây so với introsort 193 — nhanh 15,6 lần. Cái trần O(n log n) rõ ràng không phải bức tường không thể vượt. Nhưng khi nhìn kỹ bảng số, tôi nhận ra mình đã đoán sai chỗ đặt giới hạn.
Một lần tôi đo hớ: giới hạn không ở n nhỏ, mà ở khóa
Tôi vào bài với một dự đoán nghe rất hợp lý: "O(n) không phải lúc nào cũng thắng O(n log n), vì radix có hằng số ẩn — bốn lượt, cộng chi phí thiết lập — nên ở n nhỏ chắc introsort sẽ thắng, và có một điểm crossover." Tôi định đo để tìm cái crossover đó. Đo ra: không có crossover. Ngay ở n = 1000, radix đã nhanh hơn introsort 6,5 lần (3,4 so với 21,9 nano giây mỗi phần tử). Bốn lượt tuyến tính của radix vẫn rẻ hơn hẳn log n lần so sánh của introsort, ở mọi cỡ tôi thử. Dự đoán của tôi sai, và cái sai chỉ ra tôi đã tìm giới hạn nhầm chỗ.
Giới hạn thật không nằm ở n nhỏ, mà ở bề rộng khóa — chính là cái hằng số d. Tôi đo lại với khóa 64-bit, khi radix cần tám lượt thay vì bốn: nano giây mỗi phần tử tăng từ ~9 (32-bit) lên ~19 (64-bit) — gần gấp đôi, đúng như "gấp đôi số byte thì gấp đôi số lượt". Radix vẫn thắng introsort (19 so với 50 nano giây), nhưng khoảng cách hẹp lại, và ta thấy rõ quỹ đạo: khóa càng rộng, d càng lớn, tới một lúc radix không còn đáng. Cái "O(n)" của radix thực ra là O(d·n), và d không phải hằng số vũ trụ mà là bề rộng dữ liệu của bạn.
Có một hằng số ẩn thứ hai mà bảng số cũng để lộ: nhìn cột radix, nano giây mỗi phần tử nhảy từ 3,2 (ở n = 100k) lên 9,3 (ở n = 10 triệu) — tăng gần ba lần dù vẫn là "O(n)". Thủ phạm quen thuộc của cả sê-ri: cache. Bước rải của counting sort ghi mỗi phần tử vào một vị trí do giá trị nó quyết định — tức những vị trí rải rác khắp mảng (scatter), không tuần tự. Khi mảng vượt cache, mỗi lần ghi rải rác là một lần trượt cache, và hằng số của radix phình lên. Bài học đo lường: "O(n)" của một thuật toán không so sánh vẫn giấu ít nhất hai hằng số — bề rộng khóa và tính thân thiện cache — và cả hai đều đo được, đều quan trọng. Tôi đã tìm giới hạn ở chỗ dễ đoán (n nhỏ) mà đo cho thấy nó nằm ở chỗ khác (khóa và cache).
Chặn dưới là về mô hình, không phải vật lý
Điều sâu nhất của bài này không phải con số tốc độ, mà là hiểu đúng cái "chặn dưới" O(n log n). Định lý đó hoàn toàn đúng — nhưng nó là một phát biểu về một mô hình tính toán cụ thể: mô hình mà thao tác duy nhất bạn được dùng để lấy thông tin về khóa là so sánh hai khóa. Trong mô hình đó, mỗi so sánh cho một bit thông tin, và cần log(n!) ≈ n log n bit để định danh một trong n! hoán vị — nên O(n log n) là sàn không thể phá. Radix và counting sort không sống trong mô hình đó: chúng nhìn thẳng vào biểu diễn của khóa (các byte, các chữ số) và dùng nó làm chỉ số. Đổi mô hình, và cái sàn biến mất.
Nhưng đổi mô hình có giá, và cái giá là tính tổng quát. Sắp so sánh chỉ cần một thứ: một hàm so_sánh(a, b). Nhờ vậy nó sắp được bất kỳ thứ gì — chuỗi, cấu trúc, đối tượng phức tạp, khóa nhiều tiêu chí — miễn bạn định nghĩa được thứ tự. Radix và counting sort đòi hỏi khóa phải là số nguyên hoặc có độ rộng cố định để làm chỉ số được, tốn thêm bộ nhớ, và trả giá cache. Chúng là công cụ chuyên dụng sắc bén cho đúng một loại dữ liệu, không phải con dao đa năng.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi bạn sắp một lượng lớn số nguyên (hay khóa độ rộng cố định), hãy nhớ radix/counting sort tồn tại. Sắp mặc định của thư viện là sắp so sánh, tổng quát nhưng bị trần O(n log n). Nếu dữ liệu của bạn là hàng triệu số nguyên 32-bit, id, timestamp, hay khóa ngắn cố định, một radix sort có thể nhanh gấp 5–10 lần — một khoản lợi lớn mà nhiều người bỏ quên vì mặc định với tay lấy sort().
Hệ quả thứ hai, về tư duy: một "chặn dưới lý thuyết" luôn kèm theo một mô hình, và biết mô hình đó cho bạn biết khi nào phá được nó. Rất nhiều giới hạn trong khoa học máy tính có dạng này — chúng đúng trong một tập giả định, và tiến bộ thường đến từ việc nhận ra mình không buộc phải chấp nhận một giả định nào đó. Khi ai đó nói "không thể nhanh hơn X", câu hỏi đúng là "trong mô hình nào?", không phải cúi đầu chấp nhận.
Hệ quả thứ ba là con số mang theo: radix/counting sort dùng giá trị làm chỉ số nên phá được chặn dưới O(n log n) của sắp so sánh — radix thắng introsort 5–11 lần trên số 32-bit ở mọi cỡ, counting sort nhanh 15,6 lần với khóa nhỏ; nhưng "O(n)" của radix là O(d·n) với d = bề rộng khóa (32-bit 4 lượt ~9ns, 64-bit 8 lượt ~19ns) cộng scatter phá cache (ns/phần tử tăng 3 lần khi vượt cache), và chỉ dùng được cho khóa số/cố định. Chặn dưới là luật của một mô hình; đổi mô hình thì đổi luật, và cái giá là tính tổng quát.
Thử ba mươi giây
Nhìn dữ liệu bạn hay phải sắp và hỏi: khóa của tôi có phải số nguyên (hay thứ có thể coi như số nguyên độ rộng cố định) không? Nếu có, và số lượng lớn, bạn có một lối tắt mà sắp so sánh không cho: dùng giá trị làm chỉ số. Thử nhanh: lấy một mảng vài triệu số nguyên, sắp bằng hàm mặc định, rồi thử một radix sort đơn giản (bốn lượt đếm theo byte), và bấm giờ cả hai — bạn sẽ thấy khác biệt vài lần. Và mỗi khi gặp một "giới hạn lý thuyết" chặn đường, đừng hỏi "làm sao nhanh hơn được nữa" mà hỏi "giới hạn này giả định điều gì, và mình có buộc phải nằm trong giả định đó không?". Đôi khi câu trả lời là không — và đó là lúc bạn phá được cái trần tưởng như bất khả.
