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 hẹn 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ó nghe gần như hoàn hảo. Bài này đ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 ở đó.
Đo: 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ó.
Một lần tôi đo hớ: "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. Bài học đo lường: 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ủ đề của một bài sau) 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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là con số mang theo: ba thuật toán sắp xếp cùng O(n log n) không chạy như nhau — heapsort chậm nhất, từ 1,43 lần tới 2,37 lần quicksort, và tỉ số tăng theo n vì sift-down nhảy khắp mảng phá cache (dù nó cũng làm ~1,7 lần số so sánh); giá trị của heapsort không phải tốc độ mà là bảo đảm O(n log n) + tại chỗ, làm lưới an toàn. Cùng một ký hiệu tiệm cận có thể che một khác biệt gấp đôi, và một thuật toán "hoàn hảo trên giấy" vẫn phải trả lời câu hỏi phần cứng đặt ra.
Thử ba mươi giây
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.
