冷たい面接官は、時間をつぶすために LRU キャッシュ除去アルゴリズムを手作業で書くように私に依頼しました。

[[384337]]

この記事はWeChatの公開アカウント「Xiaolangmazhida」から転載したもので、著者はSimon Langです。この記事を転載する場合は、Xiaolangmazhida の公開アカウントにご連絡ください。

背景

効率性を追求する私たちの世界では、何かを待つときにとてもイライラするようです。Web ページを更新できないとイライラしますし、コンピューターがプログラムを実行するのが遅いとイライラします。では、私たちは何をすべきでしょうか? 技術の創造は私たちに役立つのではないでしょうか? 今日は、キャッシュの技術についてお話しし、私たちがよく知っているデータ構造、つまりリンクリストを使用して LRU キャッシュ削除アルゴリズムを実装します。

リンクリストを使用して LRU キャッシュ削除アルゴリズムを実装する方法を学ぶ前に、いくつかの質問を提起しましょう。それらについて慎重に考えてみましょう。質問は次のとおりです。

キャッシュとは何ですか？また、キャッシュは何をしますか？
キャッシュ除去戦略は何ですか?
リンクリストを使用して LRU キャッシュ削除アルゴリズムを実装する方法、その特性、および最適化する方法を教えてください。

さて、上記の質問に答えて次の研究に進みましょう。

1. キャッシュとは何ですか? また、その機能は何ですか?

キャッシュとは、簡単に言えば、データのコピーを保存して、後ですぐにアクセスできるようにすることです。コンピュータの使用シナリオを例に挙げてみましょう。CPU がメモリ内のデータにアクセスする場合、まずキャッシュを検索します。キャッシュが見つかった場合は、直接使用されます。キャッシュが見つからない場合は、メモリを検索する必要があります。

同様に、データベースアクセスのシナリオでは、プロジェクトシステムがデータベース内のデータの一部をクエリする必要がある場合、最初に要求でキャッシュをクエリできます。ヒットした場合は、キャッシュされた結果が直接返されます。ヒットしなかった場合は、データベースをクエリし、クエリ結果をキャッシュに格納します。次に要求されたときに、キャッシュがヒットした場合は、データベースを再度クエリせずに結果を直接返します。

上記の 2 つの例から、シナリオが何であっても、最初にキャッシュ、次にメモリ、次にキャッシュ、次にデータベースという順序があることがわかりました。しかし、キャッシュの存在はメモリ空間の一部を占有するため、キャッシュは空間を時間と交換する典型的な例であり、データのリアルタイム性を犠牲にしながらも、コンピュータの動作の高効率性を満たします。

よく考えてみると、私たちは日々の開発の中でキャッシュの例にかなり多く遭遇します。

オペレーティングシステムキャッシュ

ディスクのやり取りを減らす

データベースキャッシュ

データベースクエリを削減

Web サーバーキャッシュ

アプリケーションサーバーへのリクエストを減らす

クライアントブラウザキャッシュ

ウェブサイトへの訪問を減らす

2. キャッシュ除去戦略は何ですか?

キャッシュの本質は、スペースを時間と交換することであるため、キャッシュの容量は制限される必要があります。キャッシュがいっぱいになった場合、キャッシュ内のどのデータをクリアし、どのデータを保持する必要がありますか? これには、キャッシュ削除戦略を決定する必要があります。

実際、一般的に使用されているキャッシュ削除戦略は 3 つあります。先入れ先出し FIFO、一定期間にアクセスが最も少ないページを削除する (最も頻繁に使用されない LFU)、最も長い間使用されていないページを削除する (最も最近使用されていない LRU)

これらのアルゴリズムは、異なるレベルのキャッシュで実行された場合に効率が異なるため、特定のシナリオに基づいて選択する必要があります。

2.1 FIFOアルゴリズム

FIFO アルゴリズムは先入れ先出しアルゴリズムであり、多くの場合キューを使用して実装されます。キャッシュの設計原則は、データが最初にキャッシュに入った場合は、最初に削除されるというものです。

FIFOアルゴリズム

新しくアクセスされたデータは FIFO キューの最後に挿入され、キュー内のデータはキューの先頭から順番に移動します。

キューがいっぱいになったら、キューの先頭にあるデータを削除します

2.2 LRUアルゴリズム

LRU アルゴリズムは、データへの履歴アクセス数に基づいてデータを排除し、通常はリンクリストを使用して実装されます。キャッシュでは、データが最近アクセスされた場合、将来もアクセスされる可能性が高くなるという設計原則があります。

LRUアルゴリズム

