Pole, spojový seznam, hash: tři různé odpovědi
Kontejner se nevybírá podle toho, který je „nejlepší“, ale podle toho, které operace se budou dělat často. Každý z těch tří je v něčem konstantní a v něčem lineární — a nikdo z nich není konstantní ve všem.
| operace | pole | spojový seznam | hash | vyvážený strom |
|---|---|---|---|---|
| vzít i-tý prvek | O(1) | O(n) | — | O(log n) |
| přidat na konec | O(1)* | O(1) | O(1) | O(log n) |
| vložit na začátek | O(n) | O(1) | O(1) | O(log n) |
| najít hodnotu | O(n) | O(n) | O(1) | O(log n) |
| projít v pořadí | ano | ano | ne | ano |
| paměť na prvek | 1× | ~3× | ~2,5× | ~4× |
* amortizovaně — občas se pole musí přesypat do většího, ale zdvojnásobování velikosti rozprostře tu cenu tak, že vychází konstantní na prvek.
Poslední dva řádky jsou ty, na které se zapomíná
Hashovací tabulka neumí pořadí. Umí říct „mám tenhle klíč?“ a neumí „co je hned další větší“ ani „vypiš mi to od nejmenšího“. Když je pořadí potřeba, hash odpadá bez ohledu na to, jak je rychlý — a proto existují vyvážené stromy, které mají všechno logaritmické, ale pořadí zachovají.
Paměť na prvek není jen otázka velikosti. Spojový seznam potřebuje ukazatel u každého prvku, a ten ukazatel se s daty nikam nevejde — proto je jeho prvek roztroušený po paměti a proto je pomalejší, než jeho O() naznačuje. To je celá další kapitola.
Nejběžnější chyba v tomhle rozhodování: „budu často vkládat doprostřed, takže spojový seznam“. Vložení do spojového seznamu je O(1) jen když už držím ukazatel na to místo. Najít to místo je O(n) — a to hledání sežere všechno, co vložení ušetřilo. V praxi je pole rychlejší i pro vkládání doprostřed, dokud není opravdu velké.
Amortizovaná cena, stručně
Pole, které dojde místo, se přesype do dvojnásobně velkého. Ta jedna operace je O(n) — ale stane se to jen když se velikost zdvojnásobila, takže na prvek to vyjde konstantně.
Pozor ale: amortizovaně neznamená vždycky. Ta jedna operace, při které se pole přesypává, trvá O(n) — a v regulační smyčce se to pozná. Kapitola 11.