Medir a curva
Bench.curva e Bench.classe — a classe MEDIDA, com a honestidade de dizer quando a medida não separa duas.
A análise diz a classe esperada; a medida diz a real. Dobrar o n e ver quanto o tempo cresce responde qual curva descreve o código — um fator ~2 é linear, ~4 é quadrático, pouco mais que 2 é n log n.
dataforge
adopt Arcane.Bench as B
r := B.curva(lambda n: sum(range(0, n)), [20000, 40000, 80000])
cycle p in r["pontos"]:
out $"n = {p['n']}: {p['ms']} ms"
out $"fator ao dobrar: {r['fator']}"
c := B.classe(lambda xs: sorted(xs), [4000, 8000, 16000],
lambda n: range(n, 0, -1))
out $"classe medida: {c['classe']} ({c['certeza']}, candidatas {c['classes']})"
// Numa máquina carregada a resposta pode ser "entre O(n) e O(n^2)": a
// medição não separa as duas, e dizer isso é mais honesto que escolher.
assert len(c["classes"]) bigger_eq 1 and len(c["classe"]) bigger 0| Regra da medida | Porque |
|---|---|
| compare fatores, nunca milissegundos | o número absoluto mede a máquina |
| use tamanhos grandes o bastante | com n pequeno, o custo fixo do interpretador domina tudo |
| prepare a entrada fora do cronômetro | preparar gera os dados; senão mede-se a geração |
| repita e fique com o menor | o Bench já faz: o menor tempo é o menos perturbado |
bash
dataforge big-o src/ -v # a classe estimada, sem rodar
dataforge big-o src/ --medir # e a medida, lado a lado