6

値を持つタプルのリストを含む適切なデータ構造を探してい(hash, timestamp)ます。基本的には、次の方法で使用したいと思います。

  • データが入ってくると、それがデータ構造に既に存在するかどうかを確認します (タイムスタンプではなく、ハッシュの等価性)。
  • そうである場合は、タイムスタンプを「今」に更新します
  • そうでない場合は、タイムスタンプ「今」でセットに追加します

定期的に、特定のタイムスタンプよりも古いタプルのリストを削除して返したいと考えています (「期限切れ」になったときに他のさまざまな要素を更新する必要があります)。タイムスタンプは特定のものである必要はありません (UNIX タイムスタンプ、Pythondatetimeオブジェクト、またはその他の簡単に比較できるハッシュ/文字列にすることができます)。

これを使用して着信データを受信し、既に存在する場合は更新し、X 秒/分より古いデータを消去します。

複数のデータ構造も有効な提案になる可能性があります (最初は優先度キュー + セットを使用しましたが、優先度キューは常に値を更新するには最適ではありません)。

同じことを達成するための他のアプローチも歓迎されます。最終的な目標は、要素がいつ a) システムにとって新しいか、b) システムに既に存在するか、c) 有効期限が切れるかを追跡することです。

4

5 に答える 5

2

私があなたの質問を読み違えていない限り、普通の古いdictものはパージ以外のすべてに理想的です。パージ中にディクショナリ全体を検査する必要を回避しようとしていると仮定すると、(timestamp, hash)ペアを保持するために 2 番目のデータ構造を維持することをお勧めします。

この補足データ構造は、単純な古いものlistまたはdeque(collectionsモジュールからの) のいずれかです。おそらくこのbisectモジュールは、(カットオフ値に達するまですべてのタイムスタンプを比較するのではなく) タイムスタンプの比較の数を最小限に抑えるのに便利ですが、必要な項目を順番に反復する必要があるためです。パージするには、何が最も速いかの正確な詳細を解決するには、いくつかのテストが必要です。

編集：

Python 2.7 または 3.1+ の場合、OrderedDict(collectionsモジュールから) を使用することも検討できます。これは基本的dictに、クラスに組み込まれた補助的な順序保持データ構造を持つ であるため、自分で実装する必要はありません。唯一の問題は、それが保持する唯一の順序は挿入順序であるため、目的のために、既存のエントリを新しいタイムスタンプに再割り当てするのではなく、( を使用してdel)それを削除してから、新しいエントリを新しいタイムスタンプ。それでも、O(1) ルックアップが保持されるため、(timestamp, hash)ペアのリストを自分で管理する必要がなくなります。パージする時が来たらOrderedDict、カットオフより後のタイムスタンプを持つエントリに到達するまでエントリを削除して、 をまっすぐに繰り返すことができます。

于 2013-10-09T17:17:16.580 に答える