4

等価クラスの要素をグループ化するデータ構造を実装する必要があります。

API:

interface Grouper<T>{
  void same(T l, T r);
  Set<EquivalenceClass<T>> equivalenceClasses();
}

interface EquivalenceClass<T>{
    Set<T> members();
}

たとえば、グループ化は次のように動作します。

Grouper g;
g.same(a, b);
g.equivalenceClasses() -> [[a,b]]

g.same(b, a);
g.equivalenceClasses() -> [[a,b]]

g.same(b, c);
g.equivalenceClasses() -> [[a,b,c]]

g.same(d, e);
g.equivalenceClasses() -> [[a,b,c], [d,e]]

g.same(c, d);
g.equivalenceClasses() -> [[a,b,c,d]]

最大 1,000 万エントリまで機能する実装を探しています。それを埋めて等価クラスを一度取得するように最適化する必要があります。

4

3 に答える 3

5

Union-Findを見てください。和集合（「同じ」）はで自明に行うことができ、いくつかの最適化O(log N)で効果的に行うことができます。O(1)「equivalenceClasses」はO(N)、とにかくすべてを訪問するコストです。

于 2010-12-09T16:54:12.720 に答える
1

等価クラスを 1 回だけクエリする場合、最適な解決策は、要素に対して無向グラフを作成することです。各同値は 2 つのアイテム間の無向辺であり、同値クラスは連結成分に対応します。正しく行えば、時間と空間の複雑さはどちらも線形になります。

または、Union-Find データ構造を使用することもできます。これにより、ほぼ線形の時間計算量が得られます。また、すべての複雑さがデータ構造にカプセル化されているため、より単純であると見なすこともできます。Union-Find が線形でない理由は、クラスが成長している間に効率的なクエリをサポートすることに帰着します。

于 2010-12-09T17:54:32.630 に答える
0

Union-findは、合計実行時間のみを気にする限り、問題に最適なデータ構造です（一部の操作は遅い場合がありますが、すべての操作の合計コストはほぼ線形であることが保証されます）。ただし、各セットのメンバーの列挙は、通常、教科書のunion-findのプレーンバージョンではサポートされていません。名前が示すように、union-findは通常、union（つまり、same）とfindのみをサポートします。これは、同じセット内の要素でfindを呼び出すことによって返される識別子と同じであることが保証された識別子を返します。各セットのメンバーを列挙する必要がある場合は、セットを表す各ツリーをトラバースできるように、たとえば子ポインターを追加できるように、自分で実装する必要がある場合があります。

これを自分で実装している場合は、操作ごとの償却O（lg n）時間を達成するために、完全なユニオン検索データ構造を実装する必要はありません。基本的に、この「ライト」バージョンのunion-findでは、各セットは、2つのノードが同じリストに属しているかどうかをテストするために使用できるセット識別子ノードを指す、各ノード内の追加のポインターを持つ単一リンクリストになります。メソッドが実行されると、same小さい方のリストを大きい方のリストに追加し、小さい方のリストの要素のセット識別子を更新できます。same要素は、最大でO（lg n）回の操作に関与する小さなリストのメンバーになることができるため、合計コストは要素あたり最大でO（lg n）です。

于 2010-12-09T19:18:53.743 に答える