0

hashtable+linked list を使用して LRU を実装しました。

ハッシュ テーブルには連鎖があります。コードの構造は次のとおりです。

struct Node{
int value;
struct Node *next;
struct Node* head;
struct Node* tail;

};



struct Node* lruhashtable[10];
struct Node* trackHead;
struct Node* trackTail;

trackHead および trackTail ポインターは、挿入のシーケンスを追跡するためのものです。これは、最も使用頻度の低い要素を削除するために使用されます。1 つではなく、複数の交換ポリシーが使用されていると思います。したがって、LRUは何かの組み合わせで使用されます。したがって、要素に再度アクセスするときに要素を LRU から削除する場合は、LRU から要素を削除する必要があります。

本質的に私はシーケンス全体を維持していますが、何百万ものエントリがある場合、それは悪いことです。プライオリティ キュー + ハッシュテーブルを使用する以外に、これを改善する方法はありますか

4

1 に答える 1

0

シーケンス全体を維持する必要があり、それを正しく行う限り、何百万ものエントリがあっても悪くありません。

重要なのは、他のハッシュテーブルと同じようにハッシュテーブルを作成することです。次に、この最近使用されたノードを見つけるためにリンク リストを反復処理する代わりに、ハッシュ テーブル内の参照を使用するだけです。真ん中からリンクを外して、前に移動します。

リンクされたリストからの要素の削除は、開始するノードを見つけることができれば、一定時間の操作です。ハッシュテーブルがない場合は、反復する必要があります (線形時間) が、ハッシュテーブルがあるため、反復する必要はありません。

于 2012-10-11T23:04:26.180 に答える