6

ハッシュは、特定のキーに対応する値をほぼO(1)時間内に抽出するための優れたメカニズムを提供します。ただし、キーが挿入される順序は保持されません。では、最高の配列とハッシュをシミュレートできるデータ構造はありますか？つまり、特定のキーに対応する値をO(1)時間内に返し、nth挿入された値をO(1)時間内に返すことができますか？順序を維持する必要があります。つまり、ハッシュが{a:1,b:2,c:3}であり、のようなdel hash[b]ことが行われた場合は、nth(2)を返す必要があり{c,3}ます。

例：

hash = {};
hash[a] = 1;
hash[b] = 2;
hash[c] = 3;
nth(2); //should return 2
hash[d] = 4;
del hash[c];
nth(3); //should return 4, as 'd' has been shifted up

のようなモジュールを使用しTIE::Hashたり、同様のものを使用したりすることはできません。最初から開発する責任は私にあります。

4

4 に答える 4

8

これは、このデータ構造に割り当てられるメモリの量によって異なります。O(N) 空間の場合、いくつかの選択肢があります。

  • 「キーによる値の取得」、「挿入された n 番目の値の取得」、「挿入」の各操作で O(1) 時間でデータ構造を取得するのは簡単ですが、「削除」時間が O(N) の場合のみです。ppeterka で説明されているように、ハッシュマップと配列の組み合わせを使用するだけです。
  • あまり明白ではありませんが、「削除」の O(sqrt N) と他のすべての操作の O(1) は単純です。
  • もう少し複雑なのは、O(N 1/4 )、O(N 1/6 )、または一般的には O(M*N 1/M ) 時間で「削除」することです。
  • 他の操作のために O(1) を保持しながら、「削除」時間を O(log N) に減らすことは、おそらく不可能です。ただし、すべての操作で O(log N) 時間に同意する場合は可能です。二分探索木またはスキップ リストに基づくソリューションでは、それが可能です。1 つのオプションは、注文統計ツリーです。二分探索木のすべてのノードをカウンターで拡張し、このノードの下のサブツリーに要素の数を格納できます。次に、それを使用して n 番目のノードを見つけます。他のオプションは、Indexable skiplistを使用することです。もう 1 つのオプションは、M=log(N) で O(M*N 1/M ) ソリューションを使用することです。
  • そして、他の操作の時間をさらに増やすことなく、O(1) の「削除」を取得できるとは思いません。

無制限のスペースが利用できる場合、すべての操作を O(1) 時間で実行できます。

O(sqrt N) "削除"

2 つのデータ構造の組み合わせを使用して、キーで値を検索したり、挿入順序で値を検索したりできます。1 つ目はハッシュ マップです (キーを他の構造体の値と位置の両方にマッピングします)。2 つ目は、位置を値とキーの両方にマップする階層化された vectorです。

階層化されたベクトルは比較的単純なデータ構造であり、ゼロから簡単に開発できます。主なアイデアは、配列をそれぞれのサイズが sqrt(N) の sqrt(N) より小さい配列に分割することです。各小さな配列は、削除後に値をシフトするのに O(sqrt N) 時間しかかかりません。また、各小さな配列は循環バッファーとして実装されるため、、小さな配列は O(1) 時間で単一の要素を交換できます。これにより、O(sqrt N) 時間で「削除」操作を完了することができます (削除された値と最初/最後のサブ配列の間の各サブ配列に対して 1 つのそのような交換) . 階層化されたベクトルは、O(sqrt N) でも途中に挿入できますが、この問題はそれを必要としないため、O(1) 時間で最後に新しい要素を追加するだけで済みます。要素にその位置でアクセスするには、要素が格納されている部分配列の循環バッファーの開始位置を決定し、循環バッファーからこの要素を取得する必要があります。これには O(1) 時間も必要です。

ハッシュ マップは各キーの階層化されたベクトル内の位置を記憶するため、階層化されたベクトル内のいずれかの要素の位置が変更されたときに更新する必要があります (「削除」ごとに O(sqrt N) ハッシュ マップが更新されます)。

O(M*N 1/M ) "削除"

「削除」操作をさらに最適化するには、この回答で説明されているアプローチを使用できます。要素を遅延して削除し、削除された要素を考慮して、トライを使用して要素の位置を調整します。

すべての操作で O(1)

これを行うには、3 つのデータ構造を組み合わせて使用​​できます。1 つ目はハッシュ マップです (キーを値と配列内の位置の両方にマッピングします)。2 つ目は、位置を値とキーの両方にマップする配列です。3 つ目はビット セットで、配列の要素ごとに 1 ビットです。

