» »

It means business

It means business

Vajenc ::

Oprostite moji programski nepismenosti, me pa uporabnost programa vseeno zanima.

Kaj pomeni ta evolucijski sortirnik v praksi? Ali to pomeni le hitrejše defregmantiranje diskov, hitrjše pregledovanje z antivirusniki, hitrejši google ..., ali je to resnično nekaj revolucionarnega kot npr., da bo (kmalu) znal iz SSKJ napisati knjigo?

V obeh primerih je uporabna vrednost, zato čestitke avtorju ;)

Thomas ::

Uporabna vrednost je velika, predvsem za programerje tipa kopernik, s tegale foruma.

Če si jaz prav predstavljam, kaj on sploh počne, ker ga ne poznam drugače kot iz postov tukajle.

Ni pa "evolucijski sortirnik". Gre za sort, ki ga mrcvari Critticall, da bi bil vse bolj prid takim uporabnikom.



> hitrjše pregledovanje z antivirusniki

Mogoče je. Če so optimalno (preko sortiranja) narejeni, potem že.
Man muss immer generalisieren - Carl Jacobi

lymph ::

Kako pa Crittical to razvija, prek pure computinga? :D

Koliko bolje bi pa tole opravil kak superačunalnik?
"Belief is immune to counter example."

Gundolf ::

Ja izgleda dobro, ampak če bi ga hotel direkt primerjat s quicksortom bi moral biti inline. Očitno ti je ratal najti zelo efektivno mešanico med inline sortiranjem in uporabo dodatnega pomnilnika (tko da je hitrejši od merga in qsorta). Tko da definitivno ima prihodnost - če je tista napaka, ki jo je jernejl našel odpravljena.

TESKAn ::

Thomas, si že razmišljal, da bi naredil distributed computing varianto?
Uf! Uf! Je rekel Vinetou in se skril za skalo,
ki jo je prav v ta namen nosil s seboj.

DixieFlatline ::

Ja Criticall, ki bi lahko izkoristil več cpujev bi zmagal! Pa PS3 version :)
The sky above the port was the color of television, tuned to a dead channel.

Thomas ::

> Kako pa Crittical to razvija, prek pure computinga? :D

Skoraj bi lahko tako rekel. Evolucijski algoritem se mu goni do onemoglosti in to je to.

> Koliko bolje bi pa tole opravil kak superačunalnik?

Milijonkrat hitreje bi prišel do istega cilja. Do kakšnega pa v istem času kot je bil porabljen za tole ... pa še ne vemo. IMO do še kar nekaj boljšega.

> če bi ga hotel direkt primerjat s quicksortom bi moral biti inline.

Jah, eno primerjavo že imamo. Koliko bolj rigorozni bi še morali biti, je pa diskutabilna zadeva, ja.

> Tko da definitivno ima prihodnost - če je tista napaka, ki jo je jernejl našel odpravljena.

Tista z 31 oziroma 32 biti ni. Bo pa tudi. In sicer "sistemsko". Bomo preverjanje bitov izkoristili še dodatno.

> Thomas, si že razmišljal, da bi naredil distributed computing varianto?

Sej ene moje stranke to delajo. Čez Božič in Novo leto se je računal en (urniški) problem na 28 računalnikih in bil zadovoljivo rešen.

> Ja Criticall, ki bi lahko izkoristil več cpujev bi zmagal! Pa PS3 version :)

Sej jih lahko. Snow je gonil tisti "mali Gauss v šoli sešteva do 100" na dual coreu hkrati in prišel na obeh do rahlo različne (a pravilne) rešitve. To je bilo na tem forumu.
Man muss immer generalisieren - Carl Jacobi

krneki0001 ::

Thomas, zdej pa iz tega naredi en benchmark za mulce, da bodo lahko testiral, kok imajo hitre računalnike. Recimo da imajo vsi enako datoteko, ki jo morajo s tem algoritmom posortat na njihovi mašini in dobijo rezultat, potem naj pa to primerjajo med seboj.

Domnevam da ta algoritem ob veliki količini podatkov dodobra obremeni sistem.

Thomas ::

Benchmark je gor na Critticall siteu. Lahko ga uporabljajo. Samo bo kmalu drug, to pa tud.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Ok, sem še jaz preveril hitrost, a tokrat malo drugače kot ostali tule.
Tisti testni programček, ki je na tvoji strani Thomas sem pač toliko predelal, da sem dodal za primerjavo navaden std::sort zraven sem pa še štel stvari. Najprej brez štetja operacij sta oba sorta laufala enako dolgo. ~1300ms. To niti ni tako pomembno, ker je malo preveč odvisno od compilerja, optimizacij, računalnika kjer laufa...

Z štetjem je pa tako - štejem vse operacije nad nizom, ki ga urejam in nad notranjimi spremenljivkami algoritma, ki naj bi bile uporabljene za hrambo podatkov (to so meja, temp1, temp2, temp). Za ostale sem sklepal da predstavljajo indexe. Tudi nisem štel operacij ki se dogajajo nad dodatnim bufferjem. Rezultati so pa taki:
asort: 269393343 primerjanj, oz. skupno 393940010 operacij
qsort: 252218716 primerjanj, oz. skupno 371474526 operacij
Glede tega ti artificial sort ne izgleda ravno bolje. Pa še upoštevat je treba vse kar dela nad svojim bufferjem, česar jaz ne štejem. Se pa da iz tega sklepat, da če že naredi nekaj več dela, da ima pa lokalnost podatkov nad katerimi dela toliko boljšo.

Lahko dam tud program pol gor če hočete, standard C++.

Aja, za tisti qsort jaz samo predpostavljam da je qsort. Če se komu da iskat kaj dejansko je, je standardna implementacija za gcc 3.4 na winsih.

Thomas ::

Vse operacije pač niso enakovredne.

Če delata v ekstremu random fajla enako, pri ponavljajočem se ključu sigurno ne. To pa je večina nizov, ki jih sortamo in tam Artificial (že) kraljuje.
Man muss immer generalisieren - Carl Jacobi

WarpedGone ::

