36

Java には LinkedHashMap があり、99% を LRU キャッシュに移動します。

LRU キャッシュの Javascript 実装はありますか (できれば信頼できるソースから)。

  1. 理解できる
  2. 効率的 (償却された O(1) get/put/delete)

? ウェブで検索しましたが、見つかりませんでした。Ajax Design Patternsで 1 つ見つけたと思いましたが、sendToTail()メソッドを詳しく説明しており、O(n) のパフォーマンスを備えています (おそらく、キューと連想配列が分割されているため)。

私は自分で書くことができると思いますが、コアアルゴリズムの車輪を再発明することは健康に危険を及ぼす可能性があるという難しい方法を学びました:/

4

9 に答える 9

9

これ:

https://github.com/monsur/jscache

setItem(つまり、put)は最悪の場合O(N)ですが、挿入時にキャッシュがいっぱいになった場合に発生します。この場合、期限切れのアイテムまたは使用頻度の最も低いアイテムをパージするためにキャッシュが検索されます。getItemは O(1) であり、有効期限はgetItem操作で処理されます (つまり、フェッチされているアイテムの有効期限が切れている場合、それを削除して null を返します)。

コードは、簡単に理解できるほどコンパクトです。

PS を指定するオプションをコンストラクターに追加すると便利な場合がありますfillFactor。これは 0.75 に固定されています (つまり、キャッシュがパージされると、そのサイズは少なくとも最大サイズの 3/4 に縮小されます)。

于 2009-06-15T15:04:07.503 に答える
7

これは言及する価値があります: https://github.com/rsms/js-lru

関数のコア セットは O(1) で、コードには多くのコメントが付けられています (ASCII アートも!)

于 2014-11-03T23:11:50.300 に答える
4

monsur.com の実装は、実世界時間で実際に有効期限が切れるアイテムがあるため、挿入時にのみ O(n) です。これは単純な LRU ではありません。実世界の時間に関係なく、最近使用したアイテムのみを維持することに関心がある場合、これは O(1) で実行できます。二重にリンクされたリストとして実装されたキューは、最後から挿入または削除するための O(1) であり、キャッシュに必要なのはこれだけです。ルックアップに関しては、javascript が哀れなほど簡単にするハッシュ マップは、ほぼ O(1) ルックアップに適しているはずです (JavaScript エンジンが優れたハッシュ マップを使用すると仮定すると、もちろん実装に依存します)。これで、項目を指すハッシュ マップを持つ項目のリンク リストが作成されました。必要に応じてリンク リストの端を操作して、一方の端に新しいアイテムと要求されたアイテムを配置し、もう一方の端から古いアイテムを削除します。

于 2010-07-27T19:54:24.567 に答える
0

これは LRU キャッシュではありませんが、独自のリンク マップの実装があります。JS オブジェクトをストアとして使用するため、同様のパフォーマンス特性があります (ラッパー オブジェクトとハッシュ関数によってパフォーマンスが低下します)。

現在、ドキュメントは基本的に存在しませんが、関連する SO answerがあります。

メソッドは、現在のeach()キー、現在の値、およびコールバック関数への引数としてさらに要素があるかどうかを示すブール値を渡します。

または、ループは次の方法で手動で行うこともできます

for(var i = map.size; i--; map.next()) {
    var currentKey = map.key();
    var currentValue = map.value();
}
于 2009-06-15T15:30:26.520 に答える