新しく追加されたデータはリンクリストの先頭に挿入されます
キャッシュヒットが発生するたびに (つまり、キャッシュされたデータにアクセスするたびに)、データはリンクリストの先頭に移動されます。
リンクリストがいっぱいになると、リンクリストの末尾のデータは破棄されます。

2.3 LFUアルゴリズム

LFU アルゴリズムは、データの過去のアクセス頻度に基づいてデータを削除します。したがって、LFU アルゴリズムの各データブロックには参照カウントがあります。すべてのデータブロックは参照カウントに従ってソートされ、同じ参照カウントを持つデータブロックは時間順にソートされます。キャッシュでは、データが何度もアクセスされると、将来さらに頻繁にアクセスされるという原則に基づいて設計されています。

LFUアルゴリズム

新しく追加されたデータはキューの末尾に挿入されます (参照カウントは 1 です)。
キュー内のデータにアクセスした後、参照カウントが増加し、キューが並べ替えられます。
データを削除する必要がある場合は、ソートされたリスト内の最後のデータブロックを削除します。

3. リンクリストを使用してキャッシュ削除を実装する方法、その特徴、最適化する方法を教えてください。

上記の記事では、キャッシュと削除戦略の概念を理解しました。その中でも、LRUアルゴリズムは筆記試験/面接で頻繁にテストされます。秋に採用活動をしていたとき、多くの企業からこのアルゴリズムを手動で記述するように求められました。誰もが陥る落とし穴を避けるために、以下にLRUキャッシュ削除アルゴリズムを手動で記述してみましょう。

リンクリストには複数の形式があることは誰もが知っていますが、どれを選択すればよいのでしょうか?

3分ほど考えてみてください...

さあ、答えを発表しましょう！

実際、リンクリストは、接続構造の違いにより、単一リンクリスト、循環リンクリスト、二重リンクリストに分類できます。

単方向リンクリスト
- 各ノードには、後続ポインターという 1 つのポインターのみが含まれます。
- 単一リンクリストには、最初のノードと末尾のノードという 2 つの特別なノードがあります。最初のノードのアドレスはリンクリスト全体を表し、末尾のノードの後続ポインターは空のアドレス null を指します。
- パフォーマンス特性: ノードの挿入と削除の時間計算量は O(1) で、検索の時間計算量は O(n) です。
循環リンクリスト
- 末尾ノードの後続ポインターが最初のノードのアドレスを指していることを除いて、すべてが単一のリンクリストと一致しています。
- ジョセフ問題などの周期的な特性を持つデータを保存するのに適しています。
二重リンクリスト
- データの保存に加えて、ノードには前のノードアドレス（前任者ポインタprev）と次のノードアドレス（後任ポインタnext）を指す2つのポインタもあります。
- 最初のノードの先行ポインター prev と末尾ノードの後続ポインターは両方とも空のアドレスを指します。

二重リンクリストが単一リンクリストよりも優れている主な利点は、先行ノードの検索にかかる時間計算量が O(1) であるのに対し、単一リンクリストでは先頭ノードからゆっくりと下方向にしか検索できないため、依然として O(n) であることです。さらに、挿入と削除の最適化も行われます。

疑問が湧くかもしれません: 単一リンクリストの挿入と削除は O(1) ではないでしょうか?

はい、しかし一般的に、挿入や削除の操作を実行する場合、最初に検索してから挿入または削除する必要があります。実際には最初に O(n)、次に O(1) であることがわかります。

削除操作を実行する必要があるため、ノードを削除するには、ノード自体のポインタを取得するだけでなく、他の先行ノードのポインタを操作する必要があります。双方向リンクリストは先行ノードを直接見つけることができるため、操作時間の複雑さは O(1) になります。したがって、LRU キャッシュ削除アルゴリズムを実装するための構造として双方向リンクリストを使用する方が効率的です。

アルゴリズムのアイデア

キャッシュされたすべての値を格納するために二重リンクリストを維持し、最も古い値をリストの末尾に配置します。

アクセスされた値がリンクリスト内にある場合: リンクリスト内の値が検索され、削除され、その値がリンクリストの先頭に再度追加されます (リンクリスト内の値の順序が新しいものから古いものへとなるようにします)

アクセスされた値がリンクリストにない場合: リンクリストがいっぱいの場合: リンクリストの最後の値を削除し、追加する値をリンクリストの先頭に置きます。リンクリストがいっぱいでない場合: リンクリストの先頭に直接追加します。

3.1 LRUキャッシュ除去アルゴリズム

