Cấu trúc 'gần như O(1)' này tụt thành O(n) nếu bạn quên đúng hai dòng

Hỏi hai người trong một công ty lớn "anh chị có chung sếp tổng không", có hai cách trả lời. Cách tệ: mỗi người lần lượt hỏi lên sếp trực tiếp, rồi sếp của sếp, leo mãi tới đỉnh — nếu sơ đồ tổ chức dài lê thê thì leo rã chân. Cách khôn: ai đã một lần leo tới đỉnh thì ghi luôn "sếp tổng của tôi là ông X" cạnh tên mình, lần sau hỏi cái là biết ngay. Union-Find (hay Disjoint Set Union — DSU) chính là bài toán đó: một cấu trúc nhỏ đến khó tin, chỉ theo dõi các nhóm phần tử với hai thao tác — hợp hai nhóm (union) và hỏi hai phần tử có cùng nhóm không (find). Nó là xương sống của 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ổi tiếng với tuyên bố gần như huyền thoại: mỗi thao tác chạy "gần như O(1)". Tôi đo xem điều đó là thật hay chỉ là cách nói đẹp — và thấy nó vừa mong manh hơn ta tưởng, vừa đẹp hơn ta tưở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.

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 (đúng cái mẹo "ghi luôn sếp tổng cạnh tên" ở đầu bài). 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. "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ề đến code hằng ngày

Điều đầ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ó.

Điều 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ữ.

Và bạn dùng union-find nhiều hơn tưởng, thường là gián tiếp. Thuật toán Kruskal tìm cây khung nhỏ nhất (nền của quy hoạch mạng, phân cụm ảnh) đứng thẳng trên union-find; các trình biên dịch dùng nó cho phân tích kiểu (thuật toán hợp nhất Hindley-Milner của Haskell/ML là union-find trên các biến kiểu); và trong xử lý dữ liệu lớn, gộp các bản ghi trùng (record linkage, "cùng một người dùng qua nhiều email") chính là bài toán thành phần liên thông — Spark có GraphFrames.connectedComponents làm đúng việc này ở quy mô cụm máy. Ở tầng cơ sở dữ liệu thì WITH RECURSIVE mô phỏng được gộp nhóm nhưng chậm hơn nhiều một union-find trong bộ nhớ — nên việc gộp cụm lớn thường kéo dữ liệu ra ngoài xử lý. Mẫu số chung: 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 đó, và "gần O(1)" là thứ phải mua chứ không tự có.

Muốn tự kiểm thì nếu 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ó.