Custo das estruturas
O que cada operação de cluster, vault e string realmente custa.
Escolher a estrutura certa costuma render mais que otimizar o algoritmo. Esta é a tabela que decide.
Cluster#
| Operação | Custo | Por quê |
|---|---|---|
xs[i] | O(1) | acesso direto pelo índice |
xs.append(x) | O(1)* | amortizado — ver casos |
xs.pop() | O(1) | remove do fim |
xs.pop(0) | O(n) | desloca todos os outros |
xs.insert(0, x) | O(n) | idem |
x in xs | O(n) | percorre até achar |
xs.index_of(x) | O(n) | idem |
xs.remove(x) | O(n) | procura e desloca |
len(xs) | O(1) | o tamanho é guardado |
xs[a:b] | O(b−a) | copia a fatia |
xs.sort() | O(n log n) | ordenação por comparação |
xs.reverse() | O(n) | troca aos pares |
sum(xs), max(xs) | O(n) | percorre uma vez |
[...a, ...b] | O(n+m) | copia os dois |
Vault#
| Operação | Custo | Por quê |
|---|---|---|
v[chave] | O(1) | tabela de espalhamento |
v[chave] := x | O(1) | idem |
v.has(chave) | O(1) | idem |
chave in v | O(1) | idem |
v.get(chave, padrao) | O(1) | idem |
delete v[chave] | O(1) | idem |
v.keys() | O(n) | monta o cluster |
v.values() | O(n) | idem |
v.items() | O(n) | idem |
len(v) | O(1) | guardado |
O vault é a estrutura mais subutilizada da linguagem. Quase todo O(n²) acidental some ao trocar uma busca linear por uma consulta de vault.
String#
| Operação | Custo | Por quê |
|---|---|---|
s[i] | O(1) | acesso direto |
len(s) | O(1) | guardado |
a + b | O(n+m) | cria uma string nova |
s.contains(t) | O(n·m) | compara em cada posição |
s.split(sep) | O(n) | uma passada |
sep.join(xs) | O(n) | aloca uma vez |
s.replace(a, b) | O(n) | uma passada |
s.upper() | O(n) | cria uma nova |
s[a:b] | O(b−a) | copia |
Record e blueprint#
| Operação | Custo |
|---|---|
p.campo | O(1) |
p with {...} | O(k) — k campos |
spawn X(...) | O(k) — k campos |
p1 is p2 (record) | O(k) — compara campo a campo |
| chamar um método | O(1) + o corpo |
root.metodo() | O(d) — d = profundidade da herança |
Escolhendo#
| Você precisa de… | Use | Por quê |
|---|---|---|
| ordem e índice | Cluster | acesso O(1) por posição |
| procurar por chave | Vault | O(1) contra O(n) |
| itens únicos | Vault com valor yes | a chave já garante unicidade |
| contar ocorrências | xs.tally() | uma passada, O(n) |
| agrupar | xs.group_by(f) | uma passada, O(n) |
| valor imutável | record | igualdade estrutural, serve de chave |
| entidade com estado | blueprint | identidade própria |