Union-Find (hay Disjoint Set Union — DSU) là một cấu trúc dữ liệu nhỏ đến mức khó tin nó lại quan trọng: nó chỉ theo dõi các nhóm phần tử, hỗ trợ hai thao tác — hợp hai nhóm lại (union), và hỏi hai phần tử có cùng nhóm không (find). Nó là xương sống của thuật toán tìm cây khung nhỏ nhất, phát hiện chu trình, gộp thành phần liên thông. Và nó nổi tiếng với một tuyên bố gần như huyền thoại: mỗi thao tác chạy trong "gần như O(1)". Bài này đo xem "gần như O(1)" đó là thật hay chỉ là cách nói đẹp — và phát hiện rằng nó vừa mong manh hơn ta tưởng (dễ hỏng), vừa đẹp hơn ta tưởng (khi làm đúng).
Cấu trúc rừng cây cha, và cái bẫy chuỗi dài
Union-Find biểu diễn mỗi nhóm bằng một cây: mỗi phần tử trỏ tới một "cha", và đỉnh gốc (trỏ tới chính nó) đại diện cho cả nhóm. find(x) đi theo con trỏ cha lên tới gốc; hai phần tử cùng nhóm khi và chỉ khi cùng gốc. union(a, b) gắn gốc của nhóm này làm con của gốc nhóm kia. Đơn giản tới mức có vẻ không thể sai.
Nhưng cái đơn giản đó giấu một cái bẫy. Nếu các phép union nối các cây theo thứ tự xấu, cây có thể thoái hóa thành một chuỗi dài — mỗi phần tử là cha của phần tử tiếp theo, thành một danh sách liên kết trá hình. Khi đó find phải đi hết chuỗi, O(n) mỗi lần. Đây chính là cái tôi vào bài để đo, vì "gần O(1)" và "O(n)" là hai thế giới khác nhau.
Đo: naive là O(n), tối ưu là gần O(1)
Tôi cài bốn biến thể và cho mỗi cái xử lý cùng một kịch bản: n phần tử, hợp tuần tự union(0,1), union(1,2), ... (một thứ tự khiến bản naive dựng ra chuỗi dài), rồi find mọi phần tử. Đo độ dài đường find trung bình (số bước đi lên cha) và thời gian.
biến thể (n=20 000) đường find TB thời gian find-all
naive (không tối ưu) 9 999,5 88,07 ms
chỉ hợp theo cỡ 1,0 0,03 ms
chỉ nén đường 2,0 0,03 ms
cả hai 1,0 0,03 ms
Bản naive đúng là thảm họa: đường find trung bình 9 999,5 — bằng đúng n/2, dấu vết của một cái chuỗi dài n — và find hết mọi phần tử mất 88 mili giây. Đây là bằng chứng cứng cho điều đầu tiên: find của union-find KHÔNG tự nhiên là O(1); không tối ưu thì nó là O(n), chậm như duyệt một danh sách liên kết. Đây là chỗ tôi đã hớ — tôi vẫn nghĩ về union-find như "cấu trúc O(1)" mà quên rằng cái O(1) đó phải được mua bằng tối ưu.
Và hai tối ưu mua nó là hai ý tưởng nhỏ đến bất ngờ. Hợp theo cỡ: khi union, luôn gắn cây thấp/nhỏ vào cây cao/lớn, để cây không cao lên vô lối. Nén đường (path compression): mỗi lần find đi từ một phần tử lên gốc, trỏ thẳng mọi node trên đường đó vào gốc luôn — lần sau chúng chỉ cách gốc một bước. Chỉ cần một trong hai đã kéo đường find từ 9 999 xuống 1–2 và làm find nhanh hơn khoảng 3 000 lần. Trên kịch bản này một tối ưu là đủ; nhưng lý do các thư viện luôn dùng cả hai là để có bảo đảm lý thuyết vững cho mọi thứ tự đầu vào, không chỉ những ca may mắn.
Cái đẹp: đường find phẳng lì ở 10 triệu phần tử
Tuyên bố "gần O(1)" của union-find thực ra là một kết quả toán học sâu: với cả hai tối ưu, chi phí khấu hao mỗi thao tác là α(n) — hàm nghịch Ackermann, một hàm tăng chậm đến kinh ngạc, nhỏ hơn 5 với mọi n bạn có thể gặp trong vũ trụ này (kể cả n bằng số nguyên tử). Nghe trừu tượng, nên tôi đo nó thành con số cụ thể: chạy biến thể "cả hai" với union ngẫu nhiên ở các quy mô tăng dần, đo đường find trung bình:
n = 100 000 : đường find TB 1,01
n = 1 000 000 : đường find TB 1,01 (6,6 ns/find)
n = 10 000 000 : đường find TB 1,01 (11 ns/find)
Đường find trung bình phẳng lì ở 1,01 khi n tăng gấp trăm lần. Một thao tác find, dù cấu trúc có mười triệu phần tử, trung bình chỉ chạm khoảng một node. Con số 1,01 không đổi đó chính là α(n) hiện hình — bằng chứng thực nghiệm cho một trong những kết quả đẹp nhất của phân tích khấu hao (chủ đề một bài sau sẽ đào sâu). "Gần O(1)" không phải cách nói hoa mỹ; nó là sự thật đo được, và nó phẳng đến mức trong thực tế bạn có thể coi mỗi thao tác union-find là hằng số mà không sai chút nào.
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 union-find, đừng quên hai tối ưu — chúng ngắn (mỗi cái vài dòng) nhưng là ranh giới giữa O(n) và gần O(1). Một union-find không nén đường sẽ chạy tốt trên test nhỏ rồi bò như rùa trên dữ liệu thật với thứ tự union không may. Đặc biệt nén đường chỉ là thêm một vòng lặp nhỏ trong find, gần như miễn phí để viết mà lợi ích khổng lồ; hầu như không có lý do gì để bỏ nó.
Hệ quả thứ hai, về cách đọc độ phức tạp: "O(1) khấu hao" và "gần O(1)" là những lời hứa có điều kiện, cần đo để tin và để biết điều kiện. Union-find gần O(1) nhờ hai tối ưu; bỏ đi là mất. Rất nhiều cấu trúc "O(1) khấu hao" khác (bảng băm, mảng động) cũng vậy — cái O(1) đến từ một cơ chế cụ thể, và hiểu cơ chế đó là hiểu khi nào lời hứa còn giữ. Đo là cách nhanh nhất để phân biệt một O(1) thật với một O(1) trên giấy.
Hệ quả thứ ba là con số mang theo: find của union-find không tự nhiên O(1) — naive thoái hóa thành chuỗi O(n) (đường find 9999 = n/2, 88ms); hai tối ưu (hợp theo cỡ + nén đường) kéo nó xuống ~1 (nhanh 3000 lần), và với cả hai, đường find trung bình phẳng lì ở 1,01 ngay cả với 10 triệu phần tử — α(n) < 5 với mọi n, gần O(1) là một sự thật đo được. Một cấu trúc tí hon với hai dòng tối ưu cho bạn thao tác nhóm gần như tức thời ở bất kỳ quy mô nào — nhưng chỉ khi bạn nhớ viết hai dòng đó.
Thử ba mươi giây
Nếu bạn có một đoạn code union-find (tự viết hoặc mượn), mở hàm find ra và tìm hai thứ. Thứ nhất, trong find: sau khi tìm được gốc, nó có trỏ các node trên đường vào gốc luôn không (nén đường), hay chỉ trả về gốc rồi thôi? Thứ hai, trong union: nó có so sánh cỡ/hạng hai cây để gắn cây nhỏ vào cây lớn không, hay gắn bừa? Nếu thiếu một trong hai, cấu trúc của bạn có thể thoái hóa trên đầu vào xấu. Sửa mất vài phút, và bạn có thể tự đo: dựng một chuỗi union tuần tự vài chục nghìn phần tử, đo thời gian find trước và sau khi thêm tối ưu — bạn sẽ thấy chính con số 3 000 lần đó, và hiểu vì sao "gần O(1)" phải được mua chứ không tự có.
