Thuật toán 'hoàn hảo trên giấy' này lại chậm nhất — và càng dữ liệu lớn càng tệ

Trên hồ sơ tuyển dụng, một ứng viên có đủ mọi ô đánh dấu — bằng cấp, kinh nghiệm, kỹ năng — nghe như lựa chọn hiển nhiên. Nhưng cái hồ sơ đẹp ấy không có ô nào tên là "hợp với công việc thật", và đôi khi người trông kém hoàn hảo trên giấy lại làm việc tốt hơn. Heapsort là cái hồ sơ đẹp đó. Sau ba bài về sắp xếp, ta có một bức tranh: quicksort nhanh nhưng có ca xấu O(n²), merge sort an toàn nhưng tốn O(n) bộ nhớ. Heapsort bước vào như kẻ hứa gộp cả hai ưu điểm: O(n log n) bảo đảm như merge, mà tại chỗ không tốn bộ nhớ phụ như quicksort. Trên giấy nó gần như hoàn hảo. Tôi đo xem lời hứa đó đứng vững tới đâu — và câu trả lời là một trong những minh họa rõ nhất cả sê-ri về việc cùng một big-O có thể giấu một khác biệt gấp đôi.

Heapsort: dùng heap để sắp

Heapsort mượn thẳng cấu trúc heap ở bài về hàng đợi ưu tiên. Nó làm hai bước. Bước một: biến cả mảng thành một max-heap bằng heapify từ dưới lên, O(n) — giờ phần tử lớn nhất nằm ở gốc (đầu mảng). Bước hai: lặp n lần, mỗi lần đổi gốc (max hiện tại) xuống cuối vùng heap, thu nhỏ heap đi một, rồi sift-down để khôi phục tính heap. Sau n lần, mảng được sắp tăng dần, và tất cả diễn ra ngay trên mảng gốc — không một byte bộ nhớ phụ. Mỗi sift-down tốn O(log n), lặp n lần, nên tổng là O(n log n) bảo đảm, không có đầu vào nào phá được.

Nhìn danh sách phẩm chất, heapsort như kẻ chiến thắng: O(n log n) bảo đảm (không có ngày tồi tệ O(n²) như quicksort pivot dở), và tại chỗ (không cần mảng đệm O(n) như merge). Nó chỉ thiếu tính ổn định. Vậy hẳn nó phải ít nhất chạy ngang quicksort và merge? Tôi đo cả ba trên cùng dữ liệu, và bất ngờ nằm ở đó.

Chậm nhất trong ba, và càng lớn càng chậm

Tôi cài heapsort, và mang quicksort trung vị-của-ba cùng merge sort từ hai bài trước, sắp cùng những mảng số ngẫu nhiên ở nhiều kích thước:

n            quicksort   merge   heapsort   heapsort/quicksort
100 nghìn        4 ms      5 ms      6 ms         1,43×
1 triệu         46 ms     57 ms     77 ms         1,66×
4 triệu        202 ms    251 ms    361 ms         1,79×
16 triệu       874 ms   1102 ms   2072 ms         2,37×

Heapsort chậm nhất ở mọi kích thước, dù nó O(n log n) và tại chỗ y như (hoặc hơn) hai cái kia. Và điều đáng chú ý hơn: tỉ số heapsort/quicksort tăng dần theo n — từ 1,43 lần ở 100 nghìn phần tử lên 2,37 lần ở 16 triệu. Big-O nói ba thuật toán này ngang nhau; đồng hồ nói heapsort từ chậm-hơn-chút thành chậm-gấp-đôi khi dữ liệu lớn lên. Con số tăng dần đó không phải nhiễu — nó là một dấu vân tay, và tôi đã suýt bỏ qua nó.

"Hoàn hảo trên giấy" thua vì cache

Tôi vào bài với một kỳ vọng gọn: heapsort có bộ phẩm chất tốt nhất — bảo đảm và tại chỗ — nên nó phải là lựa chọn mặc định hợp lý, ít nhất ngang ngửa hai cái kia. Đo ra nó chậm nhất, và tôi phải hỏi vì sao. Có hai nguyên nhân, và việc tách chúng ra là bài học.

Nguyên nhân thứ nhất lộ khi đếm số phép so sánh: ở 4 triệu phần tử, heapsort làm 40,8 phép so sánh mỗi phần tử, trong khi quicksort 24 và merge 20,7 — heapsort so sánh gấp khoảng 1,7 lần. Đó là một bất lợi thật, nhưng nó cố định theo tỉ lệ, không giải thích được vì sao tỉ số thời gian tăng từ 1,43 lên 2,37. Nếu chỉ là số so sánh, tỉ số phải đứng yên.

