Digitalna evolucija @ Slo-Tech

Forum » Znanost in tehnologija »
Digitalna evolucija

Digitalna evolucija

«« «

12 / 29

»»»

Thomas :: 26. apr 2004, 22:42

No, zadeva je obrnjena. 10 krat narobe v drugo smer, po moje. To pa tudi ni cool.

Bo treba objavit source in poskusit!

Man muss immer generalisieren - Carl Jacobi

OwcA :: 26. apr 2004, 22:45

Tu igra strojna oprema, optimiziranost sistema in kode zadostno vlogo.

Otroška radovednost - gonilo napredka.

Thomas :: 26. apr 2004, 22:55

Bo treba posortat 100 milijonov (milijardo) števil. Meritve bodo potem bistveno zaneslivejše.

Seveda pa potrebujemo izvorno kodo, da bomo vedeli o čem govorimo.

Man muss immer generalisieren - Carl Jacobi

Gizm0 :: 26. apr 2004, 23:10

Bilo je testirano na P4 2.4. Uporabljam pa Javo 1.4.2.

//generiram random tabelo (v našem primeru je m=2)
for(int x=0; x < n; x++)
  field1[x]=(int)(Math.random()*m);
//klic funkcije
bucketSort(field1,m);

//bucketsort algoritem
public static void bucketSort(int[] a, int m){
  int[] buckets = new int[m];		
  for (int i = 0; i < a.length; ++i)
    ++buckets [a [i]];
  for (int i = 0, j = 0; j < m; ++j)
    for (int k = buckets [j]; k > 0; --k)
      a [i++] = j;
}

hmm... kako omogočim, da bo pastana koda imela prave zamike na tem forumu (code /code ne deluje)

Zanimivo, zdaj sem šel sprobat na p2 300mhz in rezultati so:
severalUniqueSort 849.0 ms
twoUniqueSort 592.0 ms
bucketSort 640.0 ms

Zgodovina sprememb…

spremenil: Gizm0 (26. apr 2004 ob 23:31)

Thomas :: 26. apr 2004, 23:21

Povečaj array, da boš dobil manj random odvisen rezultat!

Sicer je pa tako, da TALE Bucket mora it 2X skoz enkrat za preštevanje, drugič za pisanje.

TwoUniqueu ni treba narediti dveh celih prehodov.

Man muss immer generalisieren - Carl Jacobi

OwcA :: 26. apr 2004, 23:26

Pravilen prikaz (upoštevanje zamikov in dopuščanje seh znakov) kode lahko dosežete z uporabo taga [ st.koda jezik] (brez presledka med [ in st).

V za kodo zgoraj bi tako zapisali:
[ st.koda java]
...
[ /st.koda]

Otroška radovednost - gonilo napredka.

CaqKa :: 26. apr 2004, 23:26

gizmo:
oglati oklepaj st.koda ogalti zaklepaj koda oglati oklepaj /st.koda oglati zaklepaj

CaqKa :: 26. apr 2004, 23:28

kako pa bi st kodo zapisal?
[ st.koda st.koda] st koda [ /st.koda] ?

Gizm0 :: 26. apr 2004, 23:29

Fora tega bucketa je, da ne dela nič primerjav. Primerjave pa so za procesor "dražje" kot pa samo vstavljanje iz enega arraya v drugo. Mislim, da tu nastane ta razlika.

Thomas :: 26. apr 2004, 23:35

Zdej sem dal s Critticallom optimizirat še Bucket čez noč.

Jutri bomo pa nardili komplet meritve.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 27. apr 2004, 10:12

Po čeznočni Critticall optimizaciji in po analiziranju kode smo prišli do tehle zaključkov:

1 - Algoritem (Bucket), ki ga je dal Gizmo je skoraj 2X hitrejši kot TwoUnique in je skoraj 3X hitrejši od SeveralUnique sorta. Zelo tako, kot je dal Gizmo rezultate.

2 - Ta Bucket algoritem NE DELUJE za veliko večino primerov . Deluje samo za 0,1 ali 0,1,2 oziroma za primere iz ozkega intervala. Za primer, ko bi morali posortati števili 1907 in 4449876543210, ki se vsako pojavlja naprimer 5 milijonkrat - bi trajalo leta! Če bi sploh bilo dovolj memorije na celem svetu.

3 - Bucket je matematični sort, ki stringov ne znajo sortirati.

4 - Obravnava teh matematičnih sortov (ki so tudi pomembni, a je povsem druga specifika) bo neko drugo poglavje Critticalla.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 27. apr 2004, 13:19

No, ko smo še nekoliko stestirali Bucket : SeveralUnique, smo ugotovili, da smo prej za SeveralUnique uporabljali 64 bitne, za Bucket pa 32 bitne spremenljivke.

Ko smo zadevo izenačili, NI BIL Bucket NIKOLI hitrejši! Pri 32000 unique recordih med 5 milijoni, napaca Bucketa za 50%. Quickija pa za faktor 5 (=500%).

Vse kar Critticall pogrunta, stestiramo pod 64 bitnimi integerji, v kodi za Bucket ki jo je dal Gizmo, je bila pa 32 bitna koda pač vdelana z INT deklaracijami.

Človeška napaka, Critticall je imel skozi prav. Kar je pomembno je pa to, da je SeveralUnique samo eden peklenskih žrebcev iz štale Critticall.

Meni sinoči ni bilo jasno, kako da Critticall doslej ni iznašel Bucketa, če je ta tako dober. Odgovor je preprost. Zavrgel ga je verjetno že mnogokrat, takoj ko ga je šele napol videl. Ker je Bucket preslab.

8-)

Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

