"制限されたメモリマップ"のデータ構造

Question

鍵Kを値Vにマッピングする連想集合を実装したいと思います。さらに、各値Vを重みに関連づけたいので、Map [K→（V、Double） ]。

考えられるのは、このコレクションのメモリバージョンが制限されていることです。これは、重みしきい値tを超えた要素のみを格納します。このコレクションに要素eを挿入するたびに、eの重みをある量だけ増加させます。 1であり、他のすべての要素e '！= eの重みをある減衰係数、例えば0.0001で減衰させる。 これは、このコレクション内に存在する要素が、どちらかであることを保証します。 最近、またはb。 が頻繁にです。

もちろん、減衰動作を能動的に実行するこのようなデータ構造のナイーブなバージョンを実装し、すべての要素のしきい値tの妥当性をチェックすることができます。それはひどく非効率的です。

まさにそこにデータ構造があるのだろうと私は思っています。たぶん私の要件を実装するために使用できる関連するデータ構造があります。入力は高く評価されます。

Answer 1

これは、LFU（Least Frequently Used）キャッシュエビクションポリシーのバリエーションのように聞こえます。ここでは、エビクションの決定に、更新の相対的な割合に基づく追加のしきい値が考慮されます。

挿入時に他のすべてのエントリを積極的に減衰させる必要はありません。特定の追い出し候補をそのポイントでしきい値を超えているかどうか評価して保持するかどうかを計算できるように、 。

重みを使用しないでやや異なるアプローチは、キーを値ごとにバケットに格納することです。値の検索のキーは特定のバケットのコンテキスト内で行われます。

• 各バケットには、バケットに値を挿入できる時間範囲があります。
• 各バケットの内部にはK -> Vマップがあります。
• K -> Bucketの追加地図が保持されます。
• バケットは、順序付きリストに挿入されます。

データ構造への挿入は希望：今、最新のバケツのために有効な時間範囲外にある場合

• は、新しい現在のバケットを割り当てます。
• Kがまだ存在しない場合は、バケットマップのキーに現在のバケットとK -> currentにK -> Vを挿入バケツに
• を存在していたかどうかを確認します。
• 現在の（最新の）バケットに存在する場合は何もしないでください。
• 古いバケットに存在する場合は、それを現在のバケットに移動し、バケットマップを更新します。

最近使用されたものが最近のバケットに移動します。古いバケツに終わらないもの。古いバケツを定期的にパージします。

バケツレベルで上記の方法を使用することも可能ですが、コレクション内のアイテムよりもバケット数が少なくて済むため、コストを削減できますレベル。