Vyhledávání a kdy se vyplatí setřídit
Najít hodnotu v neuspořádaném poli znamená projít ho — v průměru půlku, v nejhorším celé. V setříděném poli stačí logaritmicky mnoho porovnání, a ten rozdíl je propastný.
- hledáme 23 · n = 16
Setříděnost je tu podmínka, ne pohodlí. Bez ní tenhle postup neplatí vůbec.
- a[8] = 17 < 23 → vlevo to není
Jedno porovnání. A ať dopadne jakkoli, polovina pole je tím vyřízená.
- 16 → 8 → 4 → 2 → 1
Zbývá osm prvků. Znovu doprostřed — a zbydou čtyři.
- kroků = ⌈log₂(n+1)⌉ = 5
Kolikrát jde 16 vydělit dvěma, než zbude jeden prvek. To je definice logaritmu.
- n = 10⁶ → 20 · n = 2·10⁶ → 21
Milion prvků se prohledá dvaceti porovnáními. Zdvojnásobení dat stojí JEDNO porovnání navíc.
| n | lineárně (průměr) | binárně (nejhůř) |
|---|---|---|
| 100 | 50 | 7 |
| 10 000 | 5 000 | 14 |
| 1 000 000 | 500 000 | 20 |
Ale setřídit něco stojí
Tohle je otázka, kterou lidé pravidelně přeskočí: jednorázové hledání v neuspořádaném poli se nemá řešit setříděním. Setřídit milion prvků stojí kolem 2·10⁷ porovnání; projít je stojí 10⁶. Setřídit a pak hledat je tedy dvacetkrát dražší než prostě projít.
Vyplatí se to až tehdy, když se hledá opakovaně:
Pro n = 1000 vychází hranice kolem 18 hledání. Míň než osmnáct — projít pole. Víc — setřídit.
A pak je tu třetí možnost, na kterou se často zapomíná: hashovací tabulka. Ta hledá v konstantním čase bez ohledu na n, tedy poráží obojí — a platí se za to pamětí a tím, že neumí odpovědět na otázku „co je hned další větší“. Setříděné pole to umí, hashovací tabulka ne. Volba mezi nimi je volba mezi dvěma různými otázkami, ne mezi rychlostmi.
Past, která tam byla devět let
Klasická implementace binárního vyhledávání počítá střed jako (lo + hi) / 2. Pro
velká pole to přeteče — a je to ta samá chyba, o které má
BitLab kapitolu 4. Správně je
lo + (hi − lo) / 2. V knihovně Javy ta chyba byla devět let, než si jí někdo všiml.