spremenil: Thomas (27. apr 2004 ob 13:20)

Gizm0 :: 27. apr 2004, 14:23

Jaz sem tako pri bucketu kot pri severalUnique uporabljal 32-bitne spremenljivke.

Vendar sem ponavjajoče cifre vedno izbral samo od 0 do m. To pomeni, da so bile v tistih 5 milijonih samo cifre od 0 do 10 (če je bil m=10). Če za ponavljajoča števila izberemo katerokoli od 5 milijonov, potem zgornja verzija bucketSorta ne deluje prav dobro.

BucketSort vedno naredi samo 2 prehoda čez vse cifre. Če jih severalUnique naredi toliko, kolikor je različnih cifer, kako je potem lahko hitrejši?

Sem pa že zgoraj omenil, da bucketSort ne dela primerjav. Zdaj je pa treba pogledat v samo arhitekturo CPUja, koliko časa porabi za primerjavo. Tudi, če algoritem rabi manj prehodov skozi zanke in ima več primerjav, je lahko počasnejši od tistega, ki nima primerjav in ima več prehodov.

Radix sort je en tak algoritem, ki tudi nima primerjav.

A s tistimi verzijami QuickSorta si se že kaj ukvarjal?

Thomas :: 27. apr 2004, 14:46

Ja ti si uporabljal Javo, ane?

V MS C++ je tko, kot sem rekel.


 
 void uniquesort() {
 //SeveralUnique
 int o=0;
 int p=0;
 int n=0;
 int k=0;
 int l=0;
 int i=0;
 int maximumsize=5000000;
 o=0; p=1; n=maximumsize; k=1;
 while (k>=i) {
 k=-1;
 while (n>k) {
 k++; l=array[k];
 if (j>l) { array[i]=l; i++; array[k]=j; }
 if (l>j) { i=k; j=array[k]; }
 }
 j=0; n=i-p;
 }
 }

Tole naj na arrayu s 5 milijoni recordov skompilira v C++, kdor hoče.

> Če jih SeveralUnique naredi toliko, kolikor je različnih cifer, kako je potem lahko hitrejši?

Just try it!

> Radix sort je en tak algoritem, ki tudi nima primerjav.

Tudi to je matematični sort. Res nima primerjav, ampak zato tudi ne zna sortirati splošnih stringov. Samo take flex, s fiksno dolžino. Ni tako dober, kot se splošno misli dandanes. Mu bo mogoče Critticall vdihnil nekaj novega življenja.

> A s tistimi verzijami QuickSorta si se že kaj ukvarjal?

Katerikoli je najboljši, ga bom dal žvečiti Critticallu.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 27. apr 2004, 16:01

Še en problemček mamo. Random generator za vhodno datoteko je še vedno 64 biten in to nekaj ne dela prav. Tako da je vprašanje, koliko jih je med 30000 res različnih ... Je nekaj na tem kar pravi Gizmo.

Will be fixed!

Man muss immer generalisieren - Carl Jacobi

Thomas :: 28. apr 2004, 14:59

n=maximumsize-1;

Tko mora biti!

Index elementov gre od 0 do maximumsize-1.

Kar se tiče hitrosti, pri dveh unique je čas enak za Bucket in Several unique.

FYI, Bucket je pa popolnoma neuporabna zadeva. Kdor ne verjame, naj z Bucketom posorta tole

10000000000
1000000000
10000000
10000
100
8

Polega tega Bucket zahteva, da je cel record sortni ključ. Če ni, izgubi vse, kar ni sortni ključ.

Res. To zaradi tega ker ne primerja (takoimenovani logični sorti primerjajajo), pač pa postavlja vrednosti.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 30. apr 2004, 17:29

Trudmo se ...

Man muss immer generalisieren - Carl Jacobi

McHusch :: 1. maj 2004, 08:07

Tole je sicer neumestno, ampak me je vseeno zbodlo v oči med brskanjem po Critticallovi strani.

Information je nešteven, zato ne morejo biti informations, ampak so information.

Ja, ja, vem da sem malenkosten.

Zgodovina sprememb…

spremenil: McHusch (1. maj 2004 ob 08:07)

Thomas :: 1. maj 2004, 08:20

Kar on očita, koj popravi!

(Pa sploh ne misli, da ne bi smel on še (marsi)česa pripomniti.)

Man muss immer generalisieren - Carl Jacobi

Rok Nemec :: 2. maj 2004, 23:28

