Bốn bài vừa rồi đo bốn thuật toán sắp xếp, 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ùng của loạt sắp xếp: vậy cái nào là tốt nhất? Bài này đ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ì.
Đo: 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 11 — một mảng đã sắp sẵn:
quicksort pivot cuối (bài 11), 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.
Một lần tôi đo hớ: "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.
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 đo lường 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, chủ đề một bài sau) — 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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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 11 đã thấy.
Hệ quả 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.
Hệ quả thứ ba là con số mang theo: thuật toán sắp xếp thực dụng nhất là một hỗn hợp — introsort ghép quicksort (nền nhanh) + insertion (mảng nhỏ, đáng ~14%) + heapsort (lưới an toàn, gần như miễn phí); cùng mảng đã sắp giết quicksort pivot cuối (331ms, đệ quy 50000 tầng) thì introsort xong trong 0,27ms với đệ quy 12 tầng. "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à chỉ đo mới cho biết ghép thế nào và mỗi mảnh đáng bao nhiêu.
Thử ba mươi giây
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ì. Nếu là C++, bạn sẽ thấy std::sort được mô tả là "introspective sort" — chính là introsort trong bài này. Nếu là Python hay Java, bạn sẽ thấy "Timsort" và cụm từ "adaptive, stable". Đó không phải chi tiết vô bổ: nó nói cho bạn biết hàm đó sẽ nhanh trên dữ liệu gần sắp của bạn (timsort), hoặc ổn định hay không (introsort của C++ thì không — muốn ổn định phải dùng stable_sort). Và lần tới khi bạn định tự cài một thuật toán "kinh điển" vì nó nghe đơn giản, hãy nhớ rằng 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.