Geek Time Wang Zheng の「The Beauty of Data Structure and Algorithm」では、順序付き単一リンクリストを使用した LRU キャッシュ削除アルゴリズムが紹介されています。コードは次のとおりです。

パブリッククラスLRUBaseLinkedList<T> { 
 
    /**
     * デフォルトのリンクリスト容量
     */
    プライベートファイナルスタティック 整数DEFAULT_CAPACITY = 10; 
 
    /**
     * ヘッドノード
     */
    プライベート SNode<T> headNode; 
 
    /**
     * リンクリストの長さ
     */
    プライベート整数の長さ; 
 
    /**
     * リンクリスト容量
     */
    プライベート整数容量。 
 
パブリックLRUBaseLinkedList() {
        this.headNode = 新しい SNode<>();
        this.capacity = DEFAULT_CAPACITY;
        this.length = 0;
    } 
 
パブリックLRUBaseLinkedList(整数容量) {
        this.headNode = 新しい SNode<>();
        this.capacity = 容量;
        this.length = 0;
    } 
 
パブリックvoid add (T データ) {
        SNode preNode = findPreNode(データ); 
 
        // リンクリストに存在する場合は、元のデータを削除し、リンクリストの先頭に挿入します
        preNode がnullの場合
            要素最適化を削除します(preNode);
            intsertElemAtBegin(データ);
        }それ以外{
            長さ >= this.capacity の場合 {
                //末尾のノードを削除する
                要素の終了位置を削除します。
            }
            intsertElemAtBegin(データ);
        }
    } 
 
    /**
     * preNodeノードの次の要素を削除します
     *
     * @param プレノード
     */
    プライベートvoid deleteElemOptim(SNode preNode) {
        SNode temp = preNode.getNext();
        preNode.setNext( temp .getNext());
一時= null ;
        長さ- ;  
    } 
 
    /**
     * リンクリストの先頭にノードを挿入する
     *
     * @param データ
     */
    プライベートvoid intsertElemAtBegin(Tデータ) {
        SNodeの next = headNode.getNext();
        headNode.setNext(新しいSNode(データ、次));
        長さ++;
    } 
 
    /**
     * 見つかった要素の前のノードを取得します
     *
     * @param データ
     * @戻る 
     */
    プライベートSNode findPreNode(Tデータ) {
        SNode ノード = headNode;
        (node.getNext() != null ) の場合 {
            （data.equals(node.getNext().getElement())）の場合{
ノードを返します。
            }
            ノード = node.getNext();
        }
戻る ヌル;
    } 
 
    /**
     * 末尾のノードを削除する
     */
    プライベートvoid deleteElemAtEnd() {
        SNode ptr = headNode;
        // 空のリンクリストは直接返されます
        (ptr.getNext() == null )の場合{
戻る;
        } 
 
        // 最後から2番目のノード
        (ptr.getNext().getNext() != null ) の場合 {
            ptr = ptr.getNext();
        } 
 
        SNode tmp = ptr.getNext();
        ptr.setNext( null );
        tmp = null ;
        長さ- ;  
    } 
 
    プライベートvoid printAll() {
        SNode ノード = headNode.getNext();
        while (ノード != null ) {
            システム.out.print (node.getElement() + "," );
            ノード = node.getNext();
        }
        System.out.println( ) ;
    } 
 
パブリッククラスSNode<T> { 
 
        プライベート T 要素。 
 
        プライベート SNode次; 
 
パブリックSNode(T要素) {
            this.element = 要素;
        } 
 
パブリックSNode(T要素、SNode次){
            this.element = 要素;
            this.next =次へ;
        } 
 
パブリックSNode() {
            this.next = null ;
        } 
 
パブリックT getElement() {
要素を返します。
        } 
 
パブリックvoid setElement(T 要素) {
            this.element = 要素;
        } 
 
パブリックSNode getNext() {
戻る 次;
        } 
 
パブリックvoid setNext(SNode next ) {
            this.next =次へ;
        }
    } 
 
公共 静的void main(String[] args) {
        LRUBaseLinkedList リスト = 新しい LRUBaseLinkedList();
        スキャナー sc = new Scanner( System.in );
        （真）の間{
            リストに追加します(sc.nextInt());
            リストを印刷します。
        }
    }
 }

このコードは、キャッシュがいっぱいかどうかに関係なく、リンクリストをトラバースする必要があるため、このリンクリストの実装に基づくキャッシュアクセスの時間計算量は O(n) です。

3.2 ハッシュテーブルを使用して LRU を最適化する

