"Ngẫu nhiên" nghe như thứ ta muốn tránh trong một chương trình: nó gợi đến kém tin cậy, khó lường, khó gỡ lỗi. Nhưng có một họ giải thuật cố tình gieo ngẫu nhiên vào chính mình — và làm vậy để chạy nhanh hơn và đáng tin hơn, chứ không phải ngược lại. Nghe nghịch lý, nên bài này đo hai ví dụ bằng đồng hồ và bộ đếm: quicksort chọn pivot ngẫu nhiên, và skip list cân bằng bằng cách tung đồng xu.
Ngẫu nhiên hóa để làm gì
Một giải thuật ngẫu nhiên hóa (randomized) đưa một nguồn may rủi có kiểm soát vào quyết định của nó. Có hai lý do rất khác nhau để làm điều đó, và bài này chạm cả hai.
Thứ nhất: chống đầu vào đối nghịch. Nhiều giải thuật có trường hợp tệ nhất phụ thuộc hình dạng dữ liệu. Nếu quy tắc là cố định, một kẻ tấn công (hay đơn giản là một khách hàng vô tình) có thể gửi đúng cái dữ liệu chạm trường hợp tệ nhất, mỗi lần. Ngẫu nhiên hóa làm quy tắc không đoán trước được, nên không đầu vào cố định nào ép được trường hợp tệ nhất.
Thứ hai: đơn giản mà vẫn nhanh. Vài cấu trúc dữ liệu cân bằng (như cây AVL) đạt O(log n) bằng logic xoay và tái cân bằng khá rối. Ngẫu nhiên hóa cho một lối tắt: để may rủi lo việc cân bằng, đổi lấy code ngắn hơn nhiều mà hiệu năng kỳ vọng vẫn tốt như vậy.
Đo: pivot ngẫu nhiên biến thảm họa thành O(n log n)
Quicksort chia mảng quanh một phần tử gọi là pivot. Chất lượng của nó phụ thuộc pivot chia mảng cân tới đâu: chia đôi đều thì O(n log n), chia lệch hết cỡ thì O(n²). Nếu ta luôn lấy pivot cố định — phần tử đầu — thì một mảng đã sắp xếp là ác mộng: mỗi lần chia tách ra một bên rỗng và một bên gần đủ, đệ quy n tầng. Tôi cho cả hai chiến lược sắp xếp cùng một mảng đã sắp sẵn (0, 1, 2, ..., n−1) và đếm số phép so sánh:
Đầu vào ĐÃ SẮP XẾP, số phép so sánh của quicksort:
n | pivot CỐ ĐỊNH | pivot NGẪU NHIÊN
4.000 | 7.998.000 | 55.057
8.000 | 31.996.000 | 122.057
16.000 | 127.992.000 | 268.682
32.000 | 511.984.000 | 549.848
64.000 | 2.047.968.000 | 1.343.815
Nhìn cột pivot cố định: mỗi lần n gấp đôi, số so sánh gấp bốn (8 triệu → 32 triệu → 128 triệu...) — đúng dấu hiệu O(n²). Ở n=64.000 nó làm hơn hai tỉ phép so sánh, mất 901 ms. Cột pivot ngẫu nhiên tăng gần tuyến tính (thực ra ~1,4·n·log n), ở n=64.000 chỉ 1,3 triệu phép so sánh, mất 1,08 ms. Chênh lệch: ít hơn 1524 lần số so sánh, nhanh hơn khoảng 830 lần — cùng thuật toán, cùng dữ liệu, chỉ khác cách chọn pivot.
Một lần tôi đo hớ: ngẫu nhiên là an toàn, không phải rủi ro
Tôi vào bài với định kiến phổ biến: "thêm ngẫu nhiên vào thì kết quả khó lường hơn, kém tin cậy hơn". Con số ở trên nói ngược lại, và chỗ đo hớ nằm ở chỗ hiểu ngược nghĩa của rủi ro.
Bản pivot cố định mới là bản rủi ro, dù nó hoàn toàn tất định. Nó nhanh trên dữ liệu ngẫu nhiên, nhưng có một lớp đầu vào — dữ liệu đã sắp xếp hay gần sắp xếp — khiến nó sập xuống O(n²). Và đây mới là điều nguy: dữ liệu đã sắp xếp cực kỳ phổ biến trong thực tế (kết quả từ một truy vấn ORDER BY, một danh sách đã lọc, dữ liệu theo thời gian). Tệ hơn, nếu quy tắc chọn pivot công khai, một kẻ tấn công chỉ cần gửi đúng dữ liệu sắp sẵn để ép dịch vụ của bạn tốn CPU gấp nghìn lần — một dạng tấn công từ chối dịch vụ bằng độ phức tạp.
Bản pivot ngẫu nhiên loại bỏ hẳn lớp rủi ro đó. Vì pivot được chọn ngẫu nhiên tại thời điểm chạy, không có đầu vào cố định nào ép được trường hợp tệ nhất — kẻ tấn công không thể đoán pivot sẽ rơi vào đâu. Nó không phải là bỏ trường hợp tệ nhất đi, mà là đổi trục của nó: từ "tệ nhất theo đầu vào" (mà đối thủ điều khiển được) thành "tệ nhất theo xui xẻo" (mà không ai điều khiển được, và xác suất nhỏ tới mức bỏ qua được — xác suất một mảng lớn liên tục chọn trúng pivot tệ nhất là nhỏ đến mức thiên văn). Ngẫu nhiên hóa ở đây chính là tăng độ tin cậy: nó biến một giải thuật có gót chân Achilles thành một giải thuật không có đầu vào nào là kẻ thù. Đó là an toàn, không phải rủi ro.
Skip list: cân bằng bằng tung đồng xu
Ví dụ thứ hai cho thấy mặt "đơn giản mà nhanh". Skip list là một danh sách liên kết có nhiều tầng: tầng đáy chứa mọi phần tử theo thứ tự, mỗi tầng trên là một "đường cao tốc" bỏ qua bớt phần tử để nhảy nhanh. Câu hỏi: mỗi nút nên có mặt ở bao nhiêu tầng? Cây AVL trả lời bằng cách đo chiều cao và xoay lại cho cân — logic rối. Skip list trả lời bằng cách tung đồng xu: mỗi nút bắt đầu ở tầng 1, rồi cứ tung đồng xu, còn ngửa thì lên thêm một tầng. Thế thôi. Không đo, không xoay, không tái cân bằng.
Điều bất ngờ là may rủi tự lo được việc cân bằng. Tôi chèn n khóa rồi đo chiều cao thực tế và số so sánh trung bình khi tìm:
Skip list (cân bằng bằng tung đồng xu):
n= 1.000 : chiều cao 10 tầng (log2 n = 10) | tìm ~19,4 so sánh
n= 10.000 : chiều cao 13 tầng (log2 n = 13) | tìm ~23,8 so sánh
n= 100.000 : chiều cao 17 tầng (log2 n = 17) | tìm ~33,4 so sánh
n=1.000.000 : chiều cao 22 tầng (log2 n = 20) | tìm ~42,0 so sánh
Chiều cao bám sát log2(n), và số so sánh khi tìm tăng đều theo log n (mỗi lần n gấp mười, số so sánh cộng thêm một hằng số nhỏ) — đúng dáng O(log n). Tất cả không một phép xoay nào. Xác suất trung bình làm cho một nửa số nút lên tầng 2, một phần tư lên tầng 3, và cứ thế — chính cấu trúc hình học ấy tạo ra các đường cao tốc thưa dần đều đặn, y như một cây cân bằng, nhưng đến từ đồng xu chứ không từ logic tái cân bằng. Đây là chỗ đo hớ thứ hai của tôi tan biến: tôi tưởng "cân bằng" bắt buộc phải là logic phức tạp, hóa ra một quy tắc ngẫu nhiên ba dòng cho kết quả tương đương về bậc độ phức tạp.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên rất thực tế: nếu bạn tự viết quicksort (hay quickselect), đừng dùng pivot cố định. Chọn pivot ngẫu nhiên, hoặc median-of-three, để không lớp đầu vào nào — nhất là dữ liệu đã sắp xếp, thứ xuất hiện khắp nơi — ép được O(n²). Đây chính là lý do các thư viện chuẩn không dùng quicksort pivot cố định trần: nhiều bản dùng introsort (chuyển sang heapsort khi đệ quy quá sâu) hoặc pivot ngẫu nhiên/median, đúng để chặn kịch bản tấn công độ phức tạp này.
Hệ quả thứ hai vượt ra ngoài sắp xếp: ngẫu nhiên hóa là một công cụ phòng thủ. Bất cứ chỗ nào hiệu năng phụ thuộc hình dạng đầu vào mà đầu vào lại đến từ bên ngoài, một hạt giống ngẫu nhiên bí mật sẽ ngắt khả năng dự đoán của đối thủ. Ví dụ kinh điển ngoài bài này: bảng băm dùng khóa băm ngẫu nhiên hóa (SipHash) để kẻ tấn công không thể cố tình dồn mọi khóa vào một xô — cùng một ý tưởng "đổi tệ-nhất-theo-đầu-vào lấy tệ-nhất-theo-xui-xẻo".
Hệ quả thứ ba là về sự đánh đổi trung thực: ngẫu nhiên hóa đổi đảm bảo tuyệt đối lấy đảm bảo kỳ vọng — và trong hầu hết trường hợp đó là món hời. Skip list và quicksort ngẫu nhiên về lý thuyết vẫn có trường hợp tệ nhất O(n²) hay O(n) chiều cao; chỉ là xác suất chạm nó nhỏ đến mức không đáng lo, và không ai ép được. Nếu bạn cần một đảm bảo cứng cho trường hợp tệ nhất (hệ thống thời gian thực nghiêm ngặt), hãy chọn cấu trúc tất định như cây AVL hay heapsort. Còn lại, code ngắn hơn cộng miễn nhiễm đầu vào đối nghịch thường đáng giá hơn một đảm bảo cứng mà bạn hiếm khi cần. Con số mang theo: pivot ngẫu nhiên trên mảng đã sắp xếp làm ít hơn 1524 lần số so sánh so với pivot cố định (1,3 triệu so với 2,05 tỉ ở n=64.000), và skip list đạt chiều cao ~log2(n) chỉ bằng tung đồng xu, không một phép xoay — ngẫu nhiên hóa là cách đổi "tệ nhất do kẻ khác chọn" lấy "tệ nhất do xui xẻo", một sự đánh đổi gần như luôn có lợi.
Thử ba mươi giây
Lấy hàm sắp xếp trong ngôn ngữ bạn hay dùng và thử cho nó một mảng đã sắp xếp sẵn cỡ vài trăm nghìn phần tử, đo thời gian; rồi thử một mảng xáo trộn cùng cỡ. Nếu hai thời gian gần bằng nhau, thư viện của bạn đã chống đầu vào đối nghịch (pivot ngẫu nhiên/median, hoặc introsort) — yên tâm. Còn nếu bạn tự viết một quicksort đâu đó với pivot = a[0], hãy tự tay chạy thử nó trên mảng đã sắp xếp: bạn sẽ thấy đồng hồ nhảy vọt, và hiểu vì sao một dòng pivot = a[lo + rand()%(hi-lo+1)] là một trong những dòng phòng thủ rẻ nhất bạn có thể viết.
