pelaksanaan golang lru

Algoritma LRU (Paling Kurang Digunakan) ialah strategi penggantian cache biasa. Apabila cache mencapai had pratetap, cache secara automatik akan menghapuskan data yang paling kurang digunakan baru-baru ini untuk mengosongkan ruang.

Di Golang, kami boleh menggunakan senarai terpaut dua kali dan jadual cincang untuk melaksanakan cache LRU. Dalam artikel ini, kami akan menerangkan cara melaksanakan cache LRU menggunakan dua struktur data ini.

Fungsi senarai pautan berganda adalah untuk mengekalkan susunan data cache Setiap kali data baharu dimasukkan atau data diakses, data akan dimajukan. Pada masa yang sama, apabila cache mencapai had atas, kami boleh memadamkan data yang paling kurang digunakan baru-baru ini daripada penghujung senarai terpaut.

Fungsi jadual cincang adalah untuk mempercepatkan carian data Setiap kali data diakses, kami boleh mencari data cache yang sepadan dengan cepat melalui indeks data yang disimpan dalam jadual cincang. Oleh itu, kami akan beroperasi pada jadual cincang semasa pelaksanaan.

Seterusnya, kami akan menerangkan cara melaksanakan cache LRU berdasarkan senarai terpaut dua kali dan jadual cincang. Kami mentakrifkan struktur LRUCache dan mengisytiharkan penunjuk kepala dan ekor senarai terpaut, serta peta jadual cincang dan kapasiti cache.

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

Seterusnya, kami akan mentakrifkan struktur nod senarai terpaut dua kali.

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

Di sini, kami menggunakan prev dan next untuk mewakili penunjuk pendahulu dan pengganti nod masing-masing, dan kunci dan nilai masing-masing mewakili pasangan nilai kunci nod.

Seterusnya, kami akan mentakrifkan pembina NewLRUCache LRUCache dan lulus dalam kapasiti kapasiti cache.

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

Dalam pembina, kami akan memulakan jadual cincang dan kapasiti cache.

Seterusnya, kami akan mentakrifkan kaedah Dapatkan dan Letakkan LRUCache untuk mengakses dan menyimpan data.

Pelaksanaan kaedah Get:

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

Mula-mula, kami mencari sama ada data yang sepadan wujud daripada jadual cincang Jika wujud, alihkan nod ke kepala senarai terpaut dan kembalikan nod nilai simpanan. Jika tidak, -1 dikembalikan.

Berikut ialah pelaksanaan kaedah 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
}

Kaedah ini menerima elem penuding nod, yang digunakan untuk mengalihkan nod ke kepala senarai terpaut. Pertama, jika nod sudah berada di kepala senarai terpaut, sebaliknya, jika nod berada di ekor senarai terpaut, kemas kini penunjuk ekor senarai terpaut jika tidak, padamkan nod daripada senarai terpaut dan letakkan nod di kepala senarai terpaut.

Pelaksanaan kaedah letak:

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
        }
    }
}

Pertama, kami mencari sama ada data yang sepadan wujud dalam jadual cincang Jika wujud, kemas kini nilai yang disimpan dalam nod dan panggil kaedah moveToHead untuk mengalihkan nod Beralih ke kepala senarai terpaut. Jika tidak, buat nod baharu dan masukkannya di kepala senarai terpaut. Jika cache mencapai had atas yang dipratetap, padamkan nod ekor senarai terpaut dan data dalam jadual cincang.

Akhir sekali, kami meletakkan kod lengkap bersama-sama:

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
        }
    }
}

Dalam artikel ini, kami telah memperkenalkan cara untuk melaksanakan algoritma cache LRU menggunakan senarai terpaut dua kali dan jadual cincang. Melalui pelaksanaan algoritma ini, kami boleh mengurus cache dengan berkesan dan mengoptimumkan kecekapan capaian data.

Atas ialah kandungan terperinci pelaksanaan golang lru. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!