LRU Cache em Zig — Implementação Completa
O LRU Cache (Least Recently Used Cache) é uma estrutura que mantém os N itens mais recentemente acessados. Quando o cache está cheio e um novo item precisa ser inserido, o item menos recentemente usado é removido (evicado). A combinação de HashMap e lista duplamente encadeada permite get e put em O(1).
Conceito
LRU Cache com capacidade 3:
put(A, 1): [A:1] (MRU) A (LRU)
put(B, 2): [A:1, B:2] (MRU) B → A (LRU)
put(C, 3): [A:1, B:2, C:3] (MRU) C → B → A (LRU)
get(A): [A:1, B:2, C:3] (MRU) A → C → B (LRU) ← A movido p/ frente
put(D, 4): [A:1, C:3, D:4] (MRU) D → A → C (LRU) ← B evicado!
Estrutura interna:
HashMap: chave → ponteiro para nó da lista
Lista: head ↔ nó1 ↔ nó2 ↔ ... ↔ tail
(MRU) (LRU)
Implementação em Zig
const std = @import("std");
const Allocator = std.mem.Allocator;
/// LRU Cache com get/put em O(1).
pub fn LruCache(comptime K: type, comptime V: type) type {
return struct {
const Self = @This();
const No = struct {
chave: K,
valor: V,
prev: ?*No,
next: ?*No,
};
mapa: std.StringHashMap(*No),
head: ?*No, // Mais recente (MRU)
tail: ?*No, // Menos recente (LRU)
capacidade: usize,
tamanho: usize,
allocator: Allocator,
pub fn init(allocator: Allocator, capacidade: usize) Self {
return .{
.mapa = std.StringHashMap(*No).init(allocator),
.head = null,
.tail = null,
.capacidade = capacidade,
.tamanho = 0,
.allocator = allocator,
};
}
pub fn deinit(self: *Self) void {
var atual = self.head;
while (atual) |no| {
const next = no.next;
self.allocator.destroy(no);
atual = next;
}
self.mapa.deinit();
}
/// Busca um valor — O(1). Move para frente (MRU).
pub fn get(self: *Self, chave: K) ?V {
if (self.mapa.get(chave)) |no| {
self.moverParaFrente(no);
return no.valor;
}
return null;
}
/// Insere ou atualiza — O(1). Evica LRU se necessário.
pub fn put(self: *Self, chave: K, valor: V) !?struct { chave: K, valor: V } {
var evicado: ?struct { chave: K, valor: V } = null;
// Se chave já existe, atualiza
if (self.mapa.get(chave)) |no| {
no.valor = valor;
self.moverParaFrente(no);
return null;
}
// Se cheio, evica o LRU (tail)
if (self.tamanho >= self.capacidade) {
if (self.tail) |lru| {
evicado = .{ .chave = lru.chave, .valor = lru.valor };
self.removerNo(lru);
_ = self.mapa.remove(lru.chave);
self.allocator.destroy(lru);
self.tamanho -= 1;
}
}
// Cria novo nó
const novo = try self.allocator.create(No);
novo.* = .{
.chave = chave,
.valor = valor,
.prev = null,
.next = null,
};
self.adicionarNaFrente(novo);
try self.mapa.put(chave, novo);
self.tamanho += 1;
return evicado;
}
/// Remove uma chave — O(1).
pub fn remove(self: *Self, chave: K) ?V {
if (self.mapa.get(chave)) |no| {
const valor = no.valor;
self.removerNo(no);
_ = self.mapa.remove(chave);
self.allocator.destroy(no);
self.tamanho -= 1;
return valor;
}
return null;
}
fn moverParaFrente(self: *Self, no: *No) void {
if (self.head == no) return; // Já é o MRU
self.removerNo(no);
self.adicionarNaFrente(no);
}
fn adicionarNaFrente(self: *Self, no: *No) void {
no.prev = null;
no.next = self.head;
if (self.head) |h| {
h.prev = no;
}
self.head = no;
if (self.tail == null) {
self.tail = no;
}
}
fn removerNo(self: *Self, no: *No) void {
if (no.prev) |p| {
p.next = no.next;
} else {
self.head = no.next;
}
if (no.next) |n| {
n.prev = no.prev;
} else {
self.tail = no.prev;
}
no.prev = null;
no.next = null;
}
/// Lista conteúdo do MRU ao LRU.
pub fn listar(self: *const Self, writer: anytype) !void {
var atual = self.head;
var primeiro = true;
while (atual) |no| {
if (!primeiro) try writer.writeAll(" → ");
try writer.print("{s}:{}", .{ no.chave, no.valor });
primeiro = false;
atual = no.next;
}
try writer.writeAll("\n");
}
};
}
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var cache = LruCache([]const u8, i32).init(allocator, 3);
defer cache.deinit();
try stdout.writeAll("=== LRU Cache (capacidade=3) ===\n\n");
// Inserções
_ = try cache.put("A", 1);
try stdout.writeAll("put(A,1): ");
try cache.listar(stdout);
_ = try cache.put("B", 2);
try stdout.writeAll("put(B,2): ");
try cache.listar(stdout);
_ = try cache.put("C", 3);
try stdout.writeAll("put(C,3): ");
try cache.listar(stdout);
// Acesso move para frente
const val = cache.get("A");
try stdout.print("\nget(A) = {?d}\n", .{val});
try stdout.writeAll("Estado: ");
try cache.listar(stdout);
// Inserção causa evição
const evicado = try cache.put("D", 4);
try stdout.print("\nput(D,4): ", .{});
try cache.listar(stdout);
if (evicado) |e| {
try stdout.print("Evicado: {s}:{d}\n", .{ e.chave, e.valor });
}
// Verificar miss
try stdout.print("\nget(B) = {?d} (evicado anteriormente)\n", .{cache.get("B")});
try stdout.print("get(D) = {?d}\n", .{cache.get("D")});
// Simulação de cache de páginas web
try stdout.writeAll("\n=== Simulação: Cache de Páginas ===\n");
var page_cache = LruCache([]const u8, []const u8).init(allocator, 4);
defer page_cache.deinit();
const acessos = [_][]const u8{
"/home", "/about", "/blog", "/contact",
"/home", // Cache hit — move para frente
"/pricing", // Cache miss — evica /about
"/blog", // Cache hit
};
for (acessos) |pagina| {
if (page_cache.get(pagina) != null) {
try stdout.print(" HIT: {s}\n", .{pagina});
} else {
const ev = try page_cache.put(pagina, "conteúdo...");
if (ev) |e| {
try stdout.print(" MISS: {s} (evicou {s})\n", .{ pagina, e.chave });
} else {
try stdout.print(" MISS: {s}\n", .{pagina});
}
}
}
}
Análise de Complexidade
| Operação | Tempo | Espaço |
|---|---|---|
| get | O(1) | O(1) |
| put | O(1) | O(1) |
| remove | O(1) | O(1) |
| Espaço total | — | O(capacidade) |
Variações
- LFU Cache (Least Frequently Used) — evica o menos frequentemente usado
- TTL Cache — evica por tempo de expiração
- ARC (Adaptive Replacement Cache) — combina LRU e LFU
Recursos Relacionados
- Hash Table — Base do mapa interno
- Lista Duplamente Encadeada — Base da lista interna
- Ring Buffer — Buffer circular
- Desafio de Código: Estruturas