Približno pol leta nazaj sem se igral z FlashSort algoritmom O(n), vendar mi ga ni uspelo realizirati v Critticall source, ker le-ta ne podpira realna števila. Mislim, da bi bili rezultati optimizacije tega algoritma precej zanimivi, zato objavljaml še ne delujoč source za flashsort algoritem.V primeru da se da komu popravit tale source, ter ga ponuditi criticall-u, naj posta rezultate.

Link do pascal style kode za FlashSort: http://www.neubert.net/Flapaper/9802n.h...

Še ne delujoč source za FlashSort:

//flashsort

$dimension a[5120] 
$rinvar a[](0,936583921)
$RINVAR a[](0,85)
$RINVAR a[](2676,85898)
$RINVAR a[](1954435679,2147483647)
$RINVAR a[](22222,23333)
$RINVAR a[](7765,858987)
$RINVAR a[](11111,9999999)
$RINVAR a[](9677777,9999958)
$RINVAR a[](14676323,87435898)
$RINVAR a[](1204,8533)
$RINVAR a[](776532,8589874)
$RINVAR a[](55502,755555)
$RINVAR a[](9677777,9999958)
$RINVAR a[](999192676,999999999)
$RINVAR a[](954435679,2147483647)

$retvar a[]

$minimize lines 160

$BES   
         elements=5120;
	   x=0; 
         y=1;
         i = 0;
         k = 0;
         c=0;
         temp1=0;
         temp2=0;
         temp4=0;
         temp5=0;
         tmp=0;
         xx=0;
         dva=2;
         utez = 1000;
         xy=0;
         xz=0;
         zz=0;
         anmin = a[y];
         nmax  = 1;
         trideset=30;
         dvajset=20;
         m=n/dvajset;
         if (m < trideset){
	   m = trideset;
	   }
         for (i=y; i < elements; i+=y){
            temp1=a[i];
             if (temp1 < anmin){
             anmin=a[i];
             }
            temp2 = a[nmax];
            if (temp1 > temp2){ 
            nmax=i;            
        	}
        }        
        temp2 = a[nmax];
        if (anmin != temp2){
        xx = temp2 - anmin;      
        xy= m-y;
        xy=xy*utez;
        c = xy/xx; 
        for (i=y; i < elements; i+=y){ 
            temp1=a[i];
            xz= temp1-anmin;

		    k=c*xz;
		    k = k/utez;
                k++;
            zz=arr256[k];
            zz = zz+y;
            arr256[k] = zz;
        }
        for (k=dva; k < m; k+=y){
          zz = arr256[k];
          xy = k-y;
          xz = arr256[xy];
          zz = zz + xz;
          arr256[k] = zz;
        }
         hold = a[nmax];
        zz = a[y];
        a[nmax]=zz;
        a[y]=hold;
//permutacija
         nmove = 0;
         flash=0;
        j=1;
        k=m;
        zz = elements - y;
        xz = arr256[k];
        while (nmove < zz){
            while (j > xz){
                j++;
                temp2=a[j];
                temp1=temp2-anmin;
                k =c * temp1;
		    k = k/utez;
                k++;
                xz = arr256[k];
            }
            flash = a[j];
            tmp = arr256[k];
		tmp++;
            while (j != tmp){
                temp2=flash - anmin;
                k = c * temp2;
                k = k/utez;
                k++;
                xz = arr256[k];    
                hold = a[xz];
                a[xz]=flash;
                flash = hold;
                xz = xz - y;
                arr256[k]=xz;
                nmove++;
                tmp =xz;
		    tmp++;
            }
        xz = arr256[k];
	}  
    }    
$EES

LP

[dopolnil odgovor tako, da uporablja barvanje sintakse -OwcA]

Zgodovina sprememb…

spremenilo: OwcA (3. maj 2004 ob 01:04)