Nguyên nhân thứ hai giải thích phần tăng đó, và nó là cache — đúng con quái vật đã xuất hiện suốt sê-ri, từ bài về cache tới cây tự cân bằng. Hãy nhìn mẫu truy cập của sift-down: nó đi từ ô i xuống con của nó ở 2i+1, rồi xuống 4i+3, rồi 8i+7... — chỉ số nhân đôi mỗi tầng, nên mỗi bước nhảy xa gấp đôi bước trước, rải khắp mảng. Đây là mẫu truy cập tệ nhất có thể cho cache: không có tính cục bộ, không đoán trước được, mỗi bước sâu là một lần trượt cache mới. Ngược hẳn với quicksort, vốn phân hoạch bằng cách quét tuyến tính qua mảng (bộ nạp trước yêu thích), và merge, vốn cũng đọc tuần tự. Khi mảng còn nhỏ và nằm gọn trong cache (100 nghìn phần tử, 391 KB), sự nhảy nhót đó không tốn mấy — heapsort chỉ chậm 1,43 lần, gần đúng phần bất lợi so sánh. Khi mảng vượt xa cache (16 triệu phần tử, 63 MB), mỗi cú nhảy thành một lần chờ RAM, và heapsort tụt xuống 2,37 lần. Bằng chứng nằm ở chính con số tăng dần: tỉ số lớn lên đúng khi dữ liệu tràn khỏi cache là chữ ký của một vấn đề cache, không phải một vấn đề đếm phép toán. Điều rút ra: ba thuật toán cùng O(n log n) không hề chạy như nhau; khác biệt nằm ở tính thân thiện cache, thứ mà big-O hoàn toàn mù, và chỉ đo một đường cong theo n mới tách được nó khỏi các hằng số cố định.

Vậy heapsort để làm gì?

Nếu heapsort chậm nhất, sao nó vẫn là thuật toán kinh điển được dạy và dùng? Vì tốc độ không phải điểm mạnh của nó — sự bảo đảm mới là. Heapsort là thuật toán sắp xếp duy nhất trong ba vừa cho O(n log n) chắc chắn (không ca xấu) vừa dùng bộ nhớ hằng số (tại chỗ). Đó chính xác là hồ sơ bạn cần cho một lưới an toàn: khi bộ nhớ chật đến mức không kham nổi mảng đệm O(n) của merge, và khi bạn tuyệt đối không được phép gặp ca O(n²) của quicksort. Đây là lý do các thư viện sắp xếp thực dụng (introsort) chạy quicksort cho nhanh ở ca thường, nhưng theo dõi độ sâu đệ quy, và khi thấy quicksort có nguy cơ suy biến thì chuyển sang heapsort để bảo đảm không bao giờ chạm O(n²). Heapsort không phải tay đua; nó là dây an toàn.

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

Điều đầu tiên: đừng chọn thuật toán chỉ vì bảng phẩm chất trên giấy đẹp. Heapsort thắng mọi ô trong bảng so sánh lý thuyết (bảo đảm ✓, tại chỗ ✓) mà vẫn là lựa chọn chậm nhất trong thực tế, vì bảng đó không có cột "thân thiện cache" — cột quyết định trên phần cứng thật. Một danh sách ưu điểm không thay được một phép đo.

Điều thứ hai: khi hai thứ cùng độ phức tạp mà khác tốc độ, và khác biệt lớn dần theo kích thước, hãy nghi ngờ cache trước tiên. Sự tăng dần của tỉ số là dấu hiệu chẩn đoán mạnh: một khác biệt về hằng số thuần (như số phép so sánh) cho tỉ số cố định; một khác biệt về số lần chạm bộ nhớ cho tỉ số tăng khi vượt cache. Biết đọc dấu hiệu này giúp bạn tối ưu đúng chỗ — sửa mẫu truy cập, không phải cắt vài phép tính.

Và bản thân heap là cấu trúc bạn dùng mỗi ngày, chỉ là không phải để sắp xếp: Java PriorityQueue, Python heapq, C++ priority_queue, Go container/heap đều là binary heap — cùng cái sift-down nhảy-cóc phá cache ở đây, nên chúng tuyệt cho "lấy phần tử nhỏ nhất/lớn nhất tiếp theo" (hàng đợi công việc, Dijkstra, gộp k-đường) nhưng không phải cách nhanh nhất để sắp cả một mảng. Còn khi cần sắp thật, không ai gọi thẳng heapsort — họ gọi sort() của thư viện, và heapsort ẩn bên trong như tầng bảo hiểm của introsort. Mẫu số chung: cùng một ký hiệu tiệm cận có thể che một khác biệt gấp đôi; một danh sách ưu điểm lý thuyết không có cột "thân thiện cache", mà trên phần cứng thật đó lại là cột quyết định — nên "hoàn hảo trên giấy" vẫn phải trả lời câu hỏi mà đồng hồ và cache đặt ra.

Muốn tự thấy thì nhìn vào mẫu truy cập bộ nhớ của một thuật toán, và hỏi: nó đọc dữ liệu tuần tự (ô kề ô) hay nhảy cóc (mỗi bước tới một địa chỉ xa)? Heapsort là ví dụ sách giáo khoa của kiểu nhảy cóc — chỉ số nhân đôi mỗi tầng — nên dù đẹp về lý thuyết, nó thua trên cache. Cách thử nhanh nếu bạn nghi một thuật toán chậm vì cache: đo nó ở vài kích thước tăng dần và tính tỉ số so với một thuật toán tuần tự cùng độ phức tạp. Nếu tỉ số đứng yên, khác biệt chỉ là hằng số; nếu tỉ số phình ra khi dữ liệu vượt cỡ cache của máy bạn, bạn vừa bắt được một vấn đề cache — và đó, chứ không phải số phép toán, là thứ đáng sửa.