Category Archives: Algo

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

diff a komprese

Někdy se zkrátka daří. Celé dny se nestane nic a pak přijde den, kdy zjistím, jak funguje unixová utilita diff a použiji těchto znalostí, abych komprimoval 3× rychleji a 70× lépe než ctihodný gzip. Ale začnu popořadě. Mám dataset, který je … Continue reading 

Posted in Algo | 8 Comments

Mergeselect

Quickselect všichni známe a milujeme – jde o algoritmus pro nalezení k-tého nejmenšího prvku neseřazeného pole v průměrném čase O(n). Jediný jeho nedostatek je, že v patologických případech může běžet v čase O(n2). Quicksort to má ale stejně a je to součást dohody, kterou jsme … Continue reading 

Posted in Algo, řazení | 5 Comments