algorithm - 本当に大きなデータのための互いに素な集合

Question

本当に大きなデータ (2 ^ 32 を超える要素と 2 ^ 32 を超えるペアを結合するなど) 用の拡張された Disjoint-sets アルゴリズムはありますか?

明らかに最大の問題は、そのような大きな配列を作成できないことです。そのため、タスクを達成するためのより良いアルゴリズムまたはより良いデータ構造があるかどうか疑問に思っていますか?

Answer 1

非常に大きなデータを処理する 1 つの方法は、外部メモリで実行することです。http://terrain.cs.duke.edu/pubs/union-find.pdf (I/O-Efficient Batched Union-Find and its Applications to Terrain Analysis) には、かなり複雑な一連の呼び出しで構成される理論アルゴリズムが含まれています。他のバッチ処理されたアルゴリズム、および (セクション 3) 漸近的に効率的ではないが、実用的であるかのように見える自己完結型の再帰アルゴリズム。