Analisis terperinci algoritma cache LRU di Golang.

Apabila membangunkan sistem yang cekap dan stabil, caching merupakan kaedah pengoptimuman yang amat diperlukan Salah satu algoritma caching yang paling biasa ialah algoritma LRU. Algoritma LRU ialah algoritma "paling kurang digunakan" Ia boleh menghapuskan elemen yang paling kurang digunakan baru-baru ini dengan merekodkan penggunaan setiap elemen dalam cache untuk memaksimumkan kecekapan penggunaan cache. Di Golang, algoritma cache LRU juga boleh dilaksanakan dengan mudah.

Artikel ini akan memperkenalkan secara terperinci pelaksanaan algoritma cache LRU di Golang, termasuk cara menggunakan senarai terpaut dua kali dan jadual cincang untuk melaksanakannya, cara mengemas kini dan menghapuskan cache dan cara melaksanakannya operasi selamat benang.

1. Menggunakan senarai terpaut dua kali dan jadual cincang untuk melaksanakan algoritma cache LRU

Di Golang, senarai terpaut dua kali ialah struktur data asas yang boleh melaksanakan algoritma cache LRU dengan mudah . Kaedah pelaksanaan khusus adalah untuk merangkum setiap elemen dalam cache ke dalam nod dan menggunakan senarai berganda untuk mengurus nod ini. Pada masa yang sama, jadual cincang (peta) digunakan untuk merekodkan lokasi setiap nod untuk memudahkan carian dan kemas kini pantas.

Berikut ialah struktur kod asas untuk melaksanakan algoritma cache LRU di Golang:

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
}

Dalam kod di atas, LRUCache ialah struktur, termasuk Cache jadual cincang, a Head penunjuk dan Tail penunjuk, digunakan untuk merekodkan nod kepala dan ekor senarai berganda dan kedudukan setiap elemen dalam cache. Antaranya, kunci jadual cincang Cache ialah kunci elemen, dan nilainya ialah penunjuk nod elemen Head menunjuk ke nod kepala senarai terpaut dua kali, dan Tail menunjuk ke; nod ekor. Size mewakili bilangan elemen dalam cache semasa dan Capacity mewakili kapasiti maksimum cache.

Dalam fungsi Constructor, kami memulakan senarai terpaut dua kali kosong dan mengembalikan struktur LRUCache. Dalam fungsi Get, kami mula-mula menentukan sama ada elemen yang ditentukan wujud dalam cache Jika ia wujud, alihkan elemen ke kepala senarai terpaut dan kembalikan nilainya, -1 dikembalikan. Dalam fungsi Put, kami mula-mula menentukan sama ada elemen yang dinyatakan wujud dalam cache Jika ia wujud, kemas kini nilai elemen dan alihkannya ke kepala jika tidak, tambahkan elemen baharu dan tambahkannya pada kepala. Jika saiz cache melebihi kapasiti maksimum, elemen yang paling kurang digunakan baru-baru ini dialih keluar dan dialih keluar daripada jadual cincang.

MoveToHead, RemoveNode, AddToHead dan RemoveTail masing-masing sepadan dengan pergerakan nod dan operasi pemadaman senarai terpaut berganda Kaedah pelaksanaan khusus diberikan dalam kod.

2. Mengemas kini dan menghapuskan cache

Apabila menggunakan algoritma cache LRU, adalah perlu untuk memastikan urutan akses elemen dalam cache disusun mengikut tertib kebanyakan masa yang digunakan baru-baru ini. Setiap kali elemen dibaca atau dikemas kini daripada cache, ia perlu dialihkan ke kepala senarai terpaut pada masa yang sama, apabila saiz cache melebihi kapasiti maksimum, elemen yang paling kurang digunakan baru-baru ini, iaitu elemen terakhir dalam senarai terpaut, perlu dihapuskan.

Berikut ialah bagaimana fungsi MoveToHead dilaksanakan:

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

MoveToHeadFungsi menerima penuding ke nod cache node sebagai parameter, mula-mula memadamkan nod daripada senarai terpaut, dan kemudian Nod ditambah pada kepala senarai terpaut.

Berikut ialah cara fungsi RemoveTail dilaksanakan:

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

RemoveTailFungsi mengembalikan nod terakhir dalam senarai terpaut dan memadamkan nod daripada senarai terpaut.

3. Kendalian selamat benang

Dalam persekitaran berbilang benang, adalah perlu untuk memastikan keselamatan rangkaian operasi cache LRU. Untuk melakukan ini, kita boleh menggunakan mutex yang disediakan dalam pakej penyegerakan. Kaedah khusus adalah untuk menambah operasi kunci mutex kepada fungsi yang memerlukan operasi cache untuk mengelakkan operasi baca dan tulis serentak pada cache. Berikut ialah struktur kod untuk melaksanakan versi selamat benang bagi algoritma caching LRU di Golang:

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()

    ...
}

...

Dalam kod di atas, kami menambah ahli LRUCache pada struktur Mutex untuk operasi caching. Pengecualian bersama serentak. Sebelum melakukan sebarang operasi caching, kita perlu mendapatkan kunci mutex. Walau apa pun, sama ada membaca atau mengubah suai cache, kita perlu melepaskan mutex.

4. Ringkasan

Artikel ini memperkenalkan pelaksanaan algoritma cache LRU di Golang, termasuk penggunaan senarai terpaut dua kali dan jadual cincang untuk melaksanakannya, kemas kini cache dan penghapusan, dan Operasi selamat benang. Algoritma cache LRU ialah algoritma cache yang mudah dan cekap yang digunakan secara meluas dalam pembangunan sebenar. Apabila menggunakan Golang untuk menulis aplikasi cache, anda boleh menggunakan algoritma cache LRU untuk meningkatkan prestasi dan kestabilan sistem mengikut keperluan sebenar.

Atas ialah kandungan terperinci Analisis terperinci algoritma cache LRU di Golang.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!