Escolher a estrutura
Uma tabela de decisão: a pergunta que o código faz mais vezes decide a estrutura.
A estrutura certa não é a “mais rápida”: é a que responde barato a pergunta que o código faz mais vezes. Um vault é ótimo para “quanto vale esta chave?” e péssimo para “qual é o menor?”.
| A pergunta frequente | Estrutura | Custo |
|---|---|---|
| está aqui? | Set | O(1) |
| quanto vale esta chave? | Vault | O(1) |
| qual é o i-ésimo? | Cluster | O(1) |
| qual é o menor agora? (e tirar) | heap — Collections.heap_* | O(log n) |
| o primeiro que chegou? | fila — Collections.deque | O(1) nas duas pontas |
| em que posição entraria? (ordenado) | Cluster ordenado + limite_inferior | O(log n) |
| estes dois estão no mesmo grupo? | Collections.union_find | ≈ O(1) |
| qual o caminho entre dois pontos? | grafo (vault de listas) | O((V + E) log V) |
dataforge
adopt Arcane.Collections as C
// O menor, repetidas vezes: heap.
fila := C.heap([5, 1, 9, 3]) // devolve a fila; nao muda a lista
assert C.heap_pop(fila) is 1
assert C.heap_pop(fila) is 3
// Duplicatas: set.
vistos := set()
duplicados := []
cycle email in ["a@x", "b@x", "a@x"]:
given email in vistos:
duplicados.append(email)
vistos.add(email)
assert duplicados is ["a@x"]