golangでLRUアルゴリズムのキャッシュシステムを実装する方法

LRU (Least Recent Used) は、限られたキャッシュ容量の中で、最近使用したデータを最初にキャッシュし、長期間使用されていないデータを削除することで、キャッシュ領域の効率的な使用を実現し、データ効率を向上させるキャッシュ アルゴリズムです。アクセス速度。

Go 言語 (golang) は、優れた同時実行性とメモリ管理機能により開発者に好まれている効率的なプログラミング言語です。この記事では、LRU アルゴリズムのキャッシュ システムを実装し、Go 言語を使用してそれを実装します。

設計アイデア

LRU キャッシュ システムを実装する前に、まずシステム要件と設計アイデアを決定する必要があります。

まず、キャッシュされたデータを保存するためのデータ構造が必要ですが、このデータ構造は高速なアクセスと更新をサポートし、使用時間に応じたデータの削除をサポートする必要があります。一般的に使用されるデータ構造には、リンク リスト、ハッシュ テーブル、二重リンク リストなどが含まれます。その中でも、二重リンク リストは LRU アルゴリズムの実装に最適です。

2 番目に、このデータ構造にアクセスして更新するための操作が必要です。一般的な操作には、キャッシュ データの読み取り、キャッシュ データの書き込み、キャッシュ データの更新、キャッシュ データの削除などが含まれます。

最後に、キャッシュのサイズを制御し、キャッシュがメモリ全体を埋め尽くさないようにするためのキャッシュ戦略が必要です。一般的に使用される戦略には、FIFO (先入れ先出し)、LFU (最も頻繁に使用されない)、LRU (最も最近使用されていない) などが含まれます。その中でも、LRU キャッシュ システムを実装するには LRU が最適です。

コードの実装

これで、明確な設計アイデアが得られたので、LRU キャッシュ システムの実装を開始できます。コードは次のとおりです。

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

使用例

これで、単純な LRU キャッシュ システムが実装されました。次のサンプル コードを通じて使用できます。

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

上記のサンプル コードでは、Value インターフェイスを実装する stringValue 型を定義しました。キャッシュ内の値。次に、LRU キャッシュ システムを作成し、4 つのキャッシュ項目を追加しました。MaxBytes はキャッシュの最大容量を表します。次に、Get メソッドを使用してキャッシュ内の key1 に対応する値を取得し、新しいキャッシュ項目を追加し、最後に最も古いキャッシュ項目を削除します。

概要

これまでのところ、LRU キャッシュ システムの実装に成功しています。この記事を通じて、LRU キャッシュ アルゴリズムの実装を学習しただけでなく、Go 言語を使用してキャッシュ システムを実装する方法も学習しました。実際の開発では、キャッシュ システムを合理的に使用すると、プログラムのパフォーマンスが大幅に向上し、システムの負荷が軽減されます。したがって、キャッシュ システムは、すべての開発者が理解し、習得する必要がある重要なスキルの 1 つです。

以上がgolangでLRUアルゴリズムのキャッシュシステムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。