Nízkoúrovňový dokonalý kód
Školení, která pořádám 
Při čtení knihy Dokonalý kód si někdy připadám, jako kdyby programátor v C četl tipy pro asembler.
Tabulky s indexovaným přístupem
V knize je třeba tento příklad: Máme na skladě 100 položek, každá z nich má číslo v rozmezí 0 až 9999. Jde o to umět tyto položky rychle hledat.
Kniha popisuje, že pokud každá položka zabírá třeba 100 bajtů, tak udělat vyhledávací tabulku pro všechna čísla by bylo nehospodárné. Doporučuje tedy vytvořit tzv. index – tabulku, ve které bude pro každé číslo jen dvoubajtový odkaz do tabulky, kde budou teprve uloženy samotné položky. K položce potom přistoupíme pomocí $table[$index[$number]].
O malou velikost zvolených čísel teď nejde (1 MB zabraný v nehospodárné variantě dnes už obvykle není žádný problém) – stačí si představit, že číslo může být třeba osmiciferné. Jde o to, že ani doporučené řešení není přes svou vyšší komplikovanost optimální.
V PHP je přitom optimální řešení po ruce – stačí položky uložit do asociativního pole (klíčem bude jejich číslo). Ta jsou v PHP totiž implementována jako hash-tabulky. Jak to je se složitostí? (M je rozsah čísel, N je počet položek, X je velikost položky)
| Čas vyhledání jednoho prvku | Zabraná paměť | |
|---|---|---|
| Nehospodárné řešení | O(1) | O(M * X) |
| Řešení z knihy | O(1) | O(M * log N) + O(N * X) |
| Asociativní pole | O(1) | O(N * (X + log M)) |
Řešení v knize má ten principiální problém, že zabraná paměť stále záleží na rozsahu čísel – když je jich hodně, tak se zabere i hodně paměti. Hash-tabulka zabere asymptoticky minimální množství paměti a přitom si zachovává konstantní rychlost přístupu k prvku.
Tabulky se schodovým přístupem
V dalším příkladu jde o to přiřadit známku na základě dosaženého skóre. Když někdo např. dosáhne skóre 30.0, dostane "F", když dosáhne 95.0, dostane "A". Kniha pro to používá takzvanou tabulku se schodovým přístupem:
<?php $rangeLimit = array(50.0, 65.0, 75.0, 90.0, 100.0); $grade = array("F", "D", "C", "B", "A"); $maxGradeLevel = count($grade) - 1; $gradeLevel = 0; $studentGrade = "A"; while ($studentGrade == "A" && $gradeLevel < $maxGradeLevel) { if ($studentScore < $rangeLimit[$gradeLevel]) { $studentGrade = $grade[$gradeLevel]; } $gradeLevel++; } ?>
Protentokrát pominu, že by se v PHP dal kód napsat mnohem elegantněji (místo dvou polí by stačilo jedno asociativní, které by se dalo projít cyklem foreach). Problém ale podobně jako u prvního příkladu vidím v tom, že když by prvků bylo hodně, čas algoritmu by na nich lineárně závisel. Kniha na to tentokrát upozorňuje a doporučuje v tomto případě použít tzv. kvazibinární vyhledávání (nehledáme přesnou hodnotu, ale např. nejbližší menší).
Když jsem se zamyslel, jak bych tento problém vyřešil sám, tak mi došlo, že bych ho nejspíš v PHP vůbec neřešil. Rozsahy pro jednotlivé známky jsou totiž data a ta patří do databáze (kde se taky dají snadno měnit). Když bych chtěl vědět známku pro dané skóre, zjistil bych to dotazem SELECT grade FROM grade_level WHERE min_score <= ? ORDER BY min_score DESC LIMIT 1. A když bych to potřeboval hromadně třeba pro všechny studenty, vyřešil bych to opět na straně databáze pomocí poddotazu.
Závěr
Na problém je vždy vhodné se podívat z vyšší perspektivy, protože některé doporučované postupy jsou pro dostupné vyjadřovací prostředky zbytečně nízkoúrovňové (a navíc třeba ještě neoptimální).
Diskuse
Radecek:
To dokonaly kod je tak nedokonaly nebo jsi takovy rypal? :P
Jakub Vrána 
:
Jak už jsem napsal, tak podle mě je to dobrá kniha. Tohle nejsou nějaké vyložené chyby – jsou to oblasti, ke kterým bych prostě jen něco dodal.
Jakub Vrána : Lukas Uhl:
Ahoj. V rámci toho řešení z knihy by přece ten index nemusel být vytvořen pro celý rozsah M, ale jen pro položky N. Takže ta "paměťová složitost" by byla jen O(N * (log N + X)) s tím, že by INSERTy apod. byly o fous pomalejší kvůli průběžné indexaci. Nebo se pletu? Jakub Vrána :
Ne, kniha doporučuje vytvořit pole (kterému říká tabulka) velikosti M, kde v každém prvku je odkaz do dalšího pole, kde jsou teprve uloženy položky. Pro čísla bez položky je v poli velikosti M uložena nějaká neplatná hodnota (např. -1).
Jakub Vrána : Michal Illich:
Opravdu v tom "děravém" poli ("nehospodárné řešení") zabírají 100 bajtů i ta neobsazená pole?Nikdy jsem implementaci PHP nestudoval, ale tak nějak jsem měl za to, že PHP používá binární strom (a/nebo hashovou tabulku) a tedy přeskočené položky žádné pole nezabírají.
Je někde popsáno, jak jsou pole v PHP implementovaná (právě z hlediska datových struktur a paměťové náročnosti)?
Jakub Vrána :
V knize je popsané obecné řešení nezávislé na programovacím jazyku. PHP žádná běžná pole vůbec nemá, všechna pole jsou asociativní (a používají hashovou tabulku). Pole tedy zabírá tolik, co součet jednotlivých uložených prvků (plus nějaká režie).
Žádné „přeskočené položky“ tedy vůbec neexistují. Když mám pole s indexy 0 a 2, tak PHP ani nenapadne, proč by se mělo starat ještě o index 1.
Nejlepší dokumentace je asi zdroják :-). Něco by se taky asi dalo najít na http://www.php.net/manual/en/internals2.php.
Jakub Vrána : Michal Illich:
Aha.- takhle jsem si myslel, že to je.
- a tím pádem nechápu, proč to na PHP tricích vůbec řešíš.
Jakub Vrána :
Řeším to proto, že mě to zaujalo. Co vypadá jako docela dobrá rada v jednom programovacím jazyce (nebo i obecně nehledě na jazyce), může být velmi špatná rada v jiném programovacím jazyce.
A dovedu si představit, že se nad tím spousta programátorů takhle nezamyslí (třeba proto, že ani neví, jak jsou v PHP implementována pole) a pro řešení daného příkladu použijí $table[$index[$number]] v domnění, že ušetří paměť. Přitom akorát zaberou paměť navíc.
Jakub Vrána : Jakub Vrána :
Dobře to bude vidět na kódu. Když by někdo radu z knihy bez přemýšlení implementoval v PHP, dojde zhruba k tomuto kódu:
<?php
$index = array();
for ($number = 0; $number < M; $number++) {
$index[$number] = null;
}
$table = array();
while ($row = $result->fetch()) {
$index[$row["number"]] = count($table);
$table[] = $row;
}
// přístup k prvku $number:
$table[$index[$number]];
?>
Kód je složitý, pomalý a zabírá hodně paměti. Když naopak použije tohle:
<?php
$table = array();
while ($row = $result->fetch()) {
$table[$row["number"]] = $row;
}
// přístup k prvku $number:
$table[$number];
?>
Tak dostane kód nejen mnohem přehlednější, ale hlavně rychlejší a paměťově šetrnější.
Jakub Vrána : optik:
Tohle už mi přijde až takové moc šťourání do detailů, knihu jsem tedy nečetl, ale opravdu tam není ani zmínka o hash tabulkách a jejich efektivitě? Přece i v tom Cčku se válí po Internetu určitě asi miliarda knihoven, které to řeší. Dobrá, možná to mohli zmínit přímo v té kapitole s tabulkami, ale i tak je podle mě detail. Na jaké je kniha cílena čtenáře? Zas tak bych je nepodceňoval.
Jakub Vrána :
Knihu jsem ještě celou nedočetl, ale ani v rejstříku hash tabulky nejsou a ani podle obsahu to nevypadá, že by ještě měly být kde zmíněny. Tohle jsou ukázky z kapitoly Metody řízené tabulkami – kde jinde už by se hash tabulky měly využít?
Já to za detail nepovažuji. Hash tabulky jsou dnes podle mě zcela běžná datová struktura, okamžitě po ruce v mnoha programovacích jazycích (jak píšeš, tak i v tom Céčku). Vůbec je nezmínit a přitom celkem detailně popisovat méně efektivní strukturu považuji za nedostatek.
Proto jsem si to ostatně poznamenal na blog – zdánlivě dobrá rada je ve skutečnosti v PHP a dalších jazycích antirada.
Kniha je cílena na programátory od středních začátečníků až po odborníky a na analytiky pokročilé a odborníky (na škále od naprostých začátečníků po odborníky).
Jakub Vrána : optik:
Tak to jo, hash tabulky určitě měly být alespoň zmíněny.
m-> 29:
Mňa by celkom zaujímalo prečo je pri "riešení z knihy(zabraná pamäť)" veľkosť položky pola "$index" práve "log N". A zložitosť je teda "O(M * log N) + O(N * X)".Takisto pri "asociatívnom poli(zabraná pamäť)" zložitosť "O(N * (X + log M))". Ak je to "log M" nejaká réžia tak ako si na to prišiel, že je práve "log M"?
Dík za odpoveď
Jakub Vrána :
Vysvětlím to na příkladě: Když je N (počet položek) třeba 100, odkaz se vejde do jednoho bajtu (protože v něm můžeme indexovat až 255 hodnot + 1 speciální). Když je položek 10 000, vejde se odkaz do dvou bajtů (65 535 + 1). A tak dále.
log M není nějaká režie. U hash-tabulek musíme kromě hashe (který zabírá konstantní paměť) uložit také původní hodnotu klíče. A ta se vejde právě do log M.
Tyhle logaritmy se dají často zanedbat, protože se dají shora omezit konstantou. Ale i samotná lineární závislost na M může být problém.
Jakub Vrána : 
Opravdový odborník :-):
Uff. Už vám asi nic radit nebudu, neboť je to ztráta času (mého).
Jen k tomu SQL: kniha je hlavně o algoritmizaci a o těch nejzákladnějších principech - ne o používání roztodivných vysokoúrovňových nástrojů, jako jsou relační databáze.
8ecd0389dc244411e8993d582bd0ae77
Ano, kniha je často dost nízkoúrovňová, ale to není její vada, to je vlastnost. Možná jen nejste její cílová skupina... Některé části jsou prostě spíše určené programátorům, kteří budou vytvářet vlastní datové struktury (např. ty hash tabulky) než kodérům, kteří píší aplikace (nebo dělají "webiki").
Opravdový odborník :-): Michal:
Vaše připomínky jsou jen slova kořeněná Vaší arogancí vůči Jakubovi. Opuštěním diskusí tohoto webu myslím přispějete nejvíce a ušetříte svůj čas "Opravdového odborníka".Opravdový odborník :-):
To jste pochopil špatně, to není zášť - chtěl jsem jen poradit mladšímu kolegovi. Zášť je možná když se pan Vrána naváží do autora knihy - nebo je to možná snaha vytvořit si image a zviditelnit se kopáním do autorit v oboru, nevím... (a že to není poprvé). Steve McConnell tento blog asi nečte, aby na kritiku mohl reagovat nebo aby mu k něčemu byla, že? Jakub Vrána :
Do nikoho se nenavážím a už vůbec do nikoho nekopu. Prostě jen popisuji, na co mám jiný názor nebo co bych doplnil.
O autora knihy v těchto článcích vůbec nejde. Poznámky na blog si zapisuji primárně proto, abych si utřídil myšlenky. Že při tom zmiňuji knihu, je především proto, abych je uvedl do kontextu.
Ale názor oněch „autorit“ mě obvykle taky zajímá. Už jsem si takhle povídal s Miloslavem Ponkrácem, Davidem Grudlem, Benjaminem Eberleiem, Miško Heverym (o jejichž dílech jsem na svém blogu psal) a teď jsem napsal i Stevu McConellovi – uvidíme, co odpoví.
Jakub Vrána : Jakub Vrána :
Steve mi na otázku, proč v kapitole o tabulkách vynechal hash tabulky, odpověděl, že mu šlo o to ukázat koncept tabulek jako takový bez ohledu na nějakou jejich konkrétní implementaci. Tedy rozdíl mezi logikou popsanou v kódu programu vs. v tabulce. A že pokud má programátor pocit, že se na nějakou úlohu hash tabulky hodí, tak ať je samozřejmě použije.
Jakub Vrána : 
Opravdový odborník :-):
Kvůli tomu jste mu nemusel psát - to je zřejmé z názvu kapitoly :-) Jde o řízení daty (nikoli algoritmem zadrátovaným v kódu), které má výhodu v tom, že 1) data lze načítat z externích zdrojů, takže chod programu může měnit i neprogramátor a není potřeba nic kompilovat 2) je to přehlednější než milion if/else nebo switchů a cyklů.
K tomu vašemu uspořádání větví v if/else vám nic nenapsal?
Opravdový odborník :-): Jakub Vrána :
Ptal jsem se jen na ty hash tabulky, což mě zajímalo nejvíc. A musím uznat, že mě odpověď poněkud zklamala – chtěl jsem se samozřejmě dozvědět trochu víc než jen to, co je zřejmé z názvu kapitoly.
Jakub Vrána : Opravdový odborník :-):
P.S. Navíc s J.V. někdy i souhlasím, třeba tady: http://zdrojak.root.cz/zpravicky/deset-entitov…-html-koderu/ takže nic ve zlém. Ale mějte se tu.
Opravdový odborník :-): Honza Marek:
Škoda. To budou zase dlouhá léta nudy, než se objeví další takový komediant :) Jakub Vrána :
Já nikde netvrdím, že by řešení pomocí SQL mělo být uvedeno přímo v knize. Jen jsem zmínil, jak bych k řešení problému přistoupil já.
Kniha „hlavně o algoritmizaci“ podle mě není. Podle mého názoru je především o snižování složitosti programů a o jejím zvládání. A delegace problémů na existující knihovny nebo nástroje je jednou z nejúčinnějších zbraní v tomto boji. Na to kniha podle mě příliš velký důraz neklade.
Naopak první ukázka je podle mě nešťastná i z toho nízkoúrovňového pohledu. Uvést poměrně složité řešení, které není optimální, i když v řadě prostředí existuje mnohem jednodušší řešení (jde přece o zvládání složitosti!), které zároveň optimální je, považuji za nedostatek. Částečně můžu mít pro autora pochopení (u čtenářů nepředpokládal znalost hašovacích tabulek a nechtěl je v knize rozebírat), ale to jsem vyjádřil už úvodem tohoto článku: „připadám si, jako kdyby programátor v C četl tipy pro asembler“.
Jakub Vrána : Diskuse je zrušena z důvodu spamu.
© 2005-2024 