Author Archives: Karel Čížex

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

Maximálně negativní

Když už jsem v tom, tak bych po minulém článku, tu mohl zmínit dvě drobnosti, které se nesou v podobném duchu. Jedna je jakž takž užitečná a druhá je jen intelektuální kuriozita. #1 Nějakou dobu jsem ve Scale při řazení podle intů … Continue reading 

Posted in CPU, low level | Leave a comment

99.00000000000000009 problémů s floating point čísly

Floating point čísla a jejich IEEE 754 varianta jsou jednou z těch věcí, které mě nikdy nepřestanou fascinovat. Jde o užitečnou věc, která člověka skoro přesvědčí, že všechno bude ok, že svět má svůj řád, že se stačí odevzdat floating vlnám a už … Continue reading 

Posted in low level | 2 Comments

Závislost je špatná (pro vaše programy i pro váš hardware)

Když jsem nedávno civěl do zdrojáků knihovny breeze, narazil jsem na kód pro slakární součin, který vypadal zhruba takhle: double sum0, sum1, sum2, sum3 = 0.0; // … for(int i = 0; i < length; i += 4) { sum0 … Continue reading 

Posted in CPU | 2 Comments