Construa um Cache Go em 10 Minutos

Joseph Livni Blocked Desbloquear Seguir Seguindo 7 de janeiro

O cache é uma das maiores inovações da ciência da computação. Isso reduz significativamente o trabalho na CPU e fornece ganhos de desempenho massivos em termos de velocidade. ?

Funciona salvando o resultado de cálculos que podem ser necessários posteriormente. Por exemplo: digamos que você tenha um serviço que, dada uma string, gerasse um hash. Um cache pode economizar tempo e recursos, verificando se o hash da string recebida já foi gerado. Se tivesse, e ainda estivesse no cache, ele seria retornado sem executar o algoritmo hash novamente.

Hoje, estaremos construindo um cache LRU ( Last Recently Used ) que armazena uma quantidade fixa de strings e ejeta o último item usado quando o cache estiver cheio.

Isso não será algo que você gostaria de executar na produção. Mas isso demonstrará claramente as data structures e os algorithms que fazem esse tipo de cache funcionar.

Para obter e executar os resultados finais:

 git clone https://github.com/Lebonesco/go_lru_cache.git 
vai correr main.go

Vamos pular em algum código!

Começaremos definindo nossas data structures . Estes incluirão Node , Queue , Hash e Cache . Nossa Queue será uma lista duplamente vinculada de ponteiros de Node que são mapeados para o Hash . Isso permitirá a inserção e exclusão de valores de O (1) . ?

Nota: estamos apenas cache de strings agora, mas qualquer data type poderia substituí-lo.

Em seguida, configuraremos nossas funções de construtor para o Cache e a Queue . Embora o Hash comece vazio, ele precisa ser inicializado ou resultará em um “erro de ponteiro nulo” mais tarde. Além disso, criamos dois Nodes vazios para a cabeça e cauda . Isso fará mais sentido quando passarmos para os métodos Add() e Remove() .

Para o código primário do cache.

O cache tem três métodos necessários para fazê-lo funcionar: Check() (recebe a string do usuário e retorna o resultado), Add() (adiciona uma string ao cache), Remove() (ejeta uma string do cache).

Dentro de Check() , se a string já existir no cache, primeiro removê-la antes de adicioná-la novamente, para que a string seja deslocada para a frente da Queue .

Ambos, Add() e Remove() envolvem operações similares que reatribuem os ponteiros do Node Left e Right na Queue .

Incrível, agora temos um cache de trabalho! ???

O último passo é adicionar um main() e alguns métodos de exibição para demonstrar nossos resultados.

Para ver seu código em ação, execute:

 vai correr main.go 
CACHE DE INÍCIO
adicione: gato
1 - [{cat}]
adicionar: azul
2 - [{blue} <-> {cat}]
adicionar: cão
3 - [{dog} <-> {blue} <-> {cat}]
adicionar: árvore
4 - [{tree} <-> {dog} <-> {blue} <-> {cat}]
adicionar: dragão
5 - [{dragon} <-> {tree} <-> {dog} <-> {blue} <-> {cat}]
adicione: batata
remover: gato
5 - [{potato} <-> {dragon} <-> {tree} <-> {dog} <-> {blue}]
adicionar: casa
remover: azul
5 - [{house} <-> {potato} <-> {dragon} <-> {tree} <-> {dog}]
remover: árvore
adicionar: árvore
5 - [{tree} <-> {house} <-> {potato} <-> {dragon} <-> {dog}]
adicione: gato
remover: cão
5 - [{cat} <-> {tree} <-> {house} <-> {potato} <-> {dragão}]

Obrigado por tomar o tempo para ler este artigo.

Se você achou útil ou interessante por favor me avise ???.