Category Archives: Algo

Lokalita v grafech a negrafech

Dneska jen krátce a stručně. V posledních dnech jsem hodně četl o garbage collectorech. Byla to zajímavá exkurze do pulzujících střev virtuálních strojů, ale o tom teď nechci psát. Chci se zmínit o něčem mnohem menším a skromnějším, co mě nejspíš napadlo po masáži … Continue reading 

Posted in Algo, CPU | Leave a comment

Vstříc řazení v lineárním čase

Obecné řazení v lineárním čase je meta, které není možné dosáhnout1. Ve výsledné složitosti se vždycky vyskytne log(n) faktor. Může být maskovaný za něco jiného, ale vždycky tam bude. Třeba takový LSD radix sort má složitost O(kn), kde k je právě … Continue reading 

Posted in Algo, řazení | 2 Comments

Od pohledu dobrý, aneb jak najít skoro stejné obrázky mezi dvěma miliony souborů za méně než deset minut

A tenhle znáte: „Proč je Pentium rychlejší než 486? 486 počítá, ale Pentium jen odhaduje.“ Přestože jde o nejapný vtip o chybě v prvních Pentiích z počítačového pravěku, má v sobě zrnko pravdy: Odhad může být mnohem rychlejší než přesný výpočet. Odhad, pokud chci, aby byl k něčemu … Continue reading 

Posted in Algo, DS | Leave a comment

YOLO tree

Stará internetová moudrost říká „you only live once“. Život je příliš krátký na jistoty a někdy to prostě musíme risknout. Jako třeba během konstrukce binárního vyhledávacího stromu (BST). BST je super věc, všichni ho známe, milujeme a napíšeme si jeden nebo … Continue reading 

Posted in Algo | Leave a comment

diff a stromy

Minule jsem tu psal, jak dělat diffy a jak se tato znalost dá využít pro kompresi dat. Teď bych chtěl jít o krok dál k diffování libovolných stromů. Už tehdy jsem se zmínil, že jsem o tom chvíli přemýšlel, ale jako vždycky jsem … Continue reading 

Posted in Algo | Leave a comment