32000 sporočil Thomasa

A bo padel rekord v obiskanosti kot je padel na finance-on.net po objavi top100 bogatašev?

A še kdo komaj čaka tisto najbolj zanimivo temo, ki naj bi jo danes napisal Thomas?

Verjetno je mislil TOLE.

Čeprav moraš biti čisti geek, da kaj od napisanega 'poštekaš'.

@Thomas: Za tiste, ki niste "čisti geeki" najbrž ni tako zanimiv. Morda pa tudi?

Moram reči, da kljub svojemu (zelo skromnem) znanju programiranja ne razumem ničesar, toda očitno je zadeva velika.

kolikor jaz razumem( pa ne me obglavit če falim), je Thomasu uspelo najti trenutno najhitrejši sortirni algoritem celoštevilskih tabel. Ti sortirni algoritmi pač neurejena števila v tabelah(arrayjih) uredijo po vrsti, torej npr. od najmanjšega do največjega.

No ja, resnici na ljubo mislim, da boljšega od tega, ki ga računa Thomasov stroj, še dolgo časa ne bo.

Ampak, kot pravilno ugotavlja Thomas, optimizirat je treba tiste reči, ki so počasne in predstavljajo ozko grlo.

Jaz bi raje videl hitrejši FFT :)

Mene pa zanima kontra algoritem.
Tak, da bi podatke čim bolj premešal. In čim hitreje seveda.
Ampak RES premešal. (dobro premešani podatki sploh niso trivialno izvedljivi)

V praksi pa dobro deluje tudi tole.

 N=3;
 for (i=0;i<numberofrecord*N;i++) {
 
 r1=random(0,numberofrecords);
 r2=random(0,numberofrecords);
 swap r1,r2
 
 }
 

Tako greš samo 3 krat skozi in rezultat je kar dober. Lahko tudi N=1 ali N=10, stvar okusa.

No, tako tudi nekateri QuickSorti prerandomizirajo sortni file, da se izognejo degradaciji, o kateri smo govorili v sosednji temi. Za enormne arraye je to malenkost, it parkrat skozi, glede na itak potrebno količino prehodov. "Najprej dodatno umažeš, da lažje umiješ" sistem, ki lepo deluje!

1. random funkcija (generator) na raznih sistemih sploh ni neka trivialno enostavna zadeva
2. sicer ideja s prireditvijo random vrednostmi ni tako slaba
3. bi bilo treba malo prečekiati drsečo autokorelacijo (in morda še katero drugo statistično funkcijo) nad nizom

Kdor se ukvarja z varnostnimi algoritmi ve, da random funkcija sploh ni nekaj enostavnega.

a se verjetnost "neugodne tabele" sploh kaj zmanjsa s tem random trikom? v zelo bizarnem slucaju ga lahk ta random ravno posortira v obratnem zaporedju

sej, trik je glih to, da je tak primer ZELO bizaren in kot tak ustrezno malo verjeten. neugodne tabele so bol verjetne pa se jih splaca razmesart.