1

N 個のアイテムが M 個の異なるセットにグループ化されている場合、要素がどのセットに属しているかを見つけるための適切なデータ構造は何ですか? たとえば、セットが {A,B} 、 {C,D,E}、{F,G} の場合、「D」を指定してセットを見つけるにはどうすればよいですか? セットはハッシュ セットであるため、セット内の含むクエリは O(1) です。

セットのリストにセットがあるだけの場合、

[{A,B}, {C,D,E}, {F,G}]

リスト内の各セットにアイテムが含まれているかどうかを尋ねるだけで、ルックアップを取得できます。これは実装が簡単で、実行時間は (セット数で) 線形です。

より高速なアプローチは、すべてのセットをハッシュ テーブルに格納し、各セットのすべてのアイテムをキーにします。あれは：

[A -> {A, B},
 B -> {A, B},
 C -> {C, D, E},
 D -> {C, D, E},
 E -> {C, D, E}, 
 F -> {F, G}, 
 G -> {F, G}]

この構造により、正しいセットを O(1) 時間で取得できますが、非効率的で醜く感じられます。正しいセットの O(1) ルックアップを可能にする、より優れたデータ構造はありますか? 一種のブルームフィルターのようにハッシュを組み合わせてルックアップキーを作るべきでしょうか? 他のアイデア？

4

1 に答える 1

0

次の方法で実装できます。

木の配列が必要になります。index がセット番号になります。

リスト全体の各要素の (要素、インデックス) ペアを格納するためのハッシュ テーブルを用意します。

各セットには、ツリー構造を使用できます。一意の識別子がルートであり、リストの要素がルートに接続されています。

于 2013-05-01T18:19:01.830 に答える