Category Archives: Algo

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

Escape analysis

Dneska jenom krátce: Nedávno jsem zakopl o paper popisující partial escape analysis a napadlo mě, že bych tu mohl napsat pár slov o tom, co je escape analysis vlastně zač (termín s dovolením nebudu překládat a vystačím si s kurzívovou metodou). Escape analysis je … Continue reading 

Posted in Algo, JVM, VM | 8 Comments