Thomas :: 3. maj 2004, 11:47


 
 $declareint x num nmin nmax cnum i hold c1 c2 k nmove j flash tmpi tmpm tmp1 tmp2 df tmp num1 lk num2 i1 ai1 j1 aj1 zero one
 $dimensions A[101] L[101]
 $rinvar A[](1,99)
 //$rinvar A[](1,1)
 //$rinvar A[](-100,40)
 //$cases 30
 $retvar A[]
 //$enhancing off
 cnum=30; //number of classes
 num=100;
 one=1;
 $BES
 
 
 
 //PROCEDURE Class;
 
 nmin=1;
 nmax=1;
 for (i=one;i<=num;i++) {
 //if A[i] < A[nmin] {nmin=i;}
 
 tmpi=A[i];
 tmpm=A[nmin];
 if (tmpi<tmpm) {nmin=i;}
 
 //if A[i] > A[nmax] {nmax=i;}
 tmpi=A[i];
 tmpm=A[nmin];
 if (tmpi>tmpm) {nmax=i;}
 
 }
 
 
 
 
 //c1=( cnum - 1 ) / ( A[nmax] - A[nmin]);
 c1=cnum;
 c1--;
 tmp1=A[nmax];
 tmp2=A[nmin];
 df=tmp1-tmp2;
 c1=c1/df;
 
 //c2= c1 * A[nmin];
 c2= A[nmin];
 c2=c2*c1;
 
 
 
 
 for (k=one;k<=cnum;k++) {
 L[k]=zero;
 }
 
 for (i=one;i<=num;i++) {
 // k=1 + ( c1 * A[i] - c2 );
 
 tmp=A[i];
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 
 
 // L[k]=L[k]+1;
 tmp=L[k];tmp++;L[k]=tmp;
 
 
 }
 
 for (k=2;k<=cnum;k++) {
 //L[k]=L[k] + L[k-1];
 tmp1=L[k];
 tmp=k;tmp--;
 tmp2=L[tmp1];
 tmp1=tmp1+tmp2;
 L[k]=tmp1;
 
 HOLD= A[nmax];
 A[nmax]=a[1];
 A[1]=HOLD;
 }
 
 
 NMOVE=0;
 j=1;
 k=cnum;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 num1=num;num1--;
 while (nmove < num1) {
 lk=L[k];
 while (j > lk) {
 j++;
 if (j>num) {goto ven;}
 
 //k=1 + ( c1 * A[j] - c2 )
 tmp=A[j];
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 lk=L[k];
 }
 
 
 
 
 FLASH=A[j];
 lk=L[k];lk++;
 while (j != Lk) {
 //k= 1 + ( c1*FLASH - c2 );
 tmp=FLASH;
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 
 
 //HOLD=A[L[k]];
 lk=L[k];
 HOLD=A[lk];
 //A[L[k]]=FLASH;
 A[lk]=FLASH; 
 //L[k]=L[k]-1;
 lk--;
 L[k]=lk;
 if (lk<zero) {L[k]=zero; goto ven;}
 if (lk>num) {L[k]=num; goto ven;}
 FLASH=HOLD;
 nmove++;
 lk=L[k];lk++;
 
 }
 }
 ven:; 
 
 num2=num;num2--;
 //num2--;
 for (i=num2;i>=one;i--) {
 //if A[i+1] < A[i] {
 i1=i;i1++;ai1=A[i1];
 if (Ai1 < A[i]) {
 HOLD=A[i];
 j=i;
 j1=j;j1++;aj1=A[j1];
 while (Aj1 < HOLD) {
 
 A[j]=Aj1;
 j++;
 if (j==num) {break;}
 j1=j;j1++;aj1=A[j1];
 }
 A[j]=HOLD;
 }
 }
 
 
 $EES
 
 for (k=one;k<num;k++) {
 tmp=k; tmp++;
 if (a[k] > a[tmp]) {tmp/=0;}
 }

Tole je flash, lahko da je linearen, ampak dela pa grozno počasi. To se zadnje leta eni nekej grejo s praktično precej neuporabnimi algoritmi. Svojo moč bi pokazali šele pri takem številu rekordov, ki ga sploh nikoli nimamo, ali pa bi dobro faktorizirali števila ki so prevelika, da bi tudi tisto "dobro" faktorizacijo kakorkoli lahko uporabili. Zaenkrat mislim da je tako tudi s flashem.

Zadeva pa deluje in PUŠČA nulti rekord pri miru. Sorta od 1 naprej.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 3. maj 2004, 12:24


 $declareint x num nmin nmax cnum i hold c1 c2 k nmove j flash tmpi tmpm tmp1 tmp2 df tmp num1 lk num2 i1 ai1 j1 aj1 zero one
 $dimensions A[101] L[101]
 $rinvar A[](1,99)
 //$rinvar A[](1,1)
 //$rinvar A[](-100,40)
 //$cases 30
 $retvar A[]
 $showvar L[]
 $resvar num,one,zero
 //$enhancing off
 cnum=30; //number of classes
 num=100;
 one=1;
 $BES
 //PROCEDURE Class;
 nmin=0;
 nmax=0;
 for (i=zero;i<=num;i++) {
 //if A[i] < A[nmin] {nmin=i;}
 tmpi=A[i];
 tmpm=A[nmin];
 if (tmpi<tmpm) {nmin=i;}
 //if A[i] > A[nmax] {nmax=i;}
 tmpi=A[i];
 tmpm=A[nmin];
 if (tmpi>tmpm) {nmax=i;}
 }
 //c1=( cnum - 1 ) / ( A[nmax] - A[nmin]);
 c1=cnum;
 c1--;
 tmp1=A[nmax];
 tmp2=A[nmin];
 df=tmp1-tmp2;
 c1=c1/df;
 //c2= c1 * A[nmin];
 c2= A[nmin];
 c2=c2*c1;
 for (k=one;k<=cnum;k++) {
 L[k]=zero;
 }
 for (i=one;i<=num;i++) {
 // k=1 + ( c1 * A[i] - c2 );
 tmp=A[i];
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 // L[k]=L[k]+1;
 tmp=L[k];tmp++;L[k]=tmp;
 }
 for (k=2;k<=cnum;k++) {
 //L[k]=L[k] + L[k-1];
 tmp1=L[k];
 tmp=k;tmp--;
 tmp2=L[tmp1];
 tmp1=tmp1+tmp2;
 L[k]=tmp1;
 HOLD= A[nmax];
 A[nmax]=a[one];
 A[one]=HOLD;
 }
 NMOVE=0;
 j=zero;
 k=cnum;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 num1=num;num1--;
 while (nmove < num1) {
 lk=L[k];
 while (j > lk) {
 j++;
 if (j>num) {goto ven;}
 //k=1 + ( c1 * A[j] - c2 )
 tmp=A[j];
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 lk=L[k];
 }
 FLASH=A[j];
 lk=L[k];lk++;
 while (j != Lk) {
 //k= 1 + ( c1*FLASH - c2 );
 tmp=FLASH;
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 //HOLD=A[L[k]];
 lk=L[k];
 HOLD=A[lk];
 //A[L[k]]=FLASH;
 A[lk]=FLASH;
 //L[k]=L[k]-1;
 lk--;
 L[k]=lk;
 if (lk<zero) {L[k]=zero; goto ven;}
 if (lk>num) {L[k]=num; goto ven;}
 FLASH=HOLD;
 nmove++;
 lk=L[k];lk++;
 }
 }
 ven:;
 num2=num;num2--;
 //num2--;
 for (i=num2;i>=zero;i--) {
 //if A[i+1] < A[i] {
 i1=i;i1++;ai1=A[i1];
 if (Ai1 < A[i]) {
 HOLD=A[i];
 j=i;
 j1=j;j1++;aj1=A[j1];
 while (Aj1 < HOLD) {
 A[j]=Aj1;
 j++;
 if (j==num) {break;}
 j1=j;j1++;aj1=A[j1];
 }
 A[j]=HOLD;
 }
 }
 $EES
 for (k=zero;k<num;k++) {
 tmp=k; tmp++;
 if (a[k] > a[tmp]) {tmp/=0;}
 }

