Golang での LRU キャッシュ アルゴリズムの詳細な分析。

効率的で安定したシステムを開発する場合、キャッシュは不可欠な最適化手法であり、最も一般的なキャッシュ アルゴリズムの 1 つは LRU アルゴリズムです。 LRU アルゴリズムは「最も最近使用されていない」アルゴリズムであり、キャッシュ内の各要素の使用状況を記録することで最も最近使用されていない要素を排除し、キャッシュの利用効率を最大化します。 Golang では、LRU キャッシュ アルゴリズムも簡単に実装できます。

この記事では、Golang での LRU キャッシュ アルゴリズムの実装について詳しく紹介します。これには、二重リンク リストとハッシュ テーブルを使用して実装する方法、キャッシュを更新および削除する方法、および実行方法が含まれます。スレッドセーフな操作。

1. 二重リンク リストとハッシュ テーブルを使用した LRU キャッシュ アルゴリズムの実装

Golang では、二重リンク リストは、LRU キャッシュ アルゴリズムを簡単に実装できる基本的なデータ構造です。 。具体的な実装方法は、キャッシュ内の各要素をノードにカプセル化し、二重リンク リストを使用してこれらのノードを管理することです。同時に、ハッシュ テーブル (マップ) を使用して各ノードの位置を記録し、迅速な検索と更新を容易にします。

以下は、Golang で LRU キャッシュ アルゴリズムを実装するための基本的なコード構造です。

type Node struct {
    Key  int
    Val  int
    Prev *Node
    Next *Node
}

type LRUCache struct {
    Size       int
    Capacity   int
    Cache      map[int]*Node
    Head, Tail *Node
}

func Constructor(capacity int) LRUCache {
    head, tail := &Node{}, &Node{}
    head.Next, tail.Prev = tail, head
    return LRUCache{
        Cache:     make(map[int]*Node),
        Capacity:  capacity,
        Size:      0,
        Head:      head,
        Tail:      tail,
    }
}

func (l *LRUCache) Get(key int) int {
    if node, ok := l.Cache[key]; ok {
        l.MoveToHead(node)
        return node.Val
    }
    return -1
}

func (l *LRUCache) Put(key, val int) {
    if node, ok := l.Cache[key]; ok {
        node.Val = val
        l.MoveToHead(node)
        return
    }
    node := &Node{Key: key, Val: val}
    l.Cache[key] = node
    l.AddToHead(node)
    l.Size++
    if l.Size > l.Capacity {
        removed := l.RemoveTail()
        delete(l.Cache, removed.Key)
        l.Size--
    }
}

func (l *LRUCache) MoveToHead(node *Node) {
    l.RemoveNode(node)
    l.AddToHead(node)
}

func (l *LRUCache) RemoveNode(node *Node) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (l *LRUCache) AddToHead(node *Node) {
    node.Prev = l.Head
    node.Next = l.Head.Next
    l.Head.Next.Prev = node
    l.Head.Next = node
}

func (l *LRUCache) RemoveTail() *Node {
    node := l.Tail.Prev
    l.RemoveNode(node)
    return node
}

上記のコードでは、LRUCache は Cache を含む構造です。 ハッシュ テーブル、Head ポインターおよび Tail ポインター。二重リンク リストの先頭ノードと末尾ノード、およびキャッシュ内の各要素の位置を記録するために使用されます。このうち、Cache ハッシュ テーブルのキーは要素のキー、値は要素のノード ポインタであり、Head は二重リンクの先頭ノードを指します。リスト、Tail は末尾ノードを指します。 Size は現在のキャッシュ内の要素の数を示し、Capacity はキャッシュの最大容量を示します。

Constructor 関数では、空の二重リンク リストを初期化し、LRUCache 構造体を返します。 Get 関数では、まず指定された要素がキャッシュに存在するかどうかを確認し、存在する場合はその要素をリンク リストの先頭に移動してその値を返し、存在しない場合は -1 を返します。 Put 関数では、まず指定された要素がキャッシュに存在するかどうかを判断し、存在する場合は要素の値を更新して先頭に移動し、存在しない場合は新しい要素を追加してキャッシュに追加します。頭。キャッシュ サイズが最大容量を超える場合、最も最近使用されていない要素が削除され、ハッシュ テーブルから削除されます。

MoveToHead、RemoveNode、AddToHead、および RemoveTail は、それぞれ二重リンクされたノードの移動および削除操作に対応します。リスト、特に実装はコードで指定されます。

2. キャッシュの更新と削除

LRU キャッシュ アルゴリズムを使用する場合、キャッシュ内の要素のアクセス シーケンスが、最後に使用された順序で配置されていることを確認する必要があります。時間順。要素がキャッシュから読み取られるか更新されるときは常に、その要素をリンク リストの先頭に移動する必要があります。同時に、キャッシュ サイズが最大容量を超えると、最も最近使用されていない要素、つまり最後の要素が移動されます。リンクされたリストでは、削除する必要があります。

次は、MoveToHead 関数の実装です:

func (l *LRUCache) MoveToHead(node *Node) {
    l.RemoveNode(node)
    l.AddToHead(node)
}

MoveToHeadこの関数は、キャッシュ ノード node# へのポインターを受け取ります。 ## パラメータとして、まずリンク リストからノードを削除し、次にリンク リストの先頭にノードを追加します。

次は、

RemoveTail 関数の実装です:

func (l *LRUCache) RemoveTail() *Node {
    node := l.Tail.Prev
    l.RemoveNode(node)
    return node
}

RemoveTailこの関数は、リンク リストの最後のノードを返し、そのノードを削除しますリンクリストから削除します。

スレッド セーフな操作

マルチスレッド環境では、LRU キャッシュ操作のスレッド セーフを確保する必要があります。これを行うには、同期パッケージで提供されるミューテックスを使用できます。具体的な方法は、キャッシュ操作を必要とする関数にミューテックス ロック操作を追加して、キャッシュ上での読み取りと書き込みの同時操作を回避することです。以下は、Golang で LRU キャッシュ アルゴリズムのスレッド セーフ バージョンを実装するためのコード構造です。

type LRUCache struct {
    Size       int
    Capacity   int
    Cache      map[int]*Node
    Head, Tail *Node
    Mutex      sync.Mutex
}

func (l *LRUCache) Get(key int) int {
    l.Mutex.Lock()
    defer l.Mutex.Unlock()

    ...
}

func (l *LRUCache) Put(key, val int) {
    l.Mutex.Lock()
    defer l.Mutex.Unlock()

    ...
}

...

上記のコードでは、

Mutex を構造 LRUCache に追加しました。 キャッシュ操作でミューテックスを同期するためのメンバー。キャッシュ操作を実行する前に、ミューテックス ロックを取得する必要があります。いずれの場合も、キャッシュを読み取るか変更するかにかかわらず、ミューテックスを解放する必要があります。

概要

この記事では、Golang での LRU キャッシュ アルゴリズムの実装について紹介します。これには、実装のための二重リンク リストとハッシュ テーブルの使用、キャッシュの更新が含まれます。削除、およびスレッドセーフ操作。 LRU キャッシュ アルゴリズムは、実際の開発で広く使用されているシンプルで効率的なキャッシュ アルゴリズムです。 Golang を使用してキャッシュ アプリケーションを作成する場合、LRU キャッシュ アルゴリズムを使用して、実際のニーズに応じてシステムのパフォーマンスと安定性を向上させることができます。

以上がGolang での LRU キャッシュ アルゴリズムの詳細な分析。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。