LRU、キャッシュ押し出し方法

残念ながら、同僚のほとんど全員がLRUとは何か、特定のサイズのキャッシュを実装する方法を知らないことに再び気付きました。 そのため、 LRUメソッドを迅速に実装する方法を説明する短い記事を書くことにし、同僚がキャッシュを不要な場所に手動でリセットすることを強制しないようにしました。

キャッシングは、一部のクエリに応じて計算結果を保存するものとして理解します。 つまり、繰り返されるクエリ結果は常に再計算されるわけではありませんが、キャッシュと呼ばれるテーブルから取得されることがあります。 現代のシステムにおけるキャッシングの役割を過大評価することは困難です。 これは、多くの場合、メモリ不足の問題を引き起こします。 実際、リクエストが多く、限られた数の結果を保存するだけのメモリがある場合はどうすればよいでしょうか？ この場合、原則として、キャッシュは次のようにまっすぐになります。 キャッシュサイズは固定されており、 Nとし、結果はN個の最も「人気のある」クエリに対してのみ保存されます。

つまり、計算の結果が保存され、再度要求される可能性があります。
これらの「人気のある」クエリを識別する方法は？ 最も有名な方法はLRUです。これについては、この記事で説明します。

LRU （最も最近使用されていない）は、最も長く要求されなかった値が置き換えられるアルゴリズムです。 したがって、最後のリクエストの時刻を値に保存する必要があります。 また、キャッシュされた値の数がNを超えるとすぐに、最も長く要求されていない値をキャッシュからプッシュする必要があります。

このメソッドを実装するには、2つのデータ構造が必要です。

1. 直接キャッシュされた値を保存するhashTableハッシュテーブル。
2. 優先キュー timeQueue 。 次の操作をサポートする構造：
   • 値と優先度のペアtimeQueue.Add（val、priority）を追加します。
   • 優先度が最も低いtimeQueue.extractMinValue（）で値を取得（削除して返します） 。

優先キューの詳細については、 こちらをご覧ください。

最初の計算では、 calculate（x）メソッドが使用されたと仮定します。 Calculateメソッドを新しいCalculateWithCacheに置き換えます 。これにより、キャッシュが補充され、古い値がプッシュされ、キャッシュ内で見つからない場合にCalculateから結果が要求されます。

これは、 calculateWithCacheアルゴリズムの動作方法です。

calculateWithCache(key) { curTime = getCurrentTime(); //         if (key in hashTable) { //       key timeQueue.set(key, curTime); return hashTable[key]; } //    result = calculate(key); //     N ,     if (hashTable.length == N) { minKey = timeQueue.extractMinValue(); hashTable.remove(minKey); } //   ,    hashTable.add(key, result); timeQueue.add(key, curTime); return result; } 

以上です。 ここで、ユーザーはキャッシュをフラッシュする代わりに、キャッシュサイズを設定する必要があります。 その際、適切なデフォルト値を設定することをお勧めします。

優先度キューの効果的な実装を使用する場合、 LRUを必要とするオーバーヘッドはO（log N）です。

標準ライブラリでは、たとえばC ++で優先度キューを実装できます。 ただし、実装されていなくてもゆっくり読んでいる場合でも、バランスの取れたツリーを使用して、少し複雑ですが、同じ複雑さの優先度を持つキューを実装する方法を推測できます。

少し考えたい人への質問 。 ハッシュテーブル操作の複雑さが一定であることを考慮して、一定のオーバーヘッドを達成する方法は？
ヒント：優先度キューを削除し、通常のキューを使用する必要があります:)

特定のキーkeyの計算時間計算 、結果のボリューム、または他の何かを考慮に入れた、より複雑なヒューリスティックを見つけることができます。
しかし、ほとんどのタスクで、 LRUは最も「人気のある」クエリを最も適切に定義します。

注1 ：保存される値の数ではなく、キャッシュごとのメモリ量を制限できます。 アルゴリズムは、実際には変更されず、長さの代わりに、新しい値を格納するためのメモリ+メモリが占​​有されます。
注2 ：これはこの記事のトピックではないため、特にマルチスレッドの問題を回避しました。

更新 （コメントについてはToSHiC22に感謝）興味のある方のために、少し高度な2Q実装へのリンク