golang lru 구현

LRU(Least Recent Used) 알고리즘은 일반적인 캐시 교체 전략입니다. 캐시가 미리 설정된 제한에 도달하면 캐시는 공간을 확보하기 위해 최근에 가장 적게 사용된 데이터를 자동으로 제거합니다.

Golang에서는 이중 연결 목록과 해시 테이블을 사용하여 LRU 캐시를 구현할 수 있습니다. 이 기사에서는 이 두 가지 데이터 구조를 사용하여 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를 사용하여 각각 노드의 선행 포인터와 후속 포인터를 나타내고, 키와 값은 각각 노드의 키-값 쌍을 나타냅니다.

다음으로 LRUCache의 생성자 NewLRUCache를 정의하고 캐시 용량을 전달합니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!