1

現在、次のようなカスタム クラスの配列があります。

Phy[] memory = new Phy[256];

私のPhyクラス内には、次の機能があります。

  • タイムスタンプ取得 (タイムスタンプを返す)
  • タイムスタンプの更新 (システム時間を使用し、1970 年以降のミリ秒を取得して設定します)

LRU クラスを見つけるための LRU 部分に関しては、次のようにします。

public int getLeastRecentlyUsed(){
    long leastUsed = memory[0].getTimeStamp();
    int  leastUsedPosition = 0;
    for(int i = 0; i < memory.length; i++){
        if(memory[i].getTimeStamp() < leastUsed){
            leastUsed = memory[i].getTimeStamp();
            leastUsedPosition = i;
        }
    }
    return leastUsedPosition;
}

これは基本的に最も古いタイムスタンプを探します。

私が今気付いた問題は、プロセッサが MS でこれらの操作の多くを行うことができ、役に立たないアルゴリズムを残すことです。

これを並べ替えるにはどうすればよいですか?

4

3 に答える 3

2

これにはタイムスタンプは必要ありません。使用するたびに、各項目をリストの先頭に移動するだけです。その場合、LRU アイテムは平均してリストの最後にあります。

Knuth volume 1 には、真の LRU を提供しないが、時間内に非常に適切な近似値に落ち着くかなり優れたアルゴリズムもあります。それは単にビットのリングで構成されています。アクセスするたびにアイテムのビットを設定し、空いているスロットを探すときにリングをスキャンし、すでにクリアされているビットが見つかるまでセットされたビットをクリアします。つまり、リングの周りで少なくとも 1 回は使用されていません。次回スキャンするときは、今回止めたところからスタート。

于 2013-02-21T12:29:31.967 に答える
1

タイムスタンプの代わりに、各'phy'オブジェクトに一意の値を指定します。この値は、割り当てられるたびに増加します。

したがって、次のようなことを行います。

class phy {
   private static int uniqueIdentifier = 0;

   private int timestamp;

   // Or give it a new (proper) name
   void updateTimestamp() {
       timestamp = uniqueIdentifier;
       uniqueIdentifier++;
   }
}

'タイム'スタンプを更新するたびに、新しい（より高い/最も高い）番号を割り当てます。これを使用して、最も最近使用されていない'phy'を見つけることができます。

注：複数のスレッドがある場合はuniqueIdentifier、同時にアクセスできないようにするために同期が必要になります（結果として一意でないtimestamp値になります）。

于 2013-02-21T12:32:24.150 に答える
1

LinkedHashMapを使用して実装してみてはどうでしょうか。

これとこれをチェックして、実装方法の例を確認してください

于 2013-02-21T12:33:30.700 に答える