Golang практика алгоритм хранения данных в кэше.

Продолжаем рубрику решения практических задачи на Go.

Реализуйте LFU (least frequently used) — это алгоритм хранения данных в кэше, который подсчитывает частоту использования каждого элемента и удаляет те, к которым обращаются реже всего.

Он должен  инициализироваться с размером кеша n и содержать следующие методы:

set(key, value): если в кеше уже есть n элементов и мы добавляем новый элемент, то он также должен удалить наименее часто используемый элемент. Если есть ключи с одинаковой наименьшей частотой, то ключ, который использовался последним, должен быть удален.

get(key): получаем значение по ключу. Если такого ключа не существует, вернуть null. Каждая операция должна выполняться за O(1).

Golang_google – больше практики Golang в нашем телеграм канале.

Код:

package problem067

type freqNode struct {
	next       *freqNode
	prev       *freqNode
	refCount   int
	dNodesHead *dataNode
	dNodesTail *dataNode
}

type dataNode struct {
	next  *dataNode
	prev  *dataNode
	key   string
	value interface{}
	fNode *freqNode
}

type LfuCache struct {
	fNodesHead *freqNode
	fNodesTail *freqNode
	dNodes     map[string]*dataNode
	maxSize    uint
}

func NewCache(maxSize uint) *LfuCache {
	m := maxSize
	if m <= 0 {
		m = 1
	}
	h, t := &freqNode{
		refCount: -1,
	}, &freqNode{
		refCount: -1,
	}
	h.next, t.prev = t, h

	return &LfuCache{
		fNodesHead: h,
		fNodesTail: t,
		dNodes:     map[string]*dataNode{},
		maxSize:    m,
	}
}

func (c *LfuCache) Get(key string) interface{} {
	dNode, dNodeExists := c.dNodes[key]
	// return nil if the key not exists
	if !dNodeExists {
		return nil
	}

	fNode := dNode.fNode
	newFNode := fNode.next
	if newFNode.refCount != fNode.refCount+1 {
		// create a freq node with refCount = fNode.refCount + 1, if not any
		h, t := &dataNode{}, &dataNode{}
		h.next, t.prev = t, h

		newFNode = &freqNode{
			prev:       fNode,
			next:       fNode.next,
			refCount:   fNode.refCount + 1,
			dNodesHead: h,
			dNodesTail: t,
		}
		fNode.next, fNode.next.prev = newFNode, newFNode
	}

	dNode.prev.next, dNode.next.prev = dNode.next, dNode.prev
	newFNode.dNodesTail.prev, newFNode.dNodesTail.prev.next = dNode, dNode
	dNode.fNode, dNode.prev, dNode.next = newFNode, newFNode.dNodesTail.prev, newFNode.dNodesTail

	if fNode.dNodesHead.next == fNode.dNodesTail {
		fNode.prev.next, fNode.next.prev = fNode.next, fNode.prev
	}

	return dNode.value
}

func (c *LfuCache) Set(key string, value interface{}) {
	if _, alreadyExists := c.dNodes[key]; alreadyExists {
		return
	}

	for len(c.dNodes) >= int(c.maxSize) {
		// delete the least frequently used dNode
		lfuFNode, lfuDNode := c.fNodesHead.next, c.fNodesHead.next.dNodesHead.next
		delete(c.dNodes, lfuDNode.key)
		lfuDNode.prev.next, lfuDNode.next.prev = lfuDNode.next, lfuDNode.prev
		if lfuFNode.dNodesHead.next == lfuFNode.dNodesTail {
			lfuFNode.prev.next, lfuFNode.next.prev = lfuFNode.next, lfuFNode.prev
		}
	}

	fNode := c.fNodesHead.next
	if fNode.refCount != 0 {
		h, t := &dataNode{}, &dataNode{}
		h.next, t.prev = t, h

		fNode = &freqNode{
			next:       c.fNodesHead.next,
			prev:       c.fNodesHead,
			refCount:   0,
			dNodesHead: h,
			dNodesTail: t,
		}
		c.fNodesHead.next, c.fNodesHead.next.prev = fNode, fNode
	}

	dNode := &dataNode{
		next:  fNode.dNodesTail,
		prev:  fNode.dNodesTail.prev,
		key:   key,
		value: value,
		fNode: fNode,
	}
	fNode.dNodesTail.prev, fNode.dNodesTail.prev.next = dNode, dNode

	c.dNodes[key] = dNode
}

Тесты:

package problem067

import (
	"os"
	"testing"
)

var cache *LfuCache = nil

func TestMain(m *testing.M) {
	cache = NewCache(4)
	os.Exit(m.Run())
}

func TestLfuCache_Set(t *testing.T) {
	cache.Set("key1", "value1")
	cache.Set("key2", "value2")
	cache.Set("key3", "value3")
	cache.Set("key4", "value4")

	cache.Get("key1")
	cache.Get("key1")
	cache.Get("key1")

	cache.Set("key5", "value5")

	if _, exists := cache.dNodes["key1"]; !exists {
		t.Logf("cache key evicted: %s", "key1")
		t.FailNow()
	}
	if _, exists := cache.dNodes["key2"]; exists {
		t.Logf("cache key not evicted: %s", "key2")
		t.FailNow()
	}
}