Câu hỏi 'thuật toán sắp xếp nào tốt nhất' có câu trả lời sai — đây là lý do

Không có vận động viên nào vô địch cả chạy nước rút, chạy marathon lẫn nhảy cao — nên các đội thi mười môn phối hợp không tìm một siêu nhân, họ ghép một đội mà mỗi người gánh phần mình giỏi. Sắp xếp cũng đúng vậy. Bốn bài vừa rồi đo bốn thuật toán, và mỗi cái để lại một vết nứt. Quicksort nhanh nhưng có ca xấu O(n²) và tràn ngăn xếp. Merge sort an toàn và ổn định nhưng tốn O(n) bộ nhớ. Heapsort bảo đảm và tại chỗ nhưng chậm vì cache. Insertion sort O(n²) nhưng vô địch ở mảng nhỏ và dữ liệu gần sắp. Câu hỏi cuối của loạt sắp xếp: vậy cái nào tốt nhất? Tôi đo, và câu trả lời không phải một cái tên — mà là một cách nghĩ khác về "tốt nhất".

Không thuật toán đơn nào thắng mọi mặt

Nhìn lại bốn vết nứt, một mẫu hình hiện ra: mỗi thuật toán mạnh ở đúng chỗ thuật toán khác yếu. Quicksort nhanh ở ca thường nhưng có ngày tồi tệ; heapsort không bao giờ có ngày tồi tệ nhưng chậm đều; insertion sort thắng ở mảng nhỏ nơi quicksort trả phí thiết lập. Điều này gợi ý rằng thuật toán sắp xếp "tốt nhất" không phải chọn một cái và chịu điểm yếu của nó, mà là ghép nhiều cái lại sao cho điểm mạnh của cái này che điểm yếu của cái kia. Đó chính xác là điều các thư viện chuẩn làm.

Introsort — thuật toán sau std::sort của C++ — ghép ba mảnh: nó chạy quicksort median-3 làm nền (nhanh ở ca thường); khi một mảng con nhỏ hơn một ngưỡng, nó chuyển sang insertion sort (nhanh nhất ở cỡ đó); và nếu đệ quy đi quá sâu (quá 2·log₂n, dấu hiệu quicksort đang suy biến), nó chuyển hẳn sang heapsort để bảo đảm O(n log n), chặn đứng ca O(n²). Timsort — thuật toán của Python và Java — đi hướng khác: nó là merge sort adaptive, dò các đoạn đã sắp sẵn trong dữ liệu (run) và dùng insertion cho các đoạn ngắn, nên trên dữ liệu gần sắp nó về gần O(n) và luôn ổn định. Cả hai đều là lai. Tôi cài introsort để đo hai câu hỏi: việc ghép insertion vào đáng bao nhiêu, và cái lưới heapsort cứu được gì.

Ngưỡng insertion đáng ~14%, và cái lưới cứu mạng

Trước tiên, ngưỡng insertion. Tôi chạy introsort trên 4 triệu số ngẫu nhiên và quét ngưỡng cutoff — cỡ mảng con mà dưới đó ta dừng quicksort và để insertion sort dọn:

cutoff = 1   (quicksort thuần) : 210 ms   (100%)
cutoff = 16                    : 192 ms   (91%)
cutoff = 64  (tối ưu)          : 181 ms   (86%)
cutoff = 128                   : 182 ms   (87%)

Có một đáy quanh cutoff 32–64, và việc thêm insertion sort làm cả sort nhanh hơn khoảng 14%. Đây là chỗ tôi đã kỳ vọng sai, và tôi sẽ nói ở phần sau. Còn cái lưới heapsort thì đo bằng độ bền: tôi lấy đúng đầu vào đã giết quicksort pivot-cuối ở bài quicksort — một mảng đã sắp sẵn:

quicksort pivot cuối, mảng đã sắp n=50k : 331 ms, đệ quy sâu 49 999 (= n, sắp tràn ngăn xếp)
introsort,            mảng đã sắp n=50k : 0,27 ms, đệ quy sâu 12  (nhanh ~1250 lần)
introsort,            mảng đã sắp n=4tr : 29 ms,  đệ quy sâu 18  (giới hạn 44)

Cùng một đầu vào biến quicksort ngây thơ thành O(n²) với đệ quy n tầng, introsort xử lý trong một phần tư mili giây với đệ quy 12 tầng. Điều thú vị: cái lưới heapsort ở đây thực ra không cần kích hoạt — median-3 một mình đã giữ đệ quy nông (18 tầng, dưới giới hạn 44), nên heapsort không chạy phát nào. Cái lưới là bảo hiểm gần như miễn phí: nó không tốn gì ở ca thường, và chỉ bung ra ở những đầu vào ác ý được chế riêng để đánh lừa median-3.

"Tốt nhất" không phải một thuật toán