No, tole zdej deluje tudi za nulti element. Ampak če nisem kaj zgrešil, je totalno brez vezen algoritem. Žal.

Ga pa Critticall seveda zna popravt

Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

spremenil: Thomas (3. maj 2004 ob 12:26)

attackiko :: 3. maj 2004, 19:46

Mogoče bi blo zanimivo, če bi ti ratal uvrstit kako novico o izboljšanem algoritmu na Slashdot. Potem bi se takoj en kup ljudi začelo ukvarjat s Critticallom..

Rok Nemec :: 3. maj 2004, 21:07

Hvala, Thomas za tako hiter odgovor!

Res je, da ima algoritem bolj akademsko vrednost, vendar je pri sortiranju vellike tabele precej hiterjši od Quick-Sorta (graf je prikazan na povezavi, tudi sam sem stestiral zadevo). Predvsem je uporaben pri kakih seminarskih nalogah, ko je treba čim hitreje nekaj posortirati . Mogoče bo na uporabi pridobil šele čez 10-20 let.

Torej ta algoritem sigurno NI primeren za sortiranje 100 števil.

če koga zanima link do java sourca :
http://bobcat.webappcabaret.net/javachi...

LP

Zgodovina sprememb…

spremenil: Rok Nemec (3. maj 2004 ob 21:14)

Thomas :: 3. maj 2004, 21:21

attackiko,

Ideja je sicer uredu in jo bo treba izvest. Vendar za Slashdot uredništvo je tole zaenkrat še prehudo. Mora pridet po ovinku tja, skozi članke v revijah.

"I am too cool to admire anybody's software!"

"They have done this in '70!"

Ampak eno stopničko na poti v New York Times - Wikipedio - smo prestopili v zadnjih par dneh. En obskuren dosežek Critticalla - Several Unique Sort - je nekaterim kljub začetnemu skepticizmu dal mislit. Ker so v principu konstruktivni, so se celo potrudili prevest algoritem v Angleščino, ga razumet in dati spremenljivkam v C programu krščanska imena, tako da zdej še jest vem, kako zadeva pravzaprav počne tisti svoj sorting.

Še nekaj novih algoritmov s članki sem in tja bo treba postavt (mathworld, Wired, JSL ...), potem bodo šele "mainstream programerji" pripravljeni pomisliti na to, da so njihovi algoritmi in kosi "navadne kode" najbrž kar bogi - če pripustijo Critticall ... se to jasni vidi. Ker če Dijkstrovi možgani niso močnejši kot Critticall ...

Škoda, ker je tipček umru 2002!

Man muss immer generalisieren - Carl Jacobi

Thomas :: 3. maj 2004, 21:24

Jeff,

Tale algoritem ki sem ga dal je preveden iz pascala. Zato utegne biti bolj tko tko.