Število operacij je merodajno kadar češ ocenit 'splošno' zahtevnost postopka, brez da bi ga dejansko ganjal na neki mašini.
Sploh ker operacija != operacija. Tut dve primerjanji sta lahko različno dragi, če se enkrat primerja večinoma lokalne zadeve, drugič pa večinoma razpršene stvari. Bolj je sumljivo/zanimivo je to, da sta oba skup trajala istih 1300ms. Poskus povečat dataset, podtikat 'psevdoneurejene' podatke etc.

Thomas: če sm te prav razumel, se AS še vedno kuha?
Zbogom in hvala za vse ribe

Gundolf ::

No evo, še za 50M elementov, 100M mi pa računalnik noče več vzet:

asort primerjav 1303694674, skupaj 1921805599
qsort primerjav 1351278390, skupaj 2048684742

Zdej se lahko mal bol počutiš Thomas :) Tam nekje sta.

Pravzaprav je čas tisti, ki ga je najslabše meriti, ker je preveč odvisen od drugih stvari. In če ima algoritem v enem primeru srečo pa dela dokaj lokalno stalno, še ni rečeno, da bo delal tudi v drugem, še sploh pa ko gre za večji dataset. Operacije so pa operacije. Sploh ti več povedo o tem, kako se bo algoritem obnašal, ko ne boš več sortiral navadnih intov. In da ne bo preveč zmede s tistim operacija != operacija. Tule imaš le operacije primerjanj (ki se jih sicer da zreducirat na < in ==) in pa prirejanje (pa kreiranje temp spremenljivk). Torej ko berete 'seštevek vseh operacij', morate vedet kaj to pomeni. Deljenja, množenja, seštevanja pa_ne_vem_še_česa tu notri ni. To so, kot sem rekel, operacije nad datasetom.

Sayer ::

Glede sorta, ki si ga uporabil std:sort - introsort...

malo info:
The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.

Ko sem jaz testiral je bil ASort zmeraj hitrejsi od Introsorta kar ni nezanemarljiv dosezek, cetudi je bila RND funkcija samo tista od Critticall Asort sampla.

Je pa nova verzija algota ASorta vsaj v mojih testih za odtenek pocasnejsa od prvotne, se vedno pa hitrejsa od Introsorta.


LP

Jean-Paul ::

Ne poznam Critticala, zato me zanima, kakšno kriterijsko funkcijo uporablja pri ugotavljanju "kvalitete" določenega algoritma. Je to število "matematičnih" operacij, procesorski čas ali mogoče kaj drugega. Iz Gundolfovega posta bi lahko sklepal, da je to prej procesorski čas kot pa število elementarnih operacij. Si nekako predstavljam, da evolucija najde "optimalen" algoritem v danem okolju (beri platformi). Če bi stvar pognali na drugi platformi (se kdo javi za testiranje na kaki ne-pcjevski arhitekturi?), bi dobili drugačen rezultat. Se motim?

Strinjam se z Gundolfom, da je bolj relevanten podatek kot čas izvajanja seveda število potrebnih operacij. Po drugi strani pa si kar živo predstavljam naslednjo generacijo (evolucijskih) prevajalnikov, ki bodo algoritem prilagodili (adaptacija na okolje?) dani arhitekturi. Seveda bo to možno samo pri odprti kodi ;-)

Je pa res, da je nekaj podobnega že dolgoletna praksa pri optimizaciji numerične knjižnice BLAS (ATLAS), le da tam ne gre za evolucijo ampak za izbiro najhitrejše implementacije iz (končnega) nabora različnih implementacij.

P.S. Bi nekdo (Thomas?) bil mogoče pripravljen razložiti (na grobo), kako poteka proces evolucije na konkretnem primeru sortirnega algoritma.

Gundolf ::

50M elementov, pri čemer so njihove vrednosti random med -10000000 in 10000000 (prej so ble default, med -100000 in 100000):

asort: primerjav 1892133300, skupaj 2977528712 operacij
qsort: primerjav 1525335543, skupaj 2198605558 operacij

Dejansko se fajn pozna koliko se elementi ponavljajo. Zdej se vsak ~2.5x, prej so se pa vsak ~250x. Na qsortu se je to poznal kot dodatnih 15M operacij, na asortu pa kot dodatnih 100M.

Edit: qsort beri kot intro sort :)) Ok, good to know kaj mamo kot default v C++. Sem vedno mislil, da so le vzeli Cjev quicksort in ga generaliziral. Sem pa jaz vzel le zadnjo verzijo Asorta (uno pod 'underconstruction').

P.S. Konc s testi, bom zdej počaku na naslednjo verzijo.

svit ::

Hm... menim da število operacij le ni tako pomembno, ampak le čas. Kaj mi pomaga, če recimo nek program uporabi samo 10 operacij, pa za izvedbo teh porabi več časa, kot pa program ki za enako množico porabi 20 operacij in prej konča. Saj se spomnite na RISC, CISC problem?
Ni ideje

gzibret ::

Hmmm, tele operacije je treba ločit med sabo. Razlika med operacijo (1 AND 1) in (10001010 + 101110101) je neprimerljiva. Gundolf, fajn bi bilo, da bi napisal, kaj si pravzaprav štel. Da ne mešamo jabolk in hrušk. A je to število korakov? Pa če je število korakov, kateri sort opravi manj FLOPS na korak?
Vse je za neki dobr!

jernejl ::

Kadar imamo ponavljajoča števila, je algoritem res dokaj hiter:

(naključna, enakomerno porazdeljena števila med 0 in( 2^16-1), 10mio zapisov):
Optimized Median (Hybrid) QSort Elapsed time = 1000 ms
Artificial Elapsed time = 907 ms
Radix Sort Elapsed time = 500 ms
STD Sort Elapsed time = 1063 ms

Kadar pa stopnja ponavljanja ni tako zelo velika, pa ne:

(naključna, enakomerno porazdeljena števila med 0 in( 2^31-1), 15mio zapisov):
Optimized Median (Hybrid) QSort Elapsed time = 1953 ms
Artificial Elapsed time = 2282 ms
Radix Sort Elapsed time = 859 ms
STD Sort Elapsed time = 2047 ms

Skrbi me tudi to, da bi algoritem imel slabo worst-case časovno zahtevnost / da ni stabilen. Tako da bi kakšni hibridi tukaj lahko imeli prednost.
Poleg tega me je pri hitrem pregledu skozi algoritem zmotila naslednja vrstica:
meja = ( array[j] + array[j+1] + 1 ) / 2;

