O（1）要素の削除による動的配列

Question

この質問は私が考えたデータ構造に関するものです。これは、C++のstd :: vector <>のような動的配列ですが、削除アルゴリズムが異なる点が異なります。

通常のダイナミック配列では、要素が削除されたとき、残りの要素はO（n）になります。最後の要素でない限り、O（1）になります。

この場合、削除された要素があれば、最後の要素に置き換えられます。これはもちろん、要素の順序を失う。しかし、今や要素の除去は一定の時間です。

リストには同じ削除時間がありますが、この構造にはランダムアクセスがあります。その唯一の注意点は、注文が混乱する可能性があるため、アクセスしているものがわからないということです。リストは、要素へのポインタ/イテレータを混乱させません。

だから、この構造は、厳密に要素を歩いて、おそらくそれらを途中で取り除くという特定のタスクを除いて、むしろ役に立たないようです。リストも同じことができますが、キャッシュのパフォーマンスは向上します。

この奇妙な/役に立たない構造は名前を持っていますか？またはちょうど良い小さな脳の嵐？

Answer 1

この考えはKnuth (Fisher–Yates) shuffleで使用されています。ランダムに選択された要素は、配列内の最後の要素に置き換えられます。とにかく私たちが望むのはランダム置換ですから、並べ替えは重要ではありません。

Answer 2

Hm、実際にそのアルゴリズムはO（1）除去時間を持っていますか？削除する要素を見つける

1. は、（削除要素を置き換えます）最後の要素が第二を見つけるO（1）
2. で検索（1）
3. Oであることを意味する

   最後の要素（最後の新しい要素）はO（1）

...私は思い付くことができるデータ構造はありません。二重リンクリストは、これらの制約を完全に満たすことができますが、削除する要素へのポインタをすでに持っていることを前提とします。

Answer 3

この方法を使用する前に、何度も覚えています。しかし、私はそれの名前を知らない。

単純な例：コンピュータゲームでは、すべての「悪い人」を繰り返して動きなどを計算しています。それらに起こる可能性のあることは、消滅することです（死体は消えてしまい、現在は99％透明です） 。その時点で、リストから削除し、反復カウンタを増やさずにイテレータを再開します。

これは、アイテムを削除するときにBinary Heapで行われますが、次のステップはヒープルール-O（log n）を維持することです。

Answer 4

この奇妙な/役に立たない構造は名前を持っていますか？

私は、マルチプロセスシステムのシミュレーションで同様のことを使用しました。

ステートマシンとして実装されたプロセスのスケジューラでは、各プロセスが外部イベント、アクティブまたは完了を待機しています。スケジューラーには、プロセスへのポインターの配列があります。

最初は各プロセスがアクティブであり、スケジューラは最後に待機して最初に完了したプロセスのインデックスを持ち、最初は0であり、配列の長さです。

V-- waiting 
[ A-active, B-active, C-active, D-active ] 
          completed --^ 
^- run 

スケジューラは、プロセスを次の状態にするために、アレイを繰り返し処理し、各プロセスを順番に実行します。プロセスが待機中であると報告した場合は、アレイ内の最後の待機プロセスの後にプロセスと交換されます。

  V-- waiting 
[ A-waiting, B-active, C-active, D-active ] 
           completed --^ 
      ^- run 

完了したと報告された場合は、最初に完了した配列の前のプロセスと交換されます。だから、アクティブから待機中または完了にスケジューラが実行され、プロセスの遷移として、配列が最後に開始時に待機中のすべてのプロセス、途中ですべてのアクティブなもの、そして完成したものと一緒に注文なっ

  V-- waiting 
[ A-waiting, D-active, C-active, B-completed ] 
        completed --^ 
      ^- run 

。もはやアクティブなプロセスが存在する場合

     V-- waiting 
[ A-waiting, C-waiting, D-active, B-completed ] 
        completed --^ 
         ^- run 

反復の特定の番号のいずれかの後、又は、完了したプロセスは、アレイの外に洗浄され、外部のイベントが処理される：

     V-- waiting 
[ A-waiting, C-waiting, D-completed, B-completed ] 
      completed --^ 
         ^- run == completed so stop 

これはに類似していますスワップを使ってコレクションからアイテムを削除していますが、両端からアイテムを削除して、コレクションの中央に残しています。

Answer 5

Setと呼ばれています。

Answer 6

私はそれの名前を知っていませんが、特定のケースではリストよりも優れています。

特に、非常に小さいデータの場合、単一または二重リンクリストよりも大幅に優れています。 すべてを連続して保存するため、要素ごとに余分なポインタオーバーヘッドはありません。