Zdej mam enga prevedenega iz Fortrana:


 
 $declareint x num nmin nmax cnum i hold c1 c2 k nmove j flash tmpi tmpm tmp1 tmp2 df tmp num1 lk num2 i1 ai1 j1 aj1 zero one
 $dimensions A[101] L[101]
 $rinvar A[](1,9)
 //$rinvar A[](1,1)
 //$rinvar A[](-100,40)
 //$cases 30
 $retvar A[]
 $showvar L[]
 $resvar num,one,zero
 //$enhancing off
 cnum=9; //number of classes
 num=100;
 one=1;
 $BES
 
 
 
 //PROCEDURE Class;
 
 nmin=0;
 nmax=0;
 for (i=zero;i<=num;i++) {
 //if A[i] < A[nmin] {nmin=i;}
 
 tmpi=A[i];
 tmpm=A[nmin];
 if (tmpi<tmpm) {nmin=i;}
 
 //if A[i] > A[nmax] {nmax=i;}
 tmpi=A[i];
 tmpm=A[nmin];
 if (tmpi>tmpm) {nmax=i;}
 
 }
 
 
 
 
 //c1=( cnum - 1 ) / ( A[nmax] - A[nmin]);
 c1=cnum;
 c1--;
 tmp1=A[nmax];
 tmp2=A[nmin];
 df=tmp1-tmp2;
 c1=c1/df;
 
 //c2= c1 * A[nmin];
 c2= A[nmin];
 c2=c2*c1;
 
 
 
 
 for (k=one;k<=cnum;k++) {
 L[k]=zero;
 }
 
 for (i=one;i<=num;i++) {
 // k=1 + ( c1 * A[i] - c2 );
 
 tmp=A[i];
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 
 
 // L[k]=L[k]+1;
 tmp=L[k];tmp++;L[k]=tmp;
 
 
 }
 
 for (k=2;k<=cnum;k++) {
 //L[k]=L[k] + L[k-1];
 tmp1=L[k];
 tmp=k;tmp--;
 tmp2=L[tmp1];
 tmp1=tmp1+tmp2;
 L[k]=tmp1;
 
 HOLD= A[nmax];
 A[nmax]=a[one];
 A[one]=HOLD;
 }
 
 
 NMOVE=0;
 j=zero;
 k=cnum;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 num1=num;num1--;
 while (nmove < num1) {
 lk=L[k];
 while (j > lk) {
 j++;
 if (j>num) {goto ven;}
 
 //k=1 + ( c1 * A[j] - c2 )
 tmp=A[j];
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 lk=L[k];
 }
 
 
 
 
 FLASH=A[j];
 lk=L[k];lk++;
 while (j != Lk) {
 //k= 1 + ( c1*FLASH - c2 );
 tmp=FLASH;
 tmp=tmp*c1;
 tmp=tmp-c2;
 tmp++;
 k=tmp;
 if (k<zero) {k=zero;}
 if (k>num) {k=num;}
 
 
 //HOLD=A[L[k]];
 lk=L[k];
 HOLD=A[lk];
 //A[L[k]]=FLASH;
 A[lk]=FLASH; 
 //L[k]=L[k]-1;
 lk--;
 L[k]=lk;
 if (lk<zero) {L[k]=zero; goto ven;}
 if (lk>num) {L[k]=num; goto ven;}
 FLASH=HOLD;
 nmove++;
 lk=L[k];lk++;
 
 }
 }
 ven:; 
 
 num2=num;num2--;
 //num2--;
 for (i=num2;i>=zero;i--) {
 //if A[i+1] < A[i] {
 i1=i;i1++;ai1=A[i1];
 if (Ai1 < A[i]) {
 HOLD=A[i];
 j=i;
 j1=j;j1++;aj1=A[j1];
 while (Aj1 < HOLD) {
 
 A[j]=Aj1;
 j++;
 if (j==num) {break;}
 j1=j;j1++;aj1=A[j1];
 }
 A[j]=HOLD;
 }
 }
 
 
 $EES
 
 for (k=zero;k<num;k++) {
 tmp=k; tmp++;
 if (a[k] > a[tmp]) {tmp/=0;}
 }

Ta pa tudi nekej ne dela povsem prav. Ni pa tko beden kot zgornji! To pa res.

Grem zdej na tvojo Java kodo!

Man muss immer generalisieren - Carl Jacobi

Rok Nemec :: 3. maj 2004, 22:02

Hmmm
Kaj pa tale (ABC sort): http://www.beechick-sort.bizhosting.com...

Thomas :: 3. maj 2004, 22:47

Kakorkoli že uporabnega se bo našlo med sorti, planiram to vreči v Critticall. Narediti celo dedicated exete, ki bodo izboljševali vsak svoj sort algoritem in samo ta algoritem in bodo prosti, kot tisti Chess_Citadele.

Preprosto pokazati, da do koder že lahko pridejo ljudje, Critticall gre še naprej. Včasih samo še malo, včasih več, včasih pa kar odločno.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 4. maj 2004, 19:03

Ravnokar se je rodil en (kompliciran) sort, hitrejši od t.i. fastquicksorta.

Čin!

Man muss immer generalisieren - Carl Jacobi

Thomas :: 4. maj 2004, 22:15

Sourceti. Tanovi sort je QuickSortX, je pa še precej drugih zraven. You may try them!

_{Meantime ... smo že prišli do boljšga.}

Man muss immer generalisieren - Carl Jacobi