Cú hớ lớn của tôi là khung câu hỏi ban đầu: tôi vào loạt bài này tìm thuật toán sắp xếp tốt nhất, như thể có một người thắng cuộc duy nhất. Đo hết bốn cái rồi ghép lại, tôi phải bỏ chính câu hỏi đó. Cái nhanh-và-bền thật sự — thứ chạy trong thư viện chuẩn mà hàng tỉ chương trình dùng — không phải một thuật toán, mà là một tổ hợp: quicksort cho tốc độ trung bình, insertion cho mảng nhỏ, heapsort cho lưới an toàn. Mỗi mảnh có một điểm yếu chí mạng, và cách chữa không phải tìm một mảnh hoàn hảo (không có), mà là xếp chúng sao cho không điểm yếu nào lộ ra. "Tốt nhất" là một kiến trúc, không phải một cái tên — đúng cái đội mười môn phối hợp ở đầu bài.

Cú hớ nhỏ hơn nằm ở con số 14%. Sau bài insertion sort, nơi tôi đo insertion nhanh hơn quicksort 1,3–1,5 lần ở mảng nhỏ, tôi tưởng việc nhét insertion vào introsort sẽ tăng tốc nhiều — có khi 30–40%. Đo ra chỉ 14%. Lý do rõ khi nghĩ về nơi công sức nằm: trong một cây đệ quy quicksort, các mảng con nhỏ đông về số lượng nhưng mỗi cái chứa rất ít phần tử, nên tổng công ở tầng lá chỉ chiếm một phần nhỏ của toàn bộ việc sắp. Tăng tốc một phần nhỏ 1,5 lần thì cả sort chỉ nhanh lên chút ít. Bài học kèm theo: một cải tiến lớn trên một phần nhỏ của công việc chỉ cho một cải tiến nhỏ trên tổng thể (đúng tinh thần luật Amdahl) — và đó là lý do đừng chỉnh ngưỡng cutoff quá tay: qua khỏi 32–64 thì đường cong phẳng, tinh chỉnh thêm là công cốc.

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

Điều đầu tiên, và thực dụng nhất: dùng hàm sort của thư viện chuẩn, đừng tự viết. std::sort, Arrays.sort, sorted() của Python không phải "một thuật toán trong sách" — chúng là những cỗ máy lai được đo và tinh chỉnh hàng thập kỷ, đã xử lý sẵn mọi ca xấu (đã sắp, sắp ngược, nhiều phần tử trùng, mảng nhỏ) mà một quicksort tự viết sẽ vấp. Bạn gần như không thể đánh bại chúng, và rất dễ viết ra một quả bom O(n²) như bài quicksort đã thấy.

Điều thứ hai, về cách nghĩ: khi không có giải pháp nào hoàn hảo, hãy ghép các giải pháp không hoàn hảo theo ngưỡng đo được. Đây là một khuôn mẫu vượt xa sắp xếp: mỗi thành phần gánh phần nó giỏi, một cơ chế phát hiện (cỡ mảng, độ sâu đệ quy) chuyển giữa chúng, và kết quả bền hơn bất kỳ mảnh đơn nào. Nhưng chú ý hệ quả của con số 14%: khi ghép, hãy đo đóng góp thật của mỗi mảnh trên tổng thể, đừng cho rằng một mảnh nhanh cục bộ sẽ tạo khác biệt lớn toàn cục.

Và cái khuôn "hỗn hợp lai" này chính là thứ bạn gọi mỗi ngày mà không để ý, với những khác biệt đáng biết. Java Arrays.sort dùng hai cỗ máy khác nhau tùy kiểu: dual-pivot quicksort cho mảng số nguyên thô (int[]), nhưng Timsort cho mảng đối tượng (Object[]) — vì đối tượng cần sắp ổn định (giữ nguyên thứ tự các phần tử bằng nhau) còn số nguyên thì không. Python sorted()/list.sort() luôn là Timsort, luôn ổn định, và cực nhanh trên dữ liệu gần sắp — nên dữ liệu đã "gần đúng thứ tự" của bạn được hưởng gần O(n) miễn phí. C++ std::sort là introsort và không bảo đảm ổn định (muốn ổn định phải gọi std::stable_sort), Go sort.Sort cũng không ổn định (dùng sort.Stable nếu cần). Cơ sở dữ liệu thì ORDER BY chạy sort ngoài (external merge sort) khi dữ liệu vượt work_mem. Mẫu số chung: "tốt nhất" trong kỹ thuật hiếm khi là một ý tưởng thuần khiết thắng tuyệt đối — thường là một tổ hợp khéo léo che lẫn khuyết điểm cho nhau, và biết hàm sort của mình là loại lai nào (ổn định không? adaptive không?) cho bạn biết nó sẽ cư xử ra sao trên dữ liệu thật.

Muốn tự thấy thì mở tài liệu hàm sort của ngôn ngữ bạn dùng và tìm xem nó là thuật toán gì. C++ sẽ ghi std::sort là "introspective sort" — chính là introsort trong bài. Python hay Java sẽ ghi "Timsort" kèm "adaptive, stable". Đó không phải chi tiết vô bổ: nó cho biết hàm sẽ nhanh trên dữ liệu gần sắp của bạn (timsort), và ổn định hay không (introsort C++ thì không). Và lần tới khi định tự cài một thuật toán "kinh điển" vì nó nghe đơn giản, hãy nhớ cái trong thư viện không đơn giản — nó là một hỗn hợp đã trả giá bằng nhiều năm đo đạc để không bao giờ có ngày tồi tệ, và đó là thứ bạn muốn đứng trên vai, không phải viết lại.