Quicksort mang tiếng là thuật toán sắp xếp nhanh nhất trong thực tế, và đúng là như vậy — khi nó chạy đúng ca trung bình. Nhưng "quicksort là O(n log n)" là một trong những nửa-sự-thật nguy hiểm nhất trong lập trình, vì cái nửa còn lại — trường hợp xấu O(n²) — không nấp ở một đầu vào kỳ dị hiếm gặp, mà nấp ở đúng đầu vào bạn ít test nhất: một mảng đã được sắp sẵn. Bài này cài quicksort thật, đo nó vinh quang trên dữ liệu ngẫu nhiên rồi sụp đổ trên dữ liệu đã sắp, và đo cả cách cứu nó.
Quicksort đứng hay ngã ở việc chọn pivot
Quicksort là chia để trị: chọn một phần tử làm pivot, phân hoạch (partition) mảng thành hai phần — những phần tử nhỏ hơn pivot dồn về trái, lớn hơn dồn về phải — rồi đệ quy sắp hai phần đó. Nó có những phẩm chất khiến nó thắng trong thực tế: sắp tại chỗ (in-place, không cần mảng phụ như merge sort), hằng số nhỏ, và bước phân hoạch chỉ là quét tuyến tính qua mảng nên rất thân thiện cache — đúng cái mà các bài trước về cache cho thấy là quyết định trên phần cứng thật.
Nhưng toàn bộ hiệu năng của quicksort treo trên một câu hỏi: pivot chia mảng có cân không? Nếu pivot rơi gần giữa, hai phần bằng nhau, cây đệ quy sâu log n tầng, tổng công là O(n log n). Nếu pivot luôn rơi vào cực trị (nhỏ nhất hoặc lớn nhất), một phần rỗng còn phần kia có n-1 phần tử — cây đệ quy sâu n tầng, mỗi tầng quét gần cả mảng, tổng công thành O(n²). Cùng một thuật toán, hai số phận, chỉ khác ở pivot. Câu hỏi thực tế: chọn pivot thế nào để rơi vào ngã nào, và đầu vào của bạn ảnh hưởng ra sao? Tôi đo.
Đo: cùng thuật toán, nhanh 45ms hay chậm 3,5 giây
Tôi cài quicksort với cách chọn pivot ngây thơ nhất — lấy phần tử cuối làm pivot (phân hoạch Lomuto) — rồi đo trên hai loại đầu vào.
Trên một triệu số ngẫu nhiên: 45 mili giây, trung bình 25 phép so sánh mỗi phần tử (đúng cỡ 1,4·log n), cây đệ quy sâu 13 tầng. Nhanh, gọn, đúng như danh tiếng.
Trên mảng đã sắp sẵn với cùng pivot phần tử cuối, tôi đo ở nhiều kích thước để nhìn dáng đường cong:
n thời gian so sánh / phần tử
20 nghìn 53 ms 9 999
40 nghìn 213 ms 19 999 (thời gian gấp 4)
80 nghìn 868 ms 39 999 (gấp 4)
160 nghìn 3 528 ms 79 999 (gấp 4)
Đây là chữ ký không thể nhầm của O(n²): mỗi khi n gấp đôi, thời gian gấp bốn. Và số so sánh mỗi phần tử đúng bằng n/2 — nghĩa là mỗi phần tử phải so với gần nửa mảng. Ngoại suy đường cong này tới một triệu phần tử thì quicksort "nhanh" của tôi sẽ mất khoảng 135 giây thay vì 45 mili giây — chậm hơn ba nghìn lần, trên cùng dữ liệu chỉ khác thứ tự. Nhưng con số thời gian chưa phải điều tệ nhất.
Một lần tôi đo hớ: ca ít test nhất lại là ca chết
Tôi vào bài với niềm tin phổ biến và lười: "quicksort là O(n log n), cứ dùng, pivot nào cũng được" — và lấy phần tử cuối cho tiện. Đây chính xác là cái bẫy, vì pivot phần tử cuối gặp mảng đã sắp là thảm họa: phần tử cuối của một mảng đã sắp luôn là phần tử lớn nhất, nên phân hoạch dồn tất cả về một bên, và điều đó lặp lại ở mọi tầng. Mảng đã sắp không phải đầu vào hiếm — nó là đầu vào thường gặp nhất: dữ liệu vừa lấy từ cơ sở dữ liệu có ORDER BY, một danh sách đã sắp bị sắp lại, dữ liệu gần như có thứ tự sẵn. Và nó cũng là đầu vào người ta quên test nhất, vì test thường ném dữ liệu ngẫu nhiên vào. Cái ta ít nhìn tới nhất lại là cái giết chương trình.
Và nó giết theo hai cách, không chỉ một. Cách thứ nhất là O(n²) chậm đã đo ở trên. Cách thứ hai âm hiểm hơn: đệ quy sâu. Vì cây đệ quy suy biến thành một chuỗi dài n tầng, chương trình gọi hàm lồng n lần — và tôi đo được với mảng đã sắp 5.000 phần tử, độ sâu đệ quy chạm đúng 4.999. Ở kích thước thật (hàng trăm nghìn phần tử), n tầng đệ quy sẽ tràn ngăn xếp và chương trình sập hẳn (segmentation fault), không phải chỉ chậm. Trong khi đó trên dữ liệu ngẫu nhiên, độ sâu chỉ 26 tầng (~log n) — an toàn. Một lỗi vừa làm chậm ba nghìn lần vừa có thể làm sập, và nó chỉ hiện ra khi ai đó đưa vào dữ liệu đã sắp mà bạn chưa từng test.
Cách cứu thì rẻ và dứt khoát: đừng để pivot phụ thuộc vào vị trí, hãy để nó phụ thuộc vào giá trị hoặc ngẫu nhiên. Tôi đổi sang trung vị-của-ba (lấy trung vị của phần tử đầu, giữa, cuối làm pivot). Đo lại trên mảng đã sắp một triệu phần tử: 9 mili giây, độ sâu 19, kết quả đúng. Nhanh hơn cả ca ngẫu nhiên (45 ms), vì mảng đã sắp có bố cục cache hoàn hảo và trung vị-của-ba tìm được pivot gần như hoàn hảo trên dữ liệu đã sắp. Bài học đo lường: con số trung bình đẹp che giấu một trường hợp xấu có thật, và trường hợp xấu đó thường nấp ở đầu vào có cấu trúc mà bạn quên test. Đừng hỏi "thuật toán này O gì?"; hãy hỏi "đầu vào của tôi có cấu trúc gì khiến trường hợp xấu bật ra?".
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, rất cụ thể: nếu bạn tự cài quicksort, đừng bao giờ dùng pivot cố định theo vị trí (đầu hay cuối). Luôn ngẫu nhiên hóa pivot, hoặc dùng trung vị-của-ba. Đây không phải chuyện tinh chỉnh hiệu năng — đó là chuyện đúng-sai, vì pivot theo vị trí biến một thuật toán O(n log n) thành một quả bom O(n²) và tràn ngăn xếp, chờ đúng dữ liệu đã sắp để nổ. Chi phí ngẫu nhiên hóa gần như bằng không; cái nó mua là sự an toàn trước ca xấu.
Hệ quả thứ hai: test thuật toán bằng đầu vào có cấu trúc, không chỉ ngẫu nhiên. Dữ liệu ngẫu nhiên là ca dễ; nó qua được mọi lỗi ẩn ở ca xấu. Muốn bắt những quả bom như thế này, phải test với mảng đã sắp, mảng sắp ngược, mảng toàn phần tử giống nhau, mảng gần-sắp — chính những đầu vào có cấu trúc mà thực tế hay tạo ra. Một bộ test chỉ có dữ liệu ngẫu nhiên là một bộ test mù trước đúng loại lỗi nguy hiểm nhất.
Hệ quả thứ ba là bài học đo lường mang theo. Con số cần nhớ: quicksort pivot phần tử cuối chạy 45ms trên 1 triệu số ngẫu nhiên nhưng thành O(n²) trên mảng đã sắp (thời gian gấp 4 mỗi khi n gấp đôi, ~3000 lần chậm hơn ở 1 triệu) và đệ quy sâu n tầng tràn ngăn xếp; trung vị-của-3 đưa mảng đã sắp về 9ms, sâu 19 tầng. Danh tiếng "O(n log n)" của quicksort là có điều kiện, và điều kiện đó — pivot cân — là thứ bạn phải chủ động bảo đảm, không phải thứ tự nhiên có.
Thử ba mươi giây
Mở đoạn code sắp xếp mà bạn (hay một thư viện ít tên tuổi bạn đang dùng) tự cài, và tìm dòng chọn pivot. Nếu nó viết đại loại pivot = a[hi] hay pivot = a[lo] — pivot theo vị trí cố định — thì bạn đang cầm một quả bom O(n²). Thử ngay: tạo một mảng đã sắp tăng dần vài trăm nghìn phần tử và ném vào nó. Nếu chương trình treo lâu bất thường hoặc sập vì tràn ngăn xếp, bạn vừa xác nhận quả bom. Cách gỡ mất một phút: đổi dòng đó thành lấy pivot ngẫu nhiên, hoặc trung vị của đầu-giữa-cuối. Và từ nay, mỗi khi đánh giá một thuật toán "nhanh", hãy hỏi thêm một câu trước khi tin: nhanh trên dữ liệu nào, và cái gì làm nó chậm?
