問題タブ [lru]

アルゴリズム LRU について少し質問があります。4 ブロックのキャッシュがある場合、このアルゴリズムを実装するには何ビットが必要ですか?

キャッシングの仕組みを理解しようとしています。私はこの概念をよりよく理解するために問題に取り組んでいます:

ブロックの長さが 1 ワードで、合計サイズが長さ 32 ビットの 16 ワードである 2 ウェイ セット連想キャッシュの場合、最初は空で、最も使用頻度の低い置換戦略を使用します。次のアドレスがヒットしたかミスしたかを示し、キャッシュの最終的な内容を一覧表示します。

住所:

1. 00010001
2. 01101011
3. 00111111
4. 01001000
5. 00011001
6. 01000010
7. 10001001
8. 00000000
9. 01001000
10. 00011100
11. 00110000
12. 11111100
13. 00111010

まず、与えられた情報では、次の順序で 2 つのオフセット ビット、3 つのセット ビット、3 つのタグ ビットがあるように私には思えます (T=tag、S=set、O=offset): TTTSSSOO

例 (アドレス 1):

タグ=000 (0)、セット = 100 (4)、オフセット = 01 (1)

これが正しいと仮定すると、上記のアドレスを検索すると、次のようになります。

1. ミス、セット 4、ブロック 0 に保存
2. ミス、セット 2、ブロック 0 に保存
3. ミス、セット 7、ブロック 0 に保存
4. ミス、セット 2、ブロック 1 に格納
5. ミス、セット 6、ブロック 0 に保存
6. ミス、セット 0、ブロック 0 に保存
7. ミス、セット 2、ブロック 0 に格納 (ブロック 0 は LRU でしたが、ブロック 1 は LRU になります)
8. ミス、セット 0、ブロック 1 に保存
9. セット 2、ブロック 1 のヒット数
10. ミス、セット 7、ブロック 1 に格納
11. ミス、セット 6、ブロック 1 に格納
12. ミス、セット 7、ブロック 0 に格納 (ブロック 0 は LRU でしたが、ブロック 1 は LRU になります)
13. ミス、セット 6、ブロック 0 に格納 (ブロック 0 は LRU でしたが、ブロック 1 は LRU になります)

キャッシュの最終的な内容は次のようになります。

セット 0: 01000010、00000000

セット 1: 空、空

セット 2: 10001001、01001000

セット 3: 空、空

セット 4: 00010001、空

セット 5: 空、空

セット 6: 00111010、00110000

セット 7: 11111100、00011100

私はこれに非常に苦労しているので、誰かが私が正しい軌道に乗っているかどうかを教えてくれることを願っています. これらが問題ないように見える場合は、同じ演習を試してみたいと思います。

EDIT1: 新しいアドレス。

1. 000_100_01
2. 000_010_01
3. 000_001_10
4. 000_001_01
5. 001_010_11
6. 000_001_00
7. 000_010_11
8. 000_010_01
9. 001_110_00
10. 000_100_11
11. 000_000_01
12. 000_101_11
13. 011_010_11

どちらが好きですか：

1. ミス、セット 4 ブロック 0 に格納
2. ミス、セット 2 ブロック 0 に格納
3. ミス、セット 1 ブロック 0 に格納
4. ミス、セット 1 ブロック 1 に格納、ブロック 0 が LRU になる
5. ミス、セット 2 に格納 ブロック 1、ブロック 0 が LRU になる
6. ミス、セット 1 ブロック 0 に格納、ブロック 1 が LRU になる
7. ミス、セット 2 ブロック 0 に格納、ブロック 1 が LRU になる
8. ヒット、セット 2 ブロック 0 が LRU になる
9. ミス、セット 6 ブロック 0 に格納
10. ミス、セット 4 ブロック 1 に格納
11. ミス、セット 0 ブロック 0 に格納
12. ミス、セット 5 ブロック 0 に格納
13. ミス、セット 2 ブロック 0 に格納、ブロック 1 が LRU になる

