Category Archives: Algo

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

Jak rychle řadit a šetřit čas

Když už tu mluvím o řazení a řadící mašinerii, tak bych taky mohl stručně a srozumitelně shrnout co, jak a proč dělat a čemu se vyhnout. Asi takhle: Obecné řadící algoritmy jako quicksort, mergesort nebo heapsort jsou super. Sami o sobě nejsou … Continue reading 

Posted in Algo, CPU, Paměť, řazení | 1 Comment

Jak řadit v lineárním čase, křísit mrtvé a dosáhnout osvícení

Když se řekne řazení, většina lidí, kteří napsali víc než jednu smyčku a dva ify se zeptá: „A je to nutné?“ Řazení nemá pověst nejrychlejší operace pod sluncem a je preferováno, když se tomu dá vyhnout např. hashováním. Někdy je to … Continue reading 

Posted in Algo, CPU, Paměť, řazení | 3 Comments