golang lruの実装

LRU (最も最近使用されていない) アルゴリズムは、一般的なキャッシュ置換戦略です。キャッシュが事前に設定された制限に達すると、キャッシュは最も最近使用されていないデータを自動的に削除して、スペースを解放します。

Golang では、二重リンク リストとハッシュ テーブルを使用して LRU キャッシュを実装できます。この記事では、これら 2 つのデータ構造を使用して LRU キャッシュを実装する方法について説明します。

二重リンク リストの機能は、キャッシュされたデータの順序を維持することであり、新しいデータが挿入されるか、データにアクセスされるたびに、データは進みます。同時に、キャッシュが上限に達した場合、リンクされたリストの最後から最も最近使用されていないデータを削除できます。

ハッシュ テーブルの機能は、データの検索を高速化することです。データにアクセスするたびに、ハッシュ テーブルに格納されているデータ インデックスを通じて、対応するキャッシュされたデータを迅速に見つけることができます。したがって、実装時にはハッシュ テーブルを操作します。

次に、二重リンクリストとハッシュテーブルに基づいたLRUキャッシュの実装方法について説明します。 LRUCache 構造を定義し、リンク リストの先頭ポインタと末尾ポインタ、およびハッシュ テーブル マップとキャッシュ容量を宣言します。

type LRUCache struct {
    head, tail *entry  // 链表头和链表尾指针
    cache      map[int]*entry  // 哈希表存储缓存中的数据
    capacity   int     // 缓存容量
}

次に、二重リンクリストノードの構造を定義します。

type entry struct {
    key, value int        // 存储节点的键值对
    prev, next *entry    // 前驱和后继指针
}

ここでは、prev と next を使用してそれぞれノードの先行ポインタと後続ポインタを表し、key と value はそれぞれノードのキーと値のペアを表します。

次に、LRUCacheのコンストラクターNewLRUCacheを定義し、キャッシュ容量capacityを渡します。

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

コンストラクターでは、ハッシュテーブルとキャッシュ容量を初期化します。

次に、データにアクセスして保存するための LRUCache の Get メソッドと Put メソッドを定義します。

Getメソッドの実装:

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

まず、ハッシュテーブルから該当するデータが存在するかどうかを調べ、存在する場合は、そのノードを連結リストの先頭に移動し、そのノードを返します。保管価値。それ以外の場合は、-1 が返されます。

次は、moveToHead メソッドの実装です。

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

このメソッドは、ノードをリンク リストの先頭に移動するために使用されるノード ポインター要素を受け取ります。まず、ノードがすでにリンク リストの先頭にある場合は戻り、ノードがリンク リストの末尾にある場合は、リンク リストの末尾ポインタを更新します。そうでない場合は、リンク リストからノードを削除し、ノードをリンクされたリストの先頭に置きます。

Put メソッドの実装:

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

まず、ハッシュ テーブルから該当するデータが存在するかどうかを確認し、存在する場合はノードに格納されている値を更新し、moveToHead メソッドを呼び出します。ノードの移動 リンクされたリストの先頭に移動します。それ以外の場合は、新しいノードを作成し、リンクされたリストの先頭に挿入します。キャッシュがあらかじめ設定した上限に達した場合は、リンクリストの末尾ノードとハッシュテーブルのデータを削除します。

最後に、完全なコードをまとめました:

type LRUCache struct {
    head, tail *entry
    cache      map[int]*entry
    capacity   int
}

type entry struct {
    key, value int
    prev, next *entry
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

この記事では、二重リンク リストとハッシュ テーブルを使用して LRU キャッシュ アルゴリズムを実装する方法を紹介しました。このアルゴリズムの実装により、キャッシュを効果的に管理し、データ アクセス効率を最適化できます。

以上がgolang lruの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。