Category Archives: Algo

Radix merge sort

Nedávno jsem tu psal o divoké hybridizaci řadících algoritmů, která mě dovedla k mergeselectu. Teď bych chtěl v této cestě pokračovat. Metodou sledování os a hledání průsečíků jsem našel jedno nepokryté místo: Radixovou obdobu merge sortu. Quicksort má radixovou verzi (radixsort) a proto … Continue reading 

Posted in Algo, řazení | Leave a comment

Iterace křížem krážem

Tenhle článek bych klidně mohl začít clickbait titulkem: „Jeden neuvěřitelný trik, který zrychlí vaše programy,“ a ani bych se za to nestyděl. Asi takhle: Když zpracovávám hromadu dat v několika průchodech (které z nějakých důvodů není možné spojit do jednoho), může nastat … Continue reading 

Posted in Algo, CPU, low level | Leave a comment

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