Cái trần O(n log n) mà ai cũng tin là tuyệt đối — hóa ra chỉ là luật một trò chơi

Muốn xếp một cỗ bài lộn xộn theo thứ tự, bạn có thể so từng đôi lá — chậm. Hoặc: trải ra mười ba ô trống trên bàn (một ô mỗi quân số), rồi ném mỗi lá vào đúng ô của nó, cuối cùng gom lại — không so lá nào với lá nào, chỉ nhìn số rồi ném vào chỗ. Cách thứ hai nhanh hơn hẳn, và nó chính là ý tưởng của radix và counting sort. Năm bài sắp xếp trước đều đụng một trần: O(n log n). Đó không phải trùng hợp — có một định lý nói mọi thuật toán chỉ dựa vào so sánh cặp khóa không thể nhanh hơn thế. Nghe như một luật vật lý. Nhưng radix và counting sort chạy O(n), nhanh hơn — và tôi đo để thấy chúng làm được bằng cách nào, rồi phát hiện 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 — đúng cái "ném lá bài vào ô của nó". 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ì?

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.

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. Điều rút ra: "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ề đến code hằng ngày

Điều đầ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().

Và bạn hưởng chính kỹ thuật này ở những chỗ ít ngờ nhất. Các cơ sở dữ liệu cột và engine phân tích hiện đại (ClickHouse, DuckDB, Spark) dùng radix sort cho cột số nguyên vì nó nhanh hơn hẳn quicksort ở quy mô lớn; nhiều thư viện của NumPy/pandas chọn radix cho kind='stable' trên số nguyên. Nhưng đây cũng là chỗ có một cái bẫy tinh tế mà dân ứng dụng cao cấp hay quên: sắp mặc định của ngôn ngữ là sắp so sánh — Java Arrays.sort(int[]) dùng dual-pivot quicksort O(n log n) chứ không radix, Go sort.Ints cũng vậy — nên "O(n) miễn phí" không tự đến, bạn phải chủ động chọn thư viện radix. Còn ở tầng cơ sở dữ liệu, một ORDER BY trên cột không index vẫn là sắp so sánh và có thể tràn ra đĩa; đó là lý do index (B-tree, đã sắp sẵn) tồn tại. Mẫu số chung, và là điều đáng mang theo: một "chặn dưới lý thuyết" luôn kèm một mô hình — 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; radix phá được O(n log n) đúng vì nó từ chối chơi trò chơi chỉ-được-so-sánh, và trả giá bằng tính tổng quát.

Muốn tự thấy thì 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ả.