17

インデックスと値が同じ範囲にある、重複のない整数の順序付きリストを保持できるデータ構造を探しています。

効率を上げるには、重要度の高い順に4つの主要な操作が必要です。

  1. 特定のインデックスから値を取得する
  2. 与えられた値のインデックスを見つける
  3. 特定のインデックスに値を挿入する
  4. 特定のインデックスの値を削除する

配列を使用すると、O（1）に1がありますが、2はO（N）であり、挿入と削除にはコストがかかります（O（N）もそうだと思います）。

リンクリストにはO（1）の挿入と削除がありますが（ノードがある場合）、1と2はO（N）であるため、ゲインが無効になります。

2つの配列a[index]=valueとb[value]= indexを維持しようとしました。これにより、1と2がO（1）になりますが、3と4はさらにコストのかかる操作になります。

これにより適したデータ構造はありますか？

4

8 に答える 8

16

赤黒木を使用してキーを値にマップします。これにより、1、3、4のO（log（n））が得られます。また、ソートされた順序でキーを維持します。

2の場合、ハッシュテーブルを使用して値をキーにマップします。これにより、O（1）のパフォーマンスが得られます。また、赤黒木でキーを追加および削除するときにハッシュテーブルを最新の状態に保つためのO（1）オーバーヘッドが追加されます。

于 2009-05-20T21:39:02.833 に答える
4

二分探索でソートされた配列を使用するのはどうですか？

挿入と削除が遅い。ただし、データが単純な整数であるという事実を考えると、CまたはC ++を使用している場合は、memcpy（）を呼び出すことで最適化できます。アレイの最大サイズがわかっている場合は、アレイを最大サイズに事前に割り当てることができるため、アレイの使用中にメモリの割り当てを回避することもできます。

「最良の」アプローチは、保存する必要のあるアイテムの数と、検索と比較して挿入/削除する必要のある頻度によって異なります。ソートされた配列をめったに挿入または削除しない場合は、値へのアクセスが確かに優れていますが、頻繁に挿入および削除する場合は、配列よりもバイナリツリーの方が優れている可能性があります。十分に小さいnの場合、配列はどのような場合でもツリーを打ち負かす可能性があります。

ストレージサイズが問題になる場合は、アレイもツリーよりも優れています。ツリーは、格納するすべてのアイテムにメモリを割り当てる必要もあります。小さな値（整数）しか格納しないため、メモリ割り当てのオーバーヘッドが大きくなる可能性があります。

ソートされた配列またはメモリ（デ）割り当てのあるツリーから挿入/削除した場合の整数のコピーなど、より高速なものをプロファイリングすることをお勧めします。

于 2009-05-20T21:32:28.040 に答える
2

使用している言語はわかりませんが、Javaの場合は、LinkedHashMapまたは同様のコレクションを利用できます。リストとマップのすべての利点があり、ほとんどの操作に一定の時間を提供し、象のメモリフットプリントを備えています。:)

Javaを使用していない場合でも、LinkedHashMapのアイデアは、問題に使用できるデータ構造に適しています。

于 2009-05-20T21:43:35.820 に答える
2

配列アクセスにはベクトルを使用します。

ベクトルへの添え字への検索インデックスとしてマップを使用します。

  • 下付き文字が与えられると、ベクトルO（1）から値をフェッチします
  • キーが与えられたら、マップを使用して値の添え字を見つけます。O（lnN）
  • 値を挿入し、償却されたベクトルO（1）を押し戻し、下付き文字をマップO（lnN）に挿入します。
  • 値を削除し、マップから削除しますO（lnN）
于 2012-10-21T09:57:35.057 に答える
1

ツリーマップはどうですか？説明されている操作のlog（n）。

于 2009-05-20T21:35:25.210 に答える
1

バランスの取れた二分木が大好きです。それらはハッシュテーブルや他の構造よりも遅い場合がありますが、はるかに予測可能です。これらは通常O(log n)、すべての操作に使用されます。赤黒木またはAVL木を使用することをお勧めします。

于 2009-05-20T21:36:00.670 に答える
1

RBツリーで2を達成する方法は？挿入/削除操作ごとに子供を数えることができます。これにより、これらの操作が大幅に長くなることはありません。次に、ツリーを降りてi番目の要素を見つけることがlogn時間で可能です。しかし、javaでもstlでもこのメソッドの実装は見当たりません。

于 2010-04-28T06:50:54.117 に答える
0

.NETで作業している場合は、MSドキュメントhttp://msdn.microsoft.com/en-us/library/f7fta44c.aspxによると

  • SortedDictionaryとSortedListの両方に、取得用のO（log n）があります
  • SortedDictionaryには挿入および削除操作用のO（log n）がありますが、SortedListにはO（n）があります。

この2つは、メモリ使用量と挿入/削除の速度が異なります。SortedListは、SortedDictionaryよりも少ないメモリを使用します。SortedListがソートされたデータから一度に入力される場合、SortedDictionaryよりも高速です。ですから、どちらが本当にあなたに最適かは状況によって異なります。

また、リンクリストの引数は挿入のO（1）である可能性があるため、実際には有効ではありませんが、挿入ポイントを見つけるためにリストをトラバースする必要があるため、実際にはそうではありません。

于 2009-05-20T21:49:07.337 に答える