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

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

王林

リリース： 2023-06-19 20:28:38

オリジナル

1736 人が閲覧しました

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

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

二重リンクリストとハッシュテーブルを使用した 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 は、それぞれ二重リンクされたノードの移動および削除操作に対応します。リスト、特に実装はコードで指定されます。

キャッシュの更新と削除

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 サイトの他の関連記事を参照してください。