問題タブ [lru]

Python で dict を使用したいのですが、キーと値のペアの数を X に制限します。つまり、dict が現在 X のキーと値のペアを格納していて、挿入を実行する場合、次のいずれかが必要です。ドロップする既存のペア。それが最も最近挿入された/アクセスされていないキーであればいいのですが、それは完全に必要というわけではありません。

これが標準ライブラリに存在する場合は、時間を節約して指摘してください!

最も使用頻度の低い (LRU) キャッシュは、使用頻度の最も低いアイテムを最初に破棄するものです。このようなキャッシュ クラスをどのように設計して実装しますか? 設計要件は次のとおりです。

1) できるだけ早くアイテムを見つける

2) キャッシュ ミスが発生してキャッシュがいっぱいになると、使用頻度の最も低いアイテムをできるだけ早く置き換える必要があります。

設計パターンとアルゴリズム設計の観点から、この問題をどのように分析して実装しますか?

Memcached は、LRU キューを使用してエビクションを行うと述べています (スラブのサイズに基づいたいくつかのルールが混在しています)。彼らのドキュメンテーションはここではあいまいに思えます。

現在、メモリが非常に少ないモバイルプラットフォームのソフトウェアに取り組んでいます。I/O ボトルネック関数では、シーク操作を使用して img ファイルから数バイトを読み取る必要があります (シークは、メモリから直接読み取るよりも約 10 倍遅いと想定できます)。私のテストでは、この関数は 7480325 回呼び出され、bytes_offset 6800 から 130000 までのバイトを読み取るため、すべてのバイトは平均で 100 回読み取られます (3 ～ 4 回読み取られるバイトもあれば、1000 回以上読み取られるバイトもあります)。

以下は私の統計です。

次に、LRU スキーマを使用してキャッシュを構築し、I/O パフォーマンスを向上させたいと考えています。他の人の質問では、ハッシュテーブル + 二重リンク リストが良い方法だと思います。しかし、私の問題を最善の方法で改善するための構造を作るにはどうすればよいでしょうか? 1300 個のバケットを作成する予定で、すべてのバケットが最大サイズ 10 の二重リンク リストを所有しています。この場合、必要な合計メモリは約 13KB です。実装と保守は簡単ですが、効率は最高ではないと思います。

私の統計では、一部のバイト オフセット間隔ではヒット率が高く、一部の間隔ではヒット率が低くなります。統計を適応させるための構造を構築するにはどうすればよいですか?

また、キーを検索するときは、サイズ 10 のリスト全体をトラバーサルする必要があります。検索効率の高い方法は他にありますか?

一部のモバイル プラットフォームではキャッシュにより多くのメモリを使用できますが、他のプラットフォームではより少ないメモリを使用できます。バケットのサイズを変更する以外に、許可されたメモリの変更をキャッシュに適応させるにはどうすればよいですか?

cafの方法の方が良さそうです。大きな二重リンク リストと、キーをノード エントリにマッピングする大きなハッシュ テーブルを使用することは、より理にかなっていて、LRU をより活用できます。しかし、ハッシュ関数の設計は難しい問題になりつつあります。

あなたの提案を待っています、ありがとう〜

C++ を使用して LRU キャッシュを実装しようとしています。それらを実装するのに最適な設計は何かを知りたいです。LRU が find() を提供し、要素を追加し、要素を削除する必要があることはわかっています。remove は LRU 要素を削除する必要があります。これを実装するのに最適な ADT は何ですか?例: 要素を値として、時間カウンターをキーとして使用するマップを使用すると、O(logn) 時間で検索できます。挿入は O(n)、削除は O(logn) です。

私は6,00,000 entries in MongoDB次の形式で周りにいます：

どこ

• 機能は任意の単語である可能性があり、
• カテゴリがポジティブまたはネガティブであり、
• countは、そのカテゴリのドキュメントでフィーチャが発生した回数を示します。

毎回データベースにクエリを実行しないように、上位 1000 個のタプルをキャッシュしたいとします。

Python で LRU キャッシュを構築するにはどうすればよいですか? または、これに対する既知の解決策はありますか?

各要素が最後に選択されてからの時間によって重み付けされているリストの要素を選択したいと思います。

キュー内の位置に基づいて関数を重み付けすることで、LRU (最近使用されていない) リストを作成できます。これは、最初はすべての要素を均等に重み付けする必要があることを除けば、洗練されたものです。

重みを選択した後で、重みを特定の量で減算または除算するだけでは、直感的に正しくないように思えます。おそらく対数や逆数などの数学的概念を使用するより良い方法はありますか? （私の長所ではありません）

LinkedHashMap から拡張されたマップを使用してキャッシュを実装しています (したがって、removeEldestEntry を実装できます)。古い実装では、設定された間隔で更新される通常のハッシュ マップが使用されていました。キャッシュ内のデータを最新の状態に保つ方法を考えていました。LRUのポイントを台無しにすることなく、特定の時間にリフレッシュできるとは思えません。エントリのタイムスタンプを DB に照会するのは特にコストがかかりますか?

std::set コンテナについて簡単な質問があります。現在、プッシュバック機能を使用してセットにフィードしています。もちろん、セットは push_back ごとにどんどん大きくなります。最新の 30 要素程度にのみ関心があります。古い要素は削除できます。したがって、私の考えは、セットのサイズを 30 要素程度に制限し、そうすることで不要な古い要素を取り除くことです。ただし、このセットはデフォルトでは制限をサポートしていません。セットのサイズを時々チェックして、余分な要素を手動で削除することができました。よりスマートな方法はありますか？

よろしくルンピ

私のアプリケーションでは、1000 前後のビットマップがたくさんあります。それらを 1 つの画像としてマージする必要があります。これを行うには、sdcard から現在必要なビットマップをロードします。このプロセスでは、最近使用されていないビットマップを再利用する必要があります。Javaでこのタスク（最近使用されていない）を達成する方法を誰か教えてもらえますか??

ありがとう、スリニバス