「挿入」操作は、配列の末尾にもう 1 つの要素を追加し、それをハッシュ マップに挿入するだけです。

「削除」操作は、ビット セット内の対応するビットのセットを解除するだけです (すべてのビット = 1 で初期化されます)。また、対応するエントリをハッシュ マップから削除します。(配列またはビット セットの要素は移動しません)。「削除」後、ビット セットの要素が一定の割合 (10% など) を超えて削除された場合、データ構造全体を最初から再作成する必要があります (これにより、O(1) の償却時間が可能になります)。

「キーによる検索」は簡単です。ここではハッシュ マップのみを使用します。

「位置による検索」には、いくつかの前処理が必要です。2D 配列を準備します。1 つのインデックスは、検索する位置です。その他のインデックスは、インデックスとして再解釈されたデータ構造の現在の状態、ビット セットです。可能なすべてのビット セットの各プレフィックスの人口カウントを計算し、人口カウントとビット セット自体の両方によってインデックス付けされたプレフィックス長を格納します。この 2D 配列の準備ができたら、まずこの 2D 配列の位置と現在の「状態」でインデックスを付け、次に値で配列にインデックスを付けて、この操作を実行できます。

すべての操作の時間の複雑さは O(1) です (挿入/削除の場合は O(1) 償却されます)。空間の複雑さは O(N 2 N ) です。

実際には、ビットセット全体を使用して配列にインデックスを付けると、N の許容値がポインターサイズ (通常は 64) によって制限され、さらに使用可能なメモリによって制限されます。これを軽減するために、配列とビット セットの両方をサイズ N/C のサブ配列に分割できます。ここで、C は定数です。これで、より小さな 2D 配列を使用して、各サブ配列の n 番目の要素を見つけることができます。また、構造体全体で n 番目の要素を見つけるには、各サブ配列に有効な要素の数を記録する追加の構造体が必要です。これは一定サイズ C の構造体であるため、すべての操作も O(1) です。この追加の構造は配列として実装することもできますが、インデックス可能なスキップリストのような対数時間構造を使用することをお勧めします。この変更の後、すべての操作の時間計算量は依然として O(1) です。空間の複雑さは O(N 2 N/C ) です。

于 2012-10-22T14:48:21.363 に答える
8

さて、質問は私にとっても明らかです（決して遅くなるよりはましです...）ここに私の提案があります：

  • 2 つのハッシュを維持できます。1 つはキー付き、もう 1 つは挿入順序付きです。ただし、これは非常に見苦しく、削除するときとその間に挿入するときに維持するのが遅くなります。これにより、両方の方法で要素にアクセスするのに必要なほぼ同じ O(1) 時間が得られます。
  • キーにハッシュを使用し、挿入順序の配列を維持できます。これはハッシュタイプよりもはるかに優れており、削除はまだそれほど高速ではありませんが、2つのハッシュアプ​​ローチよりもはるかに高速だと思います. これにより、n 番目の要素へのアクセス時にも真の O(1) が得られます。

最初、私は質問を誤解し、O(1) キー ルックアップと、n 番目の要素の O(n) ルックアップを提供するソリューションを提供しました。

Java には、この特定のタスク用のLinkedHashMapがあります。

しかし、誰かがこのページを見つけたら、これはまったく役に立たないかもしれないと思うので、ここに残します...

于 2012-10-19T08:59:12.637 に答える
3

O(1) には、引用したすべてのデータ構造はありません。特に、途中でランダムな動的挿入/削除が行われ、ソート/インデックス アクセスが行われるデータ構造は、メンテナンス時間を O(log N) よりも短くすることはできません。このような動的コレクションを維持するには、演算子「未満」(バイナリ、したがって O(log2 N)) または計算された組織 (典型的な O(sqrt N)、sqrt(N) サブ配列を使用)。O(sqrt N)>O(log N) であることに注意してください。

いいえ。

リンクされたリスト+ハッシュマップで順序を維持することを含むすべてでO(1)に到達する可能性があり、アクセスがほとんどシーケンシャルである場合は、nth(x)をキャッシュして、O(1)のnth(x+/-1)にアクセスできます。

于 2012-10-27T10:08:17.500 に答える
0

単純な配列のみが O(1) を提供すると思います。最善の方法は、最悪のシナリオで O(n) を提供するソリューションを探すことです。また、プレーン配列のインデックスとしてキーを使用するという、本当に悪いアプローチを使用することもできます。任意のキーをプレーン配列のインデックスに変換する方法があると思います。

std::string memoryMap[0x10000];
int key = 100;
std::string value = "Hello, World!";
memoryMap[key] = value;
于 2012-10-19T19:10:32.167 に答える