snow :: 5. maj 2004, 18:38

Hmm link mi ne dela? :)

Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas :: 5. maj 2004, 19:08

Ma ja, ne dela. Disertiram ravno tole.

Tako imenovani fastquicksort odnosni introsort smo uspeli derecurzivirat in zdej ga Critticall obdeluje. O tem pišem, dokumentiramo, testiramo ...

But so far very good! Tisti cpp file je bil pa napol HTML ... bomo uštimal!

Man muss immer generalisieren - Carl Jacobi

Thomas :: 6. maj 2004, 09:02

Source.

Exe.

Zanimajo me številke, kakršne vam napiše exe. Hvala lepa, komur se da.

Man muss immer generalisieren - Carl Jacobi

DoberMan :: 6. maj 2004, 09:34

1 poskus
fastQS 922
doctoredQS 1109
QS 1109
QSX 875

2 poskus
fastQS 906
doctoredQS 1109
QS 1110
QSX 875

Thomas :: 6. maj 2004, 09:55

Hvala, dobr, DoberMan ...

Tale QSX je ena early verzija, posledica napadov Critticalla direktno na QuickSort ... Sourceti so itak zraven.

Kaže tako, da primere podatkov za sort se da razdeliti na ene 100 ali še več razredov in da za vsak razred je svoj sort. Odvisno od števila recordov, od trenutne posortanosti, od števila različnih recordov, od te ali one disperzije na vhodnih podatkih ... Critticall jih lahko razvije "bez po muke".

Je pa en zanimiv twist. Pri t.i. FQS poznanim tudi kot introspekcijski sort (manjše chunke podvrže nekemu drugemu in ne QS) je najboljši ravno Several Unique. Namesto Insertion ali Heapsorta ki se uporabljata pri teh dveh. Samo Critticall potem (zgleda) zavije (še) v eno drugo smer izboljševanja ...

Man muss immer generalisieren - Carl Jacobi

snow :: 6. maj 2004, 10:15

fastquicksort 797
doctoredquicksort 884
quicksort 904
quicksortx 750

$:\$

Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

noraguta :: 6. maj 2004, 10:18

evo še malo igranja z optimizacijami.

cl /G7 /arch:SSE2 qs.cpp

fastQuickSort 1156 Press any key to continue . . .
doctoredQuickSort 1531 Press any key to continue . . .
QuickSort 1625 Press any key to continue . . .
QuickSortX 1391 Press any key to continue . . .

cl qs.cpp

fastQuickSort 1157 Press any key to continue . . .
doctoredQuickSort 1719 Press any key to continue . . .
QuickSort 1625 Press any key to continue . . .
QuickSortX 1047 Press any key to continue . . .

(mnja bi moral malo povečat število sortov , vtem času se mi procesor niti ne preklopi na full speed)

jej sem ga polomu. no tole so pravi rezultati z optimizacijo

cl /G7 /arch:SSE2 /Oi /Og qs.cpp

fastQuickSort 2250 Press any key to continue . . .
doctoredQuickSort 2860 Press any key to continue . . .
QuickSort 2609 Press any key to continue . . .
QuickSortX 2391 Press any key to continue . . .

cl qs.cpp

fastQuickSort 5204 Press any key to continue . . .
doctoredQuickSort 5422 Press any key to continue . . .
QuickSort 5719 Press any key to continue . . .
QuickSortX 4625 Press any key to continue . . .

pri NUM_ELEMENTS 20000000

Pust' ot pobyedy k pobyedye vyedyot!

Zgodovina sprememb…

spremenilo: noraguta (6. maj 2004 ob 11:47)

Thomas :: 6. maj 2004, 12:38

No, zverino z dvema (in tremi) X smo dal še razvijat in ravnokar pridno rastet(a).

...

Man muss immer generalisieren - Carl Jacobi

njok :: 6. maj 2004, 12:49

snow, mocna masina ;)

FQS 891
DQS 968
QS 922
QSX 828

OwcA :: 6. maj 2004, 13:06

fastQuickSort 656
doctoredQuickSort 750
QuickSort 797
QuickSortX 625

fastQuickSort 672
doctoredQuickSort 750
QuickSort 797
QuickSortX 641

fastQuickSort 672
doctoredQuickSort 750
QuickSort 797
QuickSortX 640

fastQuickSort 672
doctoredQuickSort 734
QuickSort 797
QuickSortX 640

Otroška radovednost - gonilo napredka.

Thomas :: 6. maj 2004, 15:36

Morm rečt, da sem zadovoljen s tem, da bolj huda (=hitrejša) je mašina, tolk boljš za X (=Critticall) sort(e)!

Zadovoljen sem tudi s tem, da Critticall je (očitno) hujši od vseh silnih human algoritem inventorjev.

:))

p.s.

Jasno, program samo nadaljuje od nekod naprej delo ljudi. But then again - so do humans.

Man muss immer generalisieren - Carl Jacobi

noraguta :: 6. maj 2004, 16:14

