1

ランダムな順序で到着するが、指定された順序で処理および/またはスタックから削除する必要があるデータを処理するための適切に効率的なストレージ構造を探しています。

これを明確にするために：

各アイテム x にはインデックス i、タイムスタンプ t があり、次のように処理されます (ストレージ構造が既に設定されていると仮定します)。

repeat
  1) Process (remove) the item with the smallest time stamp.
  2) Add new items (0 or more).
  3) Remove (0 or more) items (referenced by their index).
until false

各アイテムが一意のタイムスタンプとインデックスを持つことが保証されています。しかし、ステップ 1) が完了するまで、ステップ 2) でいくつの項目が追加されるか、またはステップ 1) と 2) がアルゴリズムの各ループ内で完了するまで、ステップ 3) でいくつの項目が削除されるかを予測することは不可能です。着信アイテムのタイムスタンプの分布は予測できず (新しいタイムスタンプが「将来」になることを除いて)、時間とともに変化する可能性があります。またはそれ未満) リストに残っている項目のいずれか。一度に処理されるのを待っている要素の最大数がありますが、これはかなり大きくなる可能性があります ~10^6-10^8,

ステップ 2) で到着した各アイテムをリンクされたソート済みリストに追加すると、ステップ 1) は O(0) になりますが、ステップ 2) は O(n) になります。二分木を使用すると、ステップ 1) はまだ O(1) であり、ステップ 2) は最初は O(log n) ですが、タイムスタンプが適切に分散されていないと、ツリーが非常に急速に不均衡になり、ステップ 2) が遅くなる可能性があります。大幅にダウンします（定期的にツリーのバランスを取り直さないと、最終的にはO（n）よりも良くなりません）。

私の推測では、定期的なリバランスを行うバイナリ ツリーに沿ったものは、リバランスが適切な間隔で行われる場合、O(log n) を提供するはずですが、この種の問題は十分に解決されていると思います。誰かが私に適切なリファレンスを教えてくれるか、車輪の再発明を避けるのに役立つちょっとしたアドバイスをくれませんか.

4

1 に答える 1

4

データ構造ヒープを使用すると、O(logN) のすべての操作でこれを簡単に実行できます。

http://en.wikipedia.org/wiki/Heap_(データ構造)

ヒープはタイムスタンプをキーとして受け取ります。また、ペア Q=(item.Index、ヒープ内のアイテムの位置) を格納するには、追加の配列 (または dict) が必要になります。

これはヒープであるため、操作 1) と 2) は各アイテムに対して O(logN) のコストがかかります。

操作 3) では、ヒープからランダムなアイテムを削除する必要があります。幸いなことに、ここで述べたように簡単です。item.index はヒープ内の実際の場所ではないため、O(1) の item.Index によってヒープ内のアイテムの位置を探すために、上記の辞書 Q が必要になります (ハッシュ マップの場合)。 、またはその位置を探すのに O(N) の費用がかかります。また、アイテムの位置は操作 (操作 1 と 2 を含む) 中に変わる可能性があるため、アイテムがヒープ内で移動するたびに Q の値を変更することを忘れないでください。

プライオリティ キューについて誰かが言及したように、ここでさらに言葉を追加します。

プライオリティ キューは、いくつかの抽象インターフェイスを持つ抽象データ型です。そして、それらのインターフェースには、常識的に「ランダムなアイテムを削除する」ことは含まれていません。

ヒープはデータ構造です。

プライオリティ キューは、ヒープを使用して実装できます。ただし、ヒープは、優先キューよりもはるかに多くの操作をサポートできます。

于 2012-08-02T03:46:57.493 に答える