Zato me bo zelo veselilo, ko bo koda napisana na način, da bo uporabna za splošne tipe.
Mimogrede naj omenim še, da je (v nasprotju s Thomasovimi trditvami) radix sort seveda brez težav uporaben tudi pri urejanju realnih števil. Tudi negativnih. Res pa je, da ga je treba za vsak tip posebej prilagoditi.
Bomo videli, kako splošen bo artificial.

Gundolf ::

gzibret, kaj misliš s tem: "kateri sort opravi manj FLOPS na korak?"
FLOPS na korak?
FLOPS?

Zaenkrat sortiramo integerje, v nobenem od algoritmov ni uporabljen niti en floating point ukaz.

Sej sem napisal katere operacije so upoštevane. Tiste, ki so pomembne, tiste ki delajo na podatkih in le te (torej vse zanke, vse notranjo preračunavanje, ki se ne dotika podatkov, vse initializacije, vse to me ne zanima):
Torej operacije primerjanja. V primeru std::sort-a je to le operator <, ker delamo na intih je to torej primerjava dveh intov. V Thomasovem primeru pravzaprav ne vem katere vse operacije primerjanja uporablja (na podatkih), se mi ni dalo gledat, mislim tudi, da algoritma ni vnaprej omejil glede tega, zato sem za vsak slučaj štel (v obeh primerih) vse možne operacije primerjanja (<, >, ==, !=, <=, >=) in jih obravnaval enako (tudi na strojnem nivoju se obravnavajo več ali manj identično s cmp ukazom)

Prirejanje je pa prirejanje. Še vedno na intih. Na intelu en mov ukaz.

Za Thomasovo kodo sem moral šteti še dodatne operacije (ki jih je sicer bilo dosti manj od ostalih), ker očitno v njegovi kodi nisem znal jasno ločiti podatkov od spremenljivk algoritma. Ne znam tega dobro razložit, ampak recimo takole - trenutno je koda videt, kot da poleg primerjanja dveh elementov in prirejanja elementov dela še neke operacije, ki operirajo mešano - na elementih in na notranjih spremenljivkah algoritma, ki niso nujno istega tipa. Vsekakor delajo nekaj z elementi, zato jih štejem. Ampak, ker so zaenkrat podatki v intih in notranje spremenljivke algoritma v intih mi to pri njihovem ločevanju dela probleme.

Ampak zakaj izbira primerjanj in prirejanj? Ker ti dve operaciji sta edini, ki jih rabiš, da sortiraš niz podatkov arbitrarnega tipa. Vsaj tako jaz razumem Thomasa, da naj bi bil to splošen algoritem. Tudi ne vidim, zakaj naj ne bi bil.

Torej, če bi zdaj hotel namesto intov sortirat double, stringe, you_name_it, se število teh operacij ne bi spremenilo.

Bom dal kodo gor jutr, ker očitno je takole preveč nejasno, samo na žalost je na službeni mašini, ki je pa zdajle ugasnjena.

Gundolf ::

Aha, sej mi je jernejl identificiral vrstico, ki mi dela probleme pri štetju ukazov :) Torej seštevanje dveh elementov iz podatkov, ki jih sortiramo. Tole bo deal-breaker glede splošnosti, če se izkaže za ključni člen. Bo pa seveda algoritem še vedno veselo delal na numeričnih podatkih.

Aja, jaz to vrstico štejem kot tri operacije (kar morda niti ni tako slabo).
[edit: tri operacije, ne dve, kot je bilo prej napisano, sem pozabil assignemnt štet]

Zgodovina sprememb…

  • spremenil: Gundolf ()

TESKAn ::

Hm, IMO je samo operacija primerjanja premalo. Imaš zraven dosti zank, ++ - ov in pri milijonu elementov, skozi katere moreš it, se to kar nabere. Ne rečem, mogoče je enako, ampak če Thomasov AS dela tako, da če nekaj je posortano, se tega ne dotika, QS pa skuša posortirat tudi že OK področja - potem imaš tu lahko kar razliko v ukazih, ki jih porabi en oz. drug algoritem...po moje bi za objektivno primerjavo moral upoštevat vse operacije, ki jih algoritem rabi.
Uf! Uf! Je rekel Vinetou in se skril za skalo,
ki jo je prav v ta namen nosil s seboj.

Gundolf ::

> ampak če Thomasov AS dela tako, da če nekaj je posortano, se tega ne dotika, QS pa skuša posortirat tudi že OK področja - potem imaš tu lahko kar razliko v ukazih
Potem se ti to takisto pozna v operacijah, ki jih štejem; ker če se nek algoritem loti že posortiranega dela, mora primerjat podatke med sabo na tem delu, kar mu seveda nabije število teh operacij.

nevone ::


AS-ArtificialSort 
QS - QuickSort z InsertionSortom

read    - read data from array
write   - write data to array
compare - compare data
režija  - ostalo
------------------------------------------------------------------------------------------------
NumberOfRec = 30.000.000  Data = Rnd(-10000000, 10000000)
AS režija 1425729604 read 1457520705 write 331048566 compare 1124275862 Elapsed time = 14766 ms
QS režija 1236597458 read 1163307478 write 392699278 compare  841307557 Elapsed time = 13937 ms

NumberOfRec = 30.000.000  Data = Rnd(-1000000, 1000000)
AS režija 1126225365 read 1318397267 write 289698392 compare 996161830 Elapsed time = 11875 ms
QS režija 1129982923 read 1138995189 write 355461726 compare 804815548 Elapsed time = 12594 ms
 
NumberOfRec = 30.000.000  Data = Rnd(-100000, 100000)
AS režija  873085958 read 1082705771 write 245138876 compare 806880105 Elapsed time =  9859 ms
QS režija 1062647478 read 1136889289 write 364675890 compare 764056912 Elapsed time = 11500 ms

NumberOfRec = 30.000.000  Data = Rnd(-10000, 10000)
AS režija  697437376 read  866605407 write 199708736 compare 636823126 Elapsed time =  7859 ms
QS režija 1089829551 read 1193201489 write 407584329 compare 773708870 Elapsed time = 10828 ms
-----------------------------------------------------------------------------------------------
NumberOfRec = 10.000.000  Data = Rnd(-10000000, 10000000)
AS režija 456338774  read 456422483  write 107896370 compare 352749508  Elapsed time = 4657 ms
QS režija 403411431  read 368796252  write 126211927 compare 269878448  Elapsed time = 4438 ms

