Category Archives: Algo

Dobrý odhad vydá za tisíc přesných počtů

Původně jsem chtěl napsat něco obecného o pravděpodob­nostních algoritmech a užitečnosti rychlých odhadů, ale nemám na to sílu. Místo toho jsem vybral pár článků a paperů, které se týkají tématu, roztřídil je na obecné a ty o Bloom filtrech, HyperLogLogách, Count-min skečích … Continue reading 

Posted in Algo, Paper | Leave a comment

Radix merge sort

Nedávno jsem psal o divoké hybridizaci řadících algoritmů, která mě dovedla k mergeselectu. Teď budu v započaté cestě pokračovat. Metoda sledování os a hledání průsečíků ukázala jedno nepokryté místo: Radixovou obdobu merge sortu. Quicksort má radixovou verzi (radixsort) a proto by mělo být … 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