7

ツリーのノードに同値類を構築するための優れたデータ構造を探しています。理想的な構造では、次の操作は高速（必要に応じてO（1）/ O（n））で簡単（ミステリーコードの段落なし）である必要があります。

  • （A）根から木を歩きます。各ノードで->子遷移は子ノードのすべての同等のバージョンを列挙します
  • （B）2つの同値類をマージする
  • （C）既存のノード（子）およびその他のデータのリストから新しいノードを作成します
  • （D）ノードと構造的に同等のノードを見つけて（つまり、同じ数の子を持ち、対応する子は同じ同値類に属し、それらの「他のデータ」は等しい）、新しい（または新しく変更された）ノードを配置できるようにします正しい同値類（マージを介して）

これまで私が検討した（これらのいくつかは組み合わせて使用​​できる）：

  • 子がノードではなくノードのコレクションへの参照であるパフェ。（A）高速、（B）マージされたコレクションを指すようにツリーをウォークしてノードを更新する必要がある、（C）新しいノードの各子を含むコレクションを見つける必要がある、（D）ツリーをウォークする必要がある
  • ノードの特性によってノードのハッシュを維持します。これにより、（D）ははるかに高速になりますが、（B）は遅くなります（等価クラスがマージされたときにハッシュを更新する必要があるため）
  • ノードをまとめて循環リンクリストにまとめます。（A）は高速です、（B）は高速ですが、循環リストの「マージ」部分が実際にリストを分割するという事実のために、（C）は高速であり、（D）はツリーを歩く必要があります
  • 上記と同様ですが、各ノードに追加の「上」ポインターがあり、循環リストの正規メンバーを見つけるために使用できます。

私は甘い代替品を逃していますか？

4

3 に答える 3

5

対処すべき等価性には 2 つの形式があるようです。単純な等価 (A) は、最新の状態に保たれる等価クラスとして追跡され、構造的等価 (D) は、単一の等価クラスを作成して破棄することがあります。

単純な同等性と構造的な同等性の両方に対して同等クラスを維持すれば、問題は概念的に単純になるように思えます。それが構造的同等性に過度の変化をもたらす場合は、構造的同等性のいくつかの側面に対して同等性クラスを維持できます。次に、これらの等価クラスを維持できるバランスを見つけながら、構造的に等価なノードのリストを作成するときに調べるノードの数を大幅に減らすことができます。

于 2009-04-09T00:44:26.097 に答える
4

1 つの構造で問題が解決するとは思いませんが、Disjoint-set data structure をご覧になることをお勧めします。結局のところ、等価クラスは集合の分割と同じものです。これらの操作の一部を迅速に処理できる必要があります。

于 2009-03-23T20:40:51.920 に答える
2

少し戻って、ツリーをまったく使用しないことをお勧めします。前回同様の問題に直面しなければならなかったとき、私はツリーから始めましたが、後で配列に移りました。

理由は複数ありますが、一番の理由はパフォーマンスでした。最大 100 程度の子を持つ私のクラスは、ツリーのノードを介するよりも配列として操作する方が実際にはパフォーマンスが向上します。これは主に、ハードウェアの局所性、CPU プリフェッチ ロジック、および CPU によるものです。パイプライン。

したがって、アルゴリズム的には、配列構造はツリーよりも多くの操作を必要としますが、これらの数十の操作を実行すると、メモリ全体でポインターを追跡するよりも高速になる可能性があります。

于 2009-04-14T01:13:33.633 に答える