NumberOfRec = 10.000.000  Data = Rnd(-1000000, 1000000)
AS režija 425885693  read 440130660  write  96803342 compare 336866681  Elapsed time = 4265 ms
QS režija 385391118  read 368389086  write 115959022 compare 268894251  Elapsed time = 4125 ms

NumberOfRec = 10.000.000  Data = Rnd(-100000, 100000)
AS režija 295435485  read 361532063  write  81886746 compare 269054474  Elapsed time = 3468 ms
QS režija 335738276  read 349297998  write 109628067 compare 239551295  Elapsed time = 3687 ms

NumberOfRec = 10.000.000  Data = Rnd(-10000, 10000)
AS režija 240164344  read 295350957  write  65730146 compare 219548985  Elapsed time = 2609 ms
QS režija 331276927  read 357870840  write 121238757 compare 232952747  Elapsed time = 3422 ms
-----------------------------------------------------------------------------------------------
NumberOfRec = 1.000.000  Data = Rnd(-1000000, 1000000)
AS režija 40119064   read 38587749   write  9324928  compare 29748757   Elapsed time = 406 ms
QS režija 35427886   read 31128851   write 11085581  compare 22806218   Elapsed time = 359 ms

NumberOfRec = 1.000.000  Data = Rnd(-100000, 100000)
AS režija 37755843   read 37651281   write  8133830  compare 28866677   Elapsed time = 359 ms
QS režija 32871091   read 30442451   write 10136824  compare 21949091   Elapsed time = 344 ms

NumberOfRec = 1.000.000  Data = Rnd(-10000, 10000)
AS režija 24433781   read 29487320   write 6632420   compare 21795754   Elapsed time = 265 ms
QS režija 29150172   read 29704019   write 9343026   compare 20345168   Elapsed time = 297 ms

NumberOfRec = 1.000.000  Data = Rnd(-1000, 1000)
AS režija 19166166   read 23103959   write  4992466  compare 17104124   Elapsed time = 187 ms
QS režija 28600020   read 30459367   write 10512159  compare 19579921   Elapsed time = 265 ms
-----------------------------------------------------------------------------------------------


Edit: ArtificialASort --> ArtificialSort
Edit: IS - Insertion Sort --> QS - QuickSort z InsertionSortom

o+ nevone
Either we will eat the Space or Space will eat us.

Zgodovina sprememb…

  • spremenila: nevone ()

nevone ::

Either we will eat the Space or Space will eat us.

Gundolf ::

Evo, ker sem že obljubil.
#include <cstdio>
#include <cstdlib>
#include <windows.h>
#include <algorithm>


class Int {
	int data;
	static double countCreate;
	static double countAssign;
	static double countConvert;
	static double countCompare;

public:
	inline Int() {++countCreate;}
	inline Int(int d) : data(d) {++countCreate;}
	inline Int(const Int& i) : data(i.data) {++countAssign;}
	inline const Int& operator=(const Int& i) {++countAssign; data = i.data; return *this;}
	inline const Int& operator=(int i) {++countAssign; data = i; return *this;}
	friend inline bool operator== (const Int& i1, const Int& i2) {return (i1.data == i1.data);}
	friend inline bool operator< (const Int& i1, const Int& i2) {++countCompare; return i1.data < i2.data;}
	friend inline bool operator<= (const Int& i1, const Int& i2) {++countCompare; return i1.data <= i2.data;}
	friend inline bool operator!= (const Int& i1, const Int& i2) {return !(i2 == i1);}
	friend inline bool operator> (const Int& i1, const Int& i2) {return (i2 < i1);}
	friend inline bool operator>= (const Int& i1, const Int& i2) {return (i2 <= i1);}
	inline operator int& () {++countConvert; return data;}
	inline operator int () const {++countConvert; return data;}
	
	static void printStats() {
		printf("%10.0f + %10.0f + %10.0f + %10.0f = %10.0f\n", 
			countCreate, countAssign, countConvert, countCompare, 
				countCreate+countAssign+countConvert+countCompare);
	}
	
	static void resetStats() {
		countCreate = 0;
		countAssign = 0;
		countConvert = 0;
		countCompare = 0;
	}
};


double Int::countCreate = 0;
double Int::countAssign = 0;
double Int::countConvert = 0;
double Int::countCompare = 0;


static const int NumberOfRec = 50000000;
static const int buffersize = 2000000;
int* levi;
int* desni;
Int* array;
Int* arrayCpy;


int Rnd(int x1, int x2) {
    int x = x2 - x1 + 1;
    int m = (rand() % x) + x1;    
    int n = (rand() % x) + x1;    
    m = (32000*m + n) % x;
    return m;     
}


// sprememba v definiciji funkcije
void ArtificialSort(Int array[], int nor) { 
	// spremembe v definiciji spremenljivk
    int index = 0; int i = 0; int j = 0; 
    int left = 0; int right = 0; int sinistra = 0; Int meja = 0;
    Int temp1 = 0; Int temp2 = 0; Int temp = 0;
	
	// od tu naprej pa nespremenjena koda
    left = 0; right = nor-1;

    while (left < right){
        if (array[left] > array[right]) {
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        } else {
            break;
        }
        left++; right--;
    }

    index = 0; levi[index] = 0; desni[index] = nor-1;

    i = index;
    while ( index >= i ) {
        left = levi[i]; right = desni[i];
        if ( right-left < 11 ) {
            sinistra = left;
            temp1 = array[right]; temp2 = array[sinistra];
            if ( temp2 > temp1 ) {
                goto labelcritticall3;
            }
            sinistra++;
            labelcritticall15:;
            while ( sinistra < right ) {
                temp2 = array[sinistra];
                if ( temp2 > temp1 ) {
                    array[right] = temp2; array[sinistra] = temp1; 
                    temp1 = temp2;
                }
                sinistra++;
            }
            temp1 = temp2;
            sinistra = left; temp2 = array[sinistra];
            right--;
            if ( temp2 > temp1 ) {
                labelcritticall3:;
                array[right] = temp2; array[sinistra] = temp1;
                temp1 = temp2;
            }
            sinistra++;
            if ( sinistra < right ) {
                temp2 = array[sinistra];
                if ( temp2 > temp1 ) goto labelcritticall3;
                sinistra++;
                goto labelcritticall15;
            }
        } else {
            for ( j = left; j < right; j++ ) {
                if ( array[j] > array[j+1] ) {
                    meja = ( array[j] + array[j+1] + 1 ) / 2;
                    if ( array[ (left + right) / 2 ] > meja ) meja = array[ (left + right) / 2 ];
                    sinistra = left;
                    while ( true ) {
                        while ( array[sinistra] < meja ) sinistra++;
                        while ( array[right] >= meja ) right--;
                        if ( sinistra > right ) break;
                        temp2 = array[right];
                        array[right] = array[sinistra];
                        array[sinistra] = temp2;
                        right--;
                    }
                    temp = desni[i];
                    if ( i > 0 ) desni[i] = right; else { levi[++index] = left; desni[index++] = right;}
                    right++;
                    if ( i != 0 ) {levi[--i] = right; desni[i] = temp; goto labelcritticall5;}
                    levi[index] = right;
                    desni[index] = temp;
                    break;
                }
            }
        }
        i++;
        labelcritticall5:;
    }

}