I often do interactive work in Python that involves some expensive operations that I don't want to repeat often. I'm generally running whatever Python file I'm working on frequently.

If I write:

I get this behavior:

That is, rerunning the file clears the cache. This works:

but when the function is long it feels strange to have its definition inside a try block. I can do this instead:

but it feels pretty contrived (for example, in calling the decorator without an '@' sign)

Is there a simple way to handle this, something like:

?

私のHacker's Delightのコピーは家にあり、私が見つけたWebリソースはこの詳細について明確ではありません.

よく知られている「行と列の正方形」アルゴリズムを使用して、次の 8 レベルの LRU を作成しました。（もっと良い名前はありますか？）。

最も使用頻度の低い行はすべてゼロになるという私の仮定の確認をお願いします。うまくいくようですが、満足のいくものであることを証明する数学がありません。

それで、これは正しいですか？または、各行の最小ハミング重みを計算する必要がありますか?

LRU ページ置換をシミュレートする関数を作成しようとしています。私は LRU をよく理解していますが、コーディングに問題があります。次のものが LRU 関数に渡されます。ユーザーは、サイズ 20 の refString という配列に格納されている # の 1 ～ 9 の 20 文字の参照文字列を指定します。ユーザーが入力したフレーム数 (1 ～ 7) は、変数 numFrames に格納されます。最後に、frame と呼ばれるサイズ 7 の配列が渡されます。

これが私が持っているコードです。近い数を取得していますが、完全ではありません。多分誰かが助けることができます！

Web API のクライアント ラッパーであるPython クライアント ライブラリを開発しました。あると便利な機能は、ローカル キャッシュ メカニズムです。これにより、ライブラリ クライアントが Web API でまったく同じ要求を呼び出すときに、時間と帯域幅を節約できます。さまざまな時期に。

要件はほとんどありません

1. キャッシュを開発し (外部ライブラリなし)、Python 2.6/2.7 env を実行する必要があります
2. ライブラリは統一されたインターフェースを提供するため、依存性が注入される外部キャッシュメカニズム (例: memcached) ラッパーを使用できます。
3. キャッシュはスレッドセーフである必要があります
4. キャッシュされるコンテンツは、Web API 応答の JSON ペイロードになります。
5. Web API によって提供されるデータは、時間ごとに異なります。たとえば、現在観測されている都市の天気は 1 時間ごとに変化する可能性がありますが、15 日間の天気予報は 5 日ごとに変化する可能性があります。

使用できる最も単純なアルゴリズムは何ですか?

私は LRU (最近使用されていない) アルゴリズムについて考えていましたが、他の代替案を評価できると思います - 私はキャッシュの専門家ではありません!

これは簡単かもしれませんが、私はそれを理解することができません。シーケンシャルフラッディングの例を誰か教えてもらえますか? 私が読んでいる教科書やインターネットの情報源には、

バッファ フレームの数がファイル内のページ数よりも少ない場合、ファイルのすべてのページを読み取ることになります。これは、LRU と繰り返されるスキャンによって引き起こされる厄介な状況です。

# フレーム < ファイル内の # ページ。

LRU を使用すると、ファイルをスキャンするたびに、ファイルのすべてのページが読み取られます。」

しかし、それは正確には何ですか？なぜそれが起こるのですか？

オブジェクトを格納する標準の LRUCache を Android に実装しました。各キーは、格納されたオブジェクトに関連付けられた一意の ObjectId です。私の問題は、キャッシュからオブジェクトを取得する唯一の方法は、ObjectId (イテレータなし) によるものであることです。getAll() メソッドを実装する最良の方法は何ですか? もう 1 つのオプションは、すべての ObjectId をリストのどこかに格納することです。これにより、リストを反復処理してすべてのオブジェクトを取得できますが、すべての ObjectId を保持する最良の方法は何でしょうか?

ありがとう！