v trenutku ko vklopimo optimizacijo v compoilerju ostane fastqs najhitrejši tudi prostor katerega pokriva je neprimerno večji,tako da nevem če je X kaj drugega kot eden od algoritmov pač.

icc mu malo bolje leži ampak vseeno zgubi al pa je poravnan.
bom pa zvecer sprobal še na drugih mašinah.

Pust' ot pobyedy k pobyedye vyedyot!

Zgodovina sprememb…

spremenilo: noraguta (6. maj 2004 ob 16:17)

attackiko :: 6. maj 2004, 16:15

fastQuickSort 2153 Press any key to continue . . .
doctoredQuickSort 2303 Press any key to continue . . .
QuickSort 2203 Press any key to continue . . .
QuickSortX 1983 Press any key to continue . . .

Pr meni vedno tale QSX zmaga. Ni slabo.

Thomas :: 6. maj 2004, 16:28

QSX je prototipek. Dokazovalec koncepta. Vendar ni vreden, da "bi nosil sandale tistemu, ki pride za njim". :))

Brez posebnih težav se da vzgojiti armado sortov, ki so vsak killer v svoji niši. Pa drugih superiornih algoritmov tudi. Full steam ahead!

Man muss immer generalisieren - Carl Jacobi

snow :: 8. maj 2004, 09:28

Tud jaz sem potem probal optimizacijo v compilerju(gcc) pa mal povečal število recordov (25000000):

fastqs : 2531
doc: 2906
qs: 2656
qsx: 2281

Zadevo testiral večkrat.. vedno nekaj podobnega.

Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas :: 8. maj 2004, 09:56

Super, snow!

Sem se poglabljal dalje (=pisaril po forumih ko je Critticall mlel) in zadevo okoli sortov do kraja skapiral.

Same niše so! Za totalno randomizirano dato (na kakršno v stvarnosti redko naletimo) naj bi bil Qsort vseeno najboljši. Za vse druge niše pa Critticall kmalu izumi svojo optimizacijo.

Samo ne! Tudi za totalno randomizirano dato se QS ne splača najbolj. Bolj se splača, da je v "introspekcijskem delu" (kjer sesortajo kratki segmenti) kaj drugega kot QS. Several unique se grozno obnese. Ravno SU, mi je prav žal!

Še bolje se pa obnesejo specializirani za N elementov. Na Critticall strani so pod "sorts on the edge".

Te zevoluiraš kar iz QS in fixiraš število elementov. Kompleks iz teh je najhitrejša možna zadeva.

Man muss immer generalisieren - Carl Jacobi

noraguta :: 8. maj 2004, 11:32

no kaj pa če sprobamo še optimizirane z 25M velikostjo tabele?

cl /Og /G7 /Gs qs.cpp

fastQuickSort 2797 Press any key to continue . . .
doctoredQuickSort 3547 Press any key to continue . . .
QuickSort 3421 Press any key to continue . . .
QuickSortX 3078 Press any key to continue . . .

in

icl -QaxW qs.cpp

fastQuickSort 2485 Press any key to continue . . .
doctoredQuickSort 2984 Press any key to continue . . .
QuickSort 2969 Press any key to continue . . .
QuickSortX 2546 Press any key to continue . . .

Pust' ot pobyedy k pobyedye vyedyot!

jeti51 :: 8. maj 2004, 12:11

fastQuickSort: 1203
doctoredQuickSort: 1266
QuickSort: 1235
QuickSortX: 1078

LP

Thomas :: 8. maj 2004, 15:06

Hvala vsem za dajanje si opravka! Zdej pa ne več, ker tole je že dva dni zadaj. Se pravi čista zgodovina.

Tanov working.cpp in qsort.exe pa dam gor, ko sfiniširam tozadevni članek.

Man muss immer generalisieren - Carl Jacobi

Thomas :: 21. maj 2004, 20:19

Link.

Nimam nič s to objavo. Samo z vsebino.

Man muss immer generalisieren - Carl Jacobi

«« «

12 / 29

»»»

Vredno ogleda ...

	Tema	Sporočila	Ogledi	Zadnje sporočilo
	Tema	Sporočila	Ogledi	Zadnje sporočilo
»	Najhitrejši programski jezik? (strani: 1 2 ) DavidJ Oddelek: Programiranje	75	8054 (5874)	Senitel 29. sep 2005 23:39:07
»	Funkcija z logičnimi operaterji.... (strani: 1 2 ) Boki_ Oddelek: Programiranje	90	5928 (5274)	CaqKa 8. nov 2004 07:48:24
»	Petaflopsu naproti (strani: 1 2 3 ) dr.J Oddelek: Novice / Procesorji	105	9576 (9576)	Marjan 13. jun 2004 19:48:27
»	cene permutacij help please meszaj Oddelek: Programiranje	26	2184 (1791)	Sergio 23. mar 2004 17:54:19
»	kako definirtati prastevilo bombacina Oddelek: Programiranje	14	3907 (3712)	ooux 18. nov 2003 21:11:36

Več podobnih tem

Forum » Znanost in tehnologija » Digitalna evolucija

Digitalna evolucija