int main() {
	try {
		array = new Int[NumberOfRec];
		arrayCpy = new Int[NumberOfRec];
		levi = new int[buffersize];
		desni = new int[buffersize];
		
		printf ("\n");
		printf (" ArtificialSort\n");
		printf ("\n");
		printf (" Creating array of random numbers ...\n");
		
		for (int i=0; i<NumberOfRec; i++) {
			array[i] = Rnd(1,10000000)-Rnd(1,10000000);
		}
		
		printf (" copy\n");
		std::copy(array, array+NumberOfRec, arrayCpy);
		
		Int::resetStats();
		printf ("\n Sorting (asort) ...\n");
		int timtim = GetTickCount();
		ArtificialSort(array, NumberOfRec);
		printf ("\n Elapsed time = %d ms\n", (int)GetTickCount()-timtim);
		Int::printStats();
		
		Int::resetStats();
		printf ("\n Sorting (qsort) ...\n");
		timtim = GetTickCount();
		std::sort(arrayCpy, arrayCpy + NumberOfRec);
		printf ("\n Elapsed time = %d ms\n", (int)GetTickCount()-timtim);
		Int::printStats();
		
		delete levi;
		delete desni;
		delete array;
		delete arrayCpy;
		
		return 0;
	} catch(...) {
		printf("oops\n");
	}
}

Pa popravil sem eno napako, ki je prej favorizirala std::sort. En assignment premalo sem štel. Pozna se tako, da recimo moj zadnji test iz skupno 2198605558 operacij za 'qsort' naraste na 2520025348 operacij.

Thomas ::

No, jest verjamem nevone in njenim testom še tabl.

V zelo randomizirani datoteki ima izboljšani qsort en advantage, ki ga bomo uknili do konca tedna ...
Man muss immer generalisieren - Carl Jacobi

gzibret ::

Gundolf - sicer malo offtopic, ampak bom vseeno odgovoril, kaj sem mislil s tistimi flopsi (morda sem se napačno izrazil).

Za vsako operacijo, ki jo narediš, se v ozadju dogajajo neki procesi v računalniku. Sicer nisem podkovan o teh zadevah, ampak operacija
(a < b) zahterva npr. 1 cikel (kakršnikoli pač), (a+1 < b) pa npr. 2 cikla, ker mora procesor prej številki a prišteti 1 in šele nato narediti primerjavo.

No, to sem mislil. Morda res niso FLOPSI, je pa kaj drugega.
Vse je za neki dobr!

Gundolf ::

Sej prav Thomas, da nevone verjameš, drgače bi bil tepen doma :P
Ne, brez heca, en komentar pa le imam. Ta qsort, ki ga je nevone dala za source. Vzame primerjalno funkcijo kot parameter, medtem ko tvoj algoritem uporablja direktno operator manjše. Ko delaš časovno primerjavo to ni ravno primerljivo, ker gre za občutno razliko v hitrosti ene in druge kode.

gzibret, to kar omenjaš ni noben problem. Tvoj prvi primer bi recimo jaz štel kot eno operacijo, drugega pa kot dve. Nevone verjetno še kaj več, ker nekako šteje tudi režijo. Ampak če greš še kaj nižje dol greš lahko praktično kar cikle štet, kar je pa dokaj ekvivalentno temu, da direkt čas pomeriš.

Ampak koliko dela ima nek sortirni algoritem se da enostavno ugotovit tako, da šteješ le operacije nad podatki, ki jih sortiraš. Sej ne da ostalo v realnosti ni pomembno, ampak je stvar implementacije in hardwarea. Moja primerjava je bila zamišljena čist teoretično, koliko mora algoritem premetavat podane podatke, da jih sortira. Ker to je vse kar mora delat. Tako bi jaz primerjal algoritme, ker z merjenjem časa primerjaš le njihove implementacije. Sploh kadar so časi blizu skupaj.

Gundolf ::

Damn, še en bug v moji kodi, tam kjer je operator == mi manjka ++countCompare;

nevone ::

>Ta qsort, ki ga je nevone dala za source. Vzame primerjalno funkcijo kot parameter, medtem ko tvoj algoritem uporablja direktno operator manjše. Ko delaš časovno primerjavo to ni ravno primerljivo, ker gre za občutno razliko v hitrosti ene in druge kode.

To primerjalno funkcijo sem jest za test spremenila v direktno primerjanje z operatorjem manjše. Tako da ta ugovor odpade.

o+ nevone
Either we will eat the Space or Space will eat us.

nevone ::

Takole sem štela operacije:

nekaj ArtificialSort kode:                      operacije
-----------------------------------------------------------------------
      sinistra = left;                          režija++;
      while ( true ) {
          while ( array[sinistra] < meja ) {    read++; compare++;
            sinistra++;                         režija++;
          }
          while ( array[right] >= meja ) {      read++; compare++;
            right--;                            režija++;
          }
          if ( sinistra > right ) break;        režija++;

          temp2 = array[right];                 read++;
          array[right] = array[sinistra];       read++; write++;
          array[sinistra] = temp2;              write++;
          right--;                              režija++;
      }
      temp = desni[i];                          režija++;
      if ( i > 0 ) {                            režija++;
          desni[i] = right;                     režija++;
      } else {
          levi[++index] = left;                 režija+=2;
          desni[index++] = right;               režija+=2;
      }
      right++;                                  režija++;