実際、このアイデアはさらに最適化できます。単方向リンクリストを双方向リンクリストに置き換え、ハッシュテーブルを導入することができます。

双方向リンクリストは先行検索をサポートし、操作の時間計算量がO(1)であることを保証します。
各データの場所を記録するハッシュテーブルを導入し、キャッシュアクセスの時間計算量をO(1)に削減する

ハッシュテーブルは検索が高速ですが、データには固定の順序がありません。一方、リンクリストには順序があります。挿入と削除は高速ですが、検索は低速です。これらを組み合わせることで、新しいデータ構造 LinkedHashMap を形成できます。

ハッシュテーブル + 二重リンクリスト

Likou の質問 146 - LRU キャッシュメカニズムを練習に使用できます。質問の画像は次のとおりです。

トピック：

既知のデータ構造を使用して、LRU (最近最も使われていない) キャッシュメカニズムを設計および実装します。

LRUCache クラスを実装します。

LRUCache(int capacity) 正の整数を容量としてLRUキャッシュを初期化します。

int get(int key) キーワードキーがキャッシュ内に存在する場合はキーワードの値を返し、存在しない場合は -1 を返します。

void put(int key, int value) キーワードがすでに存在する場合は、そのデータ値を変更します。キーワードが存在しない場合は、「キーワード値」セットを挿入します。キャッシュの容量がいっぱいになると、新しいデータ値のためのスペースを確保するために、新しいデータを書き込む前に、最も最近使用されていないデータ値を削除する必要があります。

アイデア:

私たちのアイデアはハッシュテーブル+双方向リンクリストです

ハッシュテーブルはO(1)の時間計算量要件を満たすために使用され、二重リンクリストは順序を格納するために使用されます。
ハッシュテーブルキータイプ:
値に加えて、二重リンクリストのノードにはキーも含める必要があります。これは、最も長い未使用データを削除するときに、リンクリストを使用してハッシュマップ内で削除する必要があるキーと値のペアを見つける必要があるためです。
いくつかの操作: 双方向リンクリストでは、後ろのノードは最後にアクセスされたノードです。
- 新しく追加されたノードはリンクリストの末尾に配置されます。addNodeToLast(node)
- 容量が上限に達した場合は、最も長い未使用データを削除します。removeNode(head.next)
- データが新しくアクセスされた場合（新しい値で取得または配置された場合など）、ノードをリンクリストの末尾に移動します（moveNodeToLast(node)）。
操作の便宜上、双方向リンクリストの先頭と末尾にそれぞれヘッドノードとテールノードが定義されます。

コード

クラスLRUCache {
    プライベートint容量;
    プライベート HashMap< Integer , ListNode> ハッシュマップ;
    プライベートListNodeヘッド;
    プライベートListNodeテール; 
 
    プライベートクラスListNode{
整数 鍵;
整数値;
        リストノード前;
        ListNode次;
パブリックリストノード(){
        }
パブリックListNode( int  キー、 int値){
            this.key =キー;
            this.val = val;
        }
    } 
 
パブリックLRUCache( int容量) {
        this.capacity = 容量;
        ハッシュマップ = 新しい HashMap<>();
        ヘッド = 新しいListNode();
        末尾 = 新しいListNode();
        ヘッドの次= テール;
        末尾.prev = 先頭;
    } 
 
    プライベートvoid removeNode(ListNodeノード){
        ノードを次のノードにドラッグします。
        ノードを次のノードにドラッグします。
    } 
 
    プライベート void addNodeToLast(ListNode ノード){
        ノードを末尾に追加します。
        ノードを次のノードにドラッグします。
        ノードの次の行にポインタを置きます。
        tail.prev=ノード;
    } 
 
    プライベート void moveNodeToLast(ListNode ノード){
        ノードを削除します。
        ノードを最後に追加します。
    } 
     
公共  int get( int  鍵） {
        if(hashmap.containsKey(キー)){
            ListNode ノード = hashmap.get(キー);
            ノードを最後のノードに移動します。
 node.valを返します。
        }それ以外{
 -1 を返します。
        }
    } 
     
パブリックvoid put( int  キー、 int値）{
        if(hashmap.containsKey(キー)){
            ListNode ノード = hashmap.get(キー);
            ノード.val = 値;
            ノードを最後のノードに移動します。
戻る;
        }
        if(ハッシュマップのサイズ() == 容量){
            ハッシュマップを削除します( head.next.key );
            ノードを削除します( head.next );
        } 
 
        ListNode ノード = 新しい ListNode(キー、 値 );
        hashmap.put(キー, ノード );
        ノードを最後に追加します。
    }
 }