Bagaimana untuk melaksanakan sistem cache algoritma LRU dalam golang

LRU (Kurang Terbaharu Digunakan) ialah algoritma caching Ia boleh cache data yang digunakan baru-baru ini dahulu dan menghapuskan data yang tidak digunakan untuk masa yang lama di bawah kapasiti cache terhad, dengan itu mencapai penggunaan ruang cache yang cekap dan meningkatkan kelajuan akses data. .

Bahasa Go (golang) ialah bahasa pengaturcaraan yang cekap yang digemari oleh pembangun kerana keupayaan konkurensi dan pengurusan memori yang sangat baik. Dalam artikel ini, kami akan melaksanakan sistem caching untuk algoritma LRU dan menggunakan bahasa Go untuk melaksanakannya.

Idea reka bentuk

Sebelum melaksanakan sistem cache LRU, kita perlu menentukan keperluan sistem dan idea reka bentuk.

Pertama sekali, kami memerlukan struktur data untuk menyimpan data cache ini perlu menyokong akses pantas dan kemas kini, dan juga perlu menyokong penghapusan data mengikut masa penggunaan. Struktur data yang biasa digunakan termasuk senarai terpaut, jadual cincang, senarai terpaut dua kali, dsb. Antaranya, senarai terpaut dua kali ialah pilihan terbaik untuk melaksanakan algoritma LRU.

Kedua, kami memerlukan beberapa operasi untuk mengakses dan mengemas kini struktur data ini. Operasi biasa termasuk: membaca data cache, menulis data cache, mengemas kini data cache, memadam data cache, dsb.

Akhir sekali, kami memerlukan beberapa strategi caching untuk mengawal saiz cache dan menghalang cache daripada mengisi keseluruhan memori. Strategi yang biasa digunakan termasuk FIFO (masuk pertama, keluar dahulu), LFU (paling jarang digunakan), LRU (paling kurang digunakan baru-baru ini), dll. Antaranya, LRU ialah pilihan terbaik untuk melaksanakan sistem cache LRU.

Pelaksanaan Kod

Sekarang kami mempunyai idea reka bentuk yang jelas, kami boleh mula melaksanakan sistem cache LRU kami. Kodnya adalah seperti berikut:

package lruCache

import "container/list"

type Cache struct {
    MaxBytes  int64
    nBytes    int64
    ll        *list.List
    cache     map[string]*list.Element
    OnEvicted func(key string, value Value)
}

type entry struct {
    key   string
    value Value
}

type Value interface {
    Len() int
}

func (c *Cache) Add(key string, value Value) {
    if e, ok := c.cache[key]; ok {
        c.ll.MoveToFront(e)
        kv := e.Value.(*entry)
        c.nBytes += int64(value.Len()) - int64(kv.value.Len())
        kv.value = value
    } else {
        ele := c.ll.PushFront(&entry{key, value})
        c.cache[key] = ele
        c.nBytes += int64(len(key)) + int64(value.Len())
    }
    for c.MaxBytes != 0 && c.MaxBytes < c.nBytes {
        c.RemoveOldest()
    }
}

func (c *Cache) Get(key string) (value Value, ok bool) {
    if ele, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ele)
        kv := ele.Value.(*entry)
        return kv.value, true
    }
    return
}

func (c *Cache) RemoveOldest() {
    ele := c.ll.Back()
    if ele != nil {
        c.ll.Remove(ele)
        kv := ele.Value.(*entry)
        delete(c.cache, kv.key)
        c.nBytes -= int64(len(kv.key)) + int64(kv.value.Len())
        if c.OnEvicted != nil {
            c.OnEvicted(kv.key, kv.value)
        }
    }
}

Contoh Penggunaan

Kini, kami telah melaksanakan sistem cache LRU yang mudah. Kita boleh menggunakannya melalui kod sampel berikut:

package main

import (
    "fmt"
    "go-lru-cache/lruCache"
)

type stringValue string

func (s stringValue) Len() int {
    return len(s)
}

func main() {
    cache := lruCache.Cache{
        MaxBytes: 1000,
        OnEvicted: func(key string, value lruCache.Value) {
            fmt.Printf("key=%s, value=%s is evicted\n", key, value)
        },
    }
    cache.Add("key1", stringValue("123"))
    cache.Add("key2", stringValue("456"))
    cache.Add("key3", stringValue("789"))
    if value, ok := cache.Get("key1"); ok {
        fmt.Println(value.(stringValue))
    }
    cache.Add("key4", stringValue("101"))
    fmt.Printf("cache.Len() = %d\n", cache.Len())
    cache.RemoveOldest()
    fmt.Printf("cache.Len() = %d\n", cache.Len())
}

Dalam kod sampel di atas, kami mentakrifkan jenis stringValue dan melaksanakan antara muka Value untuk mewakili nilai dalam cache. Kemudian, kami mencipta sistem cache LRU dan menambah 4 item cache, dengan MaxBytes mewakili kapasiti maksimum cache. Seterusnya, kami memperoleh nilai yang sepadan dengan Get dalam cache melalui kaedah key1, kemudian tambah item cache baharu, dan akhirnya padam item cache tertua.

Ringkasan

Setakat ini, kami telah berjaya melaksanakan sistem cache LRU. Melalui artikel ini, kami bukan sahaja mempelajari pelaksanaan algoritma cache LRU, tetapi juga mempelajari cara menggunakan bahasa Go untuk melaksanakan sistem cache. Dalam pembangunan sebenar, penggunaan rasional sistem cache boleh meningkatkan prestasi program dengan ketara dan mengurangkan beban sistem. Oleh itu, sistem caching adalah salah satu kemahiran penting yang harus difahami dan dikuasai oleh setiap pembangun.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan sistem cache algoritma LRU dalam golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!