-----------------------------------------------------------------------


nekaj QuickSort kode:                           operacije
-----------------------------------------------------------------------
      down = first;                             režija++;
      up = last;                                režija++;
      for (;;)
      {
        do
        {
          ++down;                               režija++;
        } while (pivot > This[down]);           read++; compare++;

        do
        {
          --up;                                 režija++;
        } while (This[up] > pivot);             read++; compare++;

        if (up > down)                          režija++;
        {
          int temp;
          temp = This[down];                    read++;
          This[down]= This[up];                 read++; write++;
          This[up] = temp;                      write++;
        }
        else
          break;
      }
    }
    {
      uint32 len1;
      uint32 len2;
      len1 = up - first + 1;                    režija+=3;
      len2 = last - up;                         režija+=2;
      if (len1 >= len2)
      {
        first_stack[stack_pointer] = first;     režija++;
        last_stack[stack_pointer++] = up;       režija+=2;

        first = up + 1;                         režija+=2;
      }
-----------------------------------------------------------------------

o+ nevone
Either we will eat the Space or Space will eat us.

WarpedGone ::

Pri telem ocenjevanju zahtevnosti s štetjem posameznih primerjanj in prirejanj fejst pretiravate. Včasih se je namesto 2 * 6 splačalo rečt 2 + 2 + 2 + 2 + 2 + 2. Zdej to ni več nujno bolje.

Ali en pohaca 2000 milijonov al 2010 milijonov primerjanj je irrelevantno. Relevantno je koliko je vse skup trajalo, ker tut vsa primerjanja med sabo niso ekvivalentna - cache, paralelnost kode, težko predvidljivo brenchanje etc - bistveno preveč parametrov vpliva na hitrost izvajanja kode, da bi se splačalo gledat EN PARAMETER -> skupno število enostavnih operacij. Ocena zahtevnosti je relevantna šele ko hočeš videt kako čas narašča s povečevanjem dataseta.

Dejte raj energijo porabt za ročno analizo algoritma in recimo poskušat prehitet Crittical s kako dobro idejo. Al pa pogruntat kaj so njegove močne in šibke točke - kje se najbol splača ga še peglat.
Zbogom in hvala za vse ribe

Thomas ::

You talk my language here, Warped.

Critticall ima en takle interni ukaz:

$penarr a[]=20

Pomeni, če se bo algoritem ukvarjal z nizom a[], ga kaznuj z 20.

Ali pa tale:

$rescom goto while if

NE SME biti gotowhile in if stavka.

Tako lahko zevoluiraš po svojih potrebah in željah.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Čisto nič drugega nas ne briga, kot realna hitrost algoritma - ponavadi.
Je recimo možno domnevati, da QuickSort največ porabi za pisanje v array in zato to penaliziramo extra. Evolucija bo tekla in favorizirala tiste, ki se array operacijam (ki jih lahko navedemo tudi vsako posebej z različno utežjo!) - izogibajo.

Byproduct je, da je rezultat verjetno zelo hiter. Quick je, ki ga ni čisto lahko spoznati.
Man muss immer generalisieren - Carl Jacobi

jernejl ::

nekaj ArtificialSort kode:

nekaj QuickSort kode:

Upam, da k temu priložen del "kode" ni dejanska koda, s katero je bilo primerjano število operacij.

Ali en pohaca 2000 milijonov al 2010 milijonov primerjanj je irrelevantno. Relevantno je koliko je vse skup trajalo, ker tut vsa primerjanja med sabo niso ekvivalentna - cache, paralelnost kode, težko predvidljivo brenchanje etc - bistveno preveč parametrov vpliva na hitrost izvajanja kode, da bi se splačalo gledat EN PARAMETER -> skupno število enostavnih operacij. Ocena zahtevnosti je relevantna šele ko hočeš videt kako čas narašča s povečevanjem dataseta.

Tudi na čas izvajanja vpliva veliko preveč parametrov, da bi lahko iz tega sklepali na hitrost algoritma.
Med drugim je že bilo poudarjeno, da se lahko izmerjeni časi bistveno razlikujejo na različnih arhitekturah, in pri različnih strojnih konfiguracijah in konfiguracijah sistemske prog. opreme.
Z izmerjenimi časi lahko le merimo čas izvajanja IMPLEMENTACIJE algoritma na določeni arhitekturi in strojni konfiguraciji ter konfiguraciji sistemske prog. opreme, pa še to le za nek točno določen testni primer.

Tako merjenje časa izvajanja kot štetje operacij (visokega prog. jezika?) ima svoje pomanjkljivosti.

Čisto nič drugega nas ne briga, kot realna hitrost algoritma - ponavadi.

Končnega uporabnika res briga trajanje urejanja (če odmislimo prostorsko zahtevnost). Vendar, kadar testiraš algoritem na neki strojni opremi s 1000 testnimi primeri, iz tega ne moreš določiti, kako hitro se bo zadeva izvajala nekje drugje in na drugačnih podatkih.

Thomas ::

> Tako merjenje časa izvajanja kot štetje operacij (visokega prog. jezika?) ima svoje pomanjkljivosti.

Torej se meriti ne da? :\
Man muss immer generalisieren - Carl Jacobi

jernejl ::

Torej se meriti ne da?

Kaj točno bi želel meriti, ter kaj te je napeljalo do sklepa, da se tega meriti ne da?

Zgodovina sprememb…

  • spremenil: jernejl ()

Thomas ::

Mene zanima samo to, kako hitro se v praksi izvede nek algoritem.

Kako bi se izvedel, če bi imeli neko XY arhitekturo, ki je nimamo, lahko bi jo pa če ... me bistveno manj zanima.
Man muss immer generalisieren - Carl Jacobi

nevone ::

>Tako merjenje časa izvajanja kot štetje operacij (visokega prog. jezika?) ima svoje pomanjkljivosti.

Primerjava po številu operacij pač da nek vpogled v program. Več je teh primerjav narejenih, boljše si lahko predstavljaš, kaj algoritem v posameznih situacijah lahko pomeni.

Če ima neka meritev pomankljivosti, jih pač nekoliko vzameš v račun pri končni oceni, ampak, da bi pa zaradi pomanjkljivosti ne delali raznih testnih primerjav je pa še večja pomanjkljivost.

Kogar stvar resno zanima, bo že sam izluščil katera primerjava mu najbolj ustreza. Če pa iščemo neko univerzalno primerljivost, potem se stvar zelo zamegli.

Tako da, primerjava po kakršnemkoli parametru je dobrodošla, pa četudi je pomanjkljiva.

o+ nevone
Either we will eat the Space or Space will eat us.

gzibret ::

> Dejte raj energijo porabt za ročno analizo algoritma in recimo poskušat prehitet Crittical s kako dobro idejo. Al pa pogruntat kaj so njegove močne in šibke....

Se tudi jaz popolnoma strinjam s to mislijo. Čeprav zgoraj povedano prepuščam drugim, ker sam nimam dovolj znanja. Na žalost..... (turbo pascal rules :D ).
Vse je za neki dobr!

Fizikalko ::

Ufff! Šele zdajle opazil in prebral.... Vsekakor čestitke, Thomas! Res hudo.

gumby ::

glede analize:
bi blo mozno locit med navadnimi in "hitrimi" read/write/compare operacijami, glede na cache in ostale zmoznosti strojne opreme?
ter seveda evolvirat algoritem v tej smeri...
my brain hurts

WarpedGone ::

Delit opreacije na hitre in počasne je pregrobo da bi se splačalo ali bilo uporabno. Ali greš štet urine cikle posameznega sortiranja al pa sploh pozabiš na 'operacije' in se spraviš gledat odvisnost trajanja sortiranja od števila in 'kvalitete' elementov. Kjer trajanje meriš z abstraktnimi enotami ala 1 pomeni sortiranje 10 elementov.
Zbogom in hvala za vse ribe

jernejl ::

Mene zanima samo to, kako hitro se v praksi izvede nek algoritem. Kako bi se izvedel, če bi imeli neko XY arhitekturo, ki je nimamo, lahko bi jo pa če ... me bistveno manj zanima.

V redu, pa bodimo praktični. Že sodobni Intelovi in AMDjevi procesorji se razlikujejo, razlike se denimo pojavljajo pri ukazih množenja in deljenja (MUL, DIV), seveda tudi drugje. Prav tako na merjene čase izvajanja vpliva prevajalnik, ter seveda operacijski sistem. Poleg vsega seveda tudi ostala strojna oprema (predpomnilnik, količina glavnega pomnilnika, hitrosti vodil, v določenih primerih hitrosti trdega diska itd).
To so samo nekateri faktorji, ki vplivajo na izmerjene čase, četudi opustimo vse ostale neobstoječe in obstoječe arhitekture (namenski mikrokrmilniki, mobilne naprave, strežniki; DSPji, PIC, AVR, PowerPC, SPARC...).
Ne trdim, da se ne da meriti, vendar se je treba zavedati določenih pomanjkljivosti takšnih meritev (v nasprotnem si tudi sam ne bi vzel svojih 5 minut časa za meritve).
Rezultatov zaradi tega ne gre kar tako posploševati. To poudarjam zaradi tega, ker se nekateri postavljajo na eno stran (meriti čas ali pa meriti število ukazov, urinih ciklov) - čeprav pavšalno ni mogoče kar tako trditi, katera metoda je "boljša".

Je recimo možno domnevati, da QuickSort največ porabi za pisanje v array in zato to penaliziramo extra.

Če odmislimo nekaj napak v objavljeni kodi nevone (ki bi morda lahko bistveno spremenile številke), je število pisanj nekajkrat manjše kot število branj, kar je sicer logično. Ali je pisanje časovno nekajkrat počasnejše od branja, si ne bi upal trditi. Na nivoju strojnih ukazov prav gotovo ne, razlika bi lahko nastala le pri predpomnilniku in strategiji write-through ali write-back.
Zaradi tega me zanima, na podlagi česa domnevaš, da QuickSort največ porabi za pisanje?

Tako da, primerjava po kakršnemkoli parametru je dobrodošla, pa četudi je pomanjkljiva.

V splošnem se z nevone strinjam, pri tem stavku pa bi vseeno opozoril na previdnost. V redu je, če se pomanjkljivosti zavedamo in rezultate pravilno ovrednotimo, saj v nasprotnem je lahko taka primerjava tudi zavajajoča.

bi blo mozno locit med navadnimi in "hitrimi" read/write/compare operacijami, glede na cache in ostale zmoznosti strojne opreme?

Algoritmi upravljanja s predpomnilnikom so implementirani na strojnem nivoju in do tega programer nima dostopa. Ali so operacije "hitre" ali ne, lahko le predvidevamo. Večjo imamo lokalnost obdelave, večja je verjetnost, da bodo podatki shranjeni v predpomnilniku. Algoritmi, ki delajo nad velikimi množicami podatkov, favorizirajo ravno to; zelo je pomembno, da imamo čimmanj I/O posegov na trdi disk in da je čimveč podatkov na voljo v pomnilniku ali predpomnilniku ali v registrih.

gumby ::

lahk gres tud cikle stet, ampak nisem ravno to mislil...
ciljam na razlike med _isto_ operacijo, ter evolviranje algoritma v tej smeri
my brain hurts

Thomas ::

> bi blo mozno locit med navadnimi in "hitrimi" read/write/compare operacijami, glede na cache in ostale zmoznosti strojne opreme?

Vsaka operacija ima v Critticallu neko default težo. Vendar jih lahko obtežiš tudi čisto drugače.



$WEIGHTS COMMANDS=2 ... (weights)

Penalizes any use of any command with 2 standard points.
COMMANDS=0 LINES=1 would result with the SHORTEST program possible. It is useful, when you want to see, what some long program is doing.

$WEIGHTS INC_DEC=999
Nearly prevents i--;c++; ... kind of lines

The default weights points are those:

LINES = 0

COMMANDS
VAL_TO_VAR = 1
VAR_TO_VAR = 1
INC_DEC = 1
VAR_TO_ARRAY = 70
ARRAY_TO_VAR = 10
WHILE = 2
BREAK = 1
IF = 2
GOTO = 2
OPERATION
OPERATION_+ = 1
OPERATION_- = 1
OPERATION_* = 1
OPERATION_/ = 1
OPERATION_% = 10
OPERATION_& = 1
OPERATION_| = 1
OPERATION_^ = 1
OPERATION_<< = 2
OPERATION_>> = 2
VAL_OPERATION
VAL_OPERATION_+ = 1
VAL_OPERATION_- = 1
VAL_OPERATION_* = 1
VAL_OPERATION_/ = 1
VAL_OPERATION_% = 10
VAL_OPERATION_& = 1
VAL_OPERATION_| = 1
VAL_OPERATION_^ = 1
VAL_OPERATION_<< = 2
VAL_OPERATION_>> = 2
FUNCTION
FUNCTION_SQRT = 90
FUNCTION_LOG = 130
FUNCTION_EXP = 700
FUNCTION_ABS = 7
FUNCTION_! = 2
FUNCTION_- = 1


See also: $PENVAL, $PENARR

Man muss immer generalisieren - Carl Jacobi

nevone ::

>Če odmislimo nekaj napak v objavljeni kodi nevone (ki bi morda lahko bistveno spremenile številke),

Če že omenjaš napake v moji kodi, bi bilo lepo/fer če bi povedal, kaj so te napake. Takole opozoriti na napako in ne povedati kje je, je zelo zavajajoče. In če sem prav razumela tvoje prispevke ti gre zelo za to da ne bi zavajali.

Če je v moji kodi napaka, ali pomankljivost, sem pripravljena kodo tudi spremeniti in jo pogledati in preizkusiti še iz kakšnega drugega aspekta. Meni ne gre za zavajanje. Ker koda ArtificialSorta je objavljena. Vsak se lahko sam prepriča, kako in kaj deluje. Tukaj pa pač delamo neke preseke, ki so prav tako lahko informativni.

Samo nekaj me bega pri vsej stvari. Če bi se ArtificialSort vedno in povsod v tvojih testih izkazal za slabšega, ali bi se tudi toliko sekiral glede objektivnosti testov?

Pa da ne bo pomote. Tudi tvoji testi v tej temi so pripomogli k še boljši kodi ArtificialSorta. Tako da, show must go on!

o+ nevone
Either we will eat the Space or Space will eat us.

jernejl ::

Sem menil, da je dokaj vidno in samoumevno. Pa bom skušal na hitro pojasniti (dodal sem komentarje, upam, da sem v grobem zajel bistvene stvari).
Tiste besede o pomanjkljivosti pa so bile povedane na splošno in niso bile namenjene tvojim testom. Pomanjkljivosti namreč veljajo za vse (tudi za moje opravljene meritve, ki niso nič boljše od ostalih in so daleč od popolnih meritev).


nekaj ArtificialSort kode:                      operacije
 -----------------------------------------------------------------------
       sinistra = left;                          režija++;
       while ( true ) {
           while ( array[sinistra] < meja ) {    read++; compare++;
             sinistra++;                         režija++;
           }
           while ( array[right] >= meja ) {      read++; compare++;
             right--;                            režija++;
           }
           if ( sinistra > right ) break;        režija++; //režija++ PRED if, saj se primerjava izvede v vsakem primeru (brezpogojno)
 
           temp2 = array[right];                 read++;
           array[right] = array[sinistra];       read++; write++;
           array[sinistra] = temp2;              write++;
           right--;                              režija++;
       }
       temp = desni[i];                          režija++;
       if ( i > 0 ) {                            režija++; //režija++ PRED if
           desni[i] = right;                     režija++;
       } else {
           levi[++index] = left;                 režija+=2;
           desni[index++] = right;               režija+=2;
       }
       right++;                                  režija++;
 -----------------------------------------------------------------------
 
 
 nekaj QuickSort kode:                           operacije
 -----------------------------------------------------------------------
       down = first;                             režija++;
       up = last;                                režija++;
       for (;;)
       {
         do
         {
           ++down;                               režija++;
         } while (pivot > This[down]);           read++; compare++; //read++ in compare++ morata biti znotraj zanke!
 
         do
         {
           --up;                                 režija++;
         } while (This[up] > pivot);             read++; compare++; //read++ in compare++ morata biti znotraj zanke!
 
         if (up > down)                          režija++; //režija++ mora biti pred stavkom if ! (tako kakor je zdaj, je naslednji blok brezpogojen)
         {
           int temp;
           temp = This[down];                    read++;
           This[down]= This[up];                 read++; write++;
           This[up] = temp;                      write++;
         }
         else
           break;
       }
     }
     {
       uint32 len1;
       uint32 len2;
       len1 = up - first + 1;                    režija+=3;
       len2 = last - up;                         režija+=2;
       if (len1 >= len2) //ali je šteta primerjava ?
       {
         first_stack[stack_pointer] = first;     režija++;
         last_stack[stack_pointer++] = up;       režija+=2;
 
         first = up + 1;                         režija+=2;
       }
 -----------------------------------------------------------------------


Edit: Uredil izpis programskega koda.

Zgodovina sprememb…

  • spremenil: jernejl ()

jernejl ::

Thomas, ne vem, ali so objavljene vrednosti spremenljivk le privzete vrednosti ali so uporabljene tudi v tem primeru.
Naj opozorim, da se deljenje izvaja kar nekajkrat počasneje od ostalih operacij (+,-,*), zato bi bilo smiselno ga bolj kaznovati od ostalih treh operacij. (velja za Intel in AMD). Sicer je res, da v samem algoritmu operacij deljenja ni veliko.

Še vedno pa me zanima, kako nameravate rešiti naslednji problem:
meja = ( array[j] + array[j+1] + 1 ) / 2;

(ni namreč samoumevno, da bi tip, ki ga urejamo, moral imeti definirane operacije za seštevanje z istim tipom, prištevanje integer vrednosti ter deljenje)


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Quick sort

Oddelek: Programiranje
102368 (1116) drola
»

Digitalna evolucija (strani: 1 2 3 426 27 28 29 )

Oddelek: Znanost in tehnologija
141673437 (23606) pietro
»

dos C urejanje po velikosti

Oddelek: Programiranje
81121 (952) klemen22
»

[Turbo Pascal] Pomoč...

Oddelek: Programiranje
131387 (1289) Grey
»

sortirni algoritem v Cju

Oddelek: Programiranje
61357 (1209) GaPe

Več podobnih tem