» »

It means business

It means business

Thomas ::

> Še vedno pa me zanima, kako nameravate rešiti naslednji problem:

To je tako lahko, da se mi ni zdelo vredno odgovarjat.

A je tako težko določiti vmesni string po abecedi? In dodati toliko znakov ASCII 0 na konec, kolikor je dolg prvi ali drugi string?
Man muss immer generalisieren - Carl Jacobi

nevone ::

>Sem menil, da je dokaj vidno in samoumevno.

Aja, vidim kje je nastal problem. :) Torej izsek kode, koda ki sem jo dala ni koda s katero sem dejansko delala test.
Tisti izseki imajo samo vsako linijo opremljeno s tem, kaj prispevajo k posameznim operacijam.

Takole bi morala napisati, da ne bi bilo dvoumno, ali pa vsaj dati desni del v komentar.


Nekaj kode:                     Koliko prispeva posamezna vrstica
-----------------------------------------------------------------
{
  ++down;                       // režija = 1
} while (pivot > This[down]);   // read = 1, compare = 1
                                                   
do
{
  --up;                         // režija = 1
} while (This[up] > pivot);     // read = 1, compare = 1

if (up > down)                  // režija = 1

{
  int temp;
  temp = This[down];            // read = 1
  This[down]= This[up];         // read = 1, write = 1
  This[up] = temp;              // write = 1
}


Sicer pa hvala. Lahko bi si tudi kdo drug to narobe razlagal.

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

jernejl ::

nevone, hvala za razlago, zdaj je veliko bolj jasno.

Thomas:
Zanima me za splošni tip (reciva mu T), ne za string.
Saj bomo na koncu dobili verzijo napravljeno s predlogami (templates), mar ne?

Algoritmi za urejanje, ki temeljijo na primerjavah (in so zato omejeni na sp. mejo primerjav O(n log n)), potrebujejo poleg samih elementov le operacijo za primerjavo dveh elementov (navadno operator<).
Ostali algoritmi niso splošni, ampak se prilagajajo vsakemu (znanemu) tipu posebej ter tudi niso omejeni z O(n log n) - primer je radix sort.

nevone ::

Mau smo peglal. :)

AS-ArtificialSort z InsertionSortom 
  (sprememba od prejšnje verzije NI samo vključitev Insertiona)
  
QS-QuickSort z InsertionSortom

---------------------------------------------------------------------------------------------------
NumberOfRec = 30.000.000         NumberOfRec = 10.000.000         NumberOfRec = 1.000.000
---------------------------------------------------------------------------------------------------
Data = Rnd(-10000000, 10000000)  Data = Rnd(-10000000, 10000000)  Data = Rnd(-10000000, 10000000) 
AS Elapsed time = 12437 ms       AS Elapsed time = 3968 ms        AS Elapsed time = 343 ms        
QS Elapsed time = 12781 ms       QS Elapsed time = 4046 ms        QS Elapsed time = 359 ms        
                                                                                                  
Data = Rnd(-1000000, 1000000)    Data = Rnd(-1000000, 1000000)    Data = Rnd(-1000000, 1000000)   
AS Elapsed time = 10500 ms       AS Elapsed time = 3563 ms        AS Elapsed time = 344 ms        
QS Elapsed time = 11828 ms       QS Elapsed time = 3891 ms        QS Elapsed time = 360 ms        
                                                                                                  
Data = Rnd(-100000, 100000)      Data = Rnd(-100000, 100000)      Data = Rnd(-100000, 100000)     
AS Elapsed time =  8562 ms       AS Elapsed time = 2859 ms        AS Elapsed time = 313 ms        
QS Elapsed time = 10812 ms       QS Elapsed time = 3484 ms        QS Elapsed time = 343 ms        
                                                                                                  
Data = Rnd(-10000, 10000)        Data = Rnd(-10000, 10000)        Data = Rnd(-10000, 10000)       
AS Elapsed time =  6875 ms       AS Elapsed time = 2313 ms        AS Elapsed time = 219 ms        
QS Elapsed time = 10078 ms       QS Elapsed time = 3188 ms        QS Elapsed time = 282 ms        
                                                                                                  
Data = Rnd(-100, 100)            Data = Rnd(-100, 100)            Data = Rnd(-100, 100)           
AS Elapsed time =  3703 ms       AS Elapsed time = 1234 ms        AS Elapsed time = 125 ms        
QS Elapsed time =  8407 ms       QS Elapsed time = 2656 ms        QS Elapsed time = 234 ms        
                                                                                                  
Data = Rnd(-10, 10)              Data = Rnd(-10, 10)              Data = Rnd(-10, 10)             
AS Elapsed time =  2094 ms       AS Elapsed time =  703 ms        AS Elapsed time =  78 ms        
QS Elapsed time =  7640 ms       QS Elapsed time = 2453 ms        QS Elapsed time = 203 ms        
---------------------------------------------------------------------------------------------------
Either we will eat the Space or Space will eat us.

Thomas ::

Link.

Nova verzija je gor. Dodan je insertion sort za majhne segmente, prav tako kot pri Quicku. Koda je popravljena tudi v osrednjem delu, kjer še nekoliko bolj spominja na Quick. Prednost pred njim pa je zdaj večja kot prej, poglejte si nevonine teste zgoraj in naredite svoje, če hočete.

Ni pa še to zadnja beseda, seveda.
Man muss immer generalisieren - Carl Jacobi

nicnevem ::

Zadnje meritve, ki jih je dala nevone zgledajo... skoraj to good to be true. Preden sem opazil tale ASort sem mislil, da so s QSortom+kak hack rekli zadnjo besedo na področju splošnih sortov in se tako s tem ni več vredno ukvarjati. Zato sem še toliko bolj impresioniran. Čestitam, obema. :)

P.s. Thomas, bi bilo mogoče s Critticallom razviti dobrega (optimalnega?) igralca kake igre..recimo štiri v vrsto, morda šaha? Vprašam, ker bi mi morda prišlo prav pri kaki seminarski.
overcomingbias.com -- transhumanizem.org -- singinst.org

Gundolf ::

Nevonine meritve so res too good to be true.

Moje so take:
size = 1000000, rnd. param = 10, avg element freq. = 52631.578947
asort time = 47, qsort time = 47

size = 1000000, rnd. param = 1000, avg element freq. = 501.002004
asort time = 110, qsort time = 94

size = 1000000, rnd. param = 100000, avg element freq. = 5.548651
asort time = 172, qsort time = 141

size = 1000000, rnd. param = 10000000, avg element freq. = 1.040284
asort time = 188, qsort time = 156

size = 10000000, rnd. param = 10, avg element freq. = 526315.789474
asort time = 438, qsort time = 515

size = 10000000, rnd. param = 1000, avg element freq. = 5002.501251
asort time = 1109, qsort time = 969

size = 10000000, rnd. param = 100000, avg element freq. = 50.501735
asort time = 1766, qsort time = 1406

size = 10000000, rnd. param = 10000000, avg element freq. = 1.424190
asort time = 2344, qsort time = 1859

size = 50000000, rnd. param = 10, avg element freq. = 2631578.947368
asort time = 7438, qsort time = 6312

size = 50000000, rnd. param = 1000, avg element freq. = 25012.506253
asort time = 5797, qsort time = 5109

size = 50000000, rnd. param = 100000, avg element freq. = 250.440776
asort time = 8938, qsort time = 7625

size = 50000000, rnd. param = 10000000, avg element freq. = 3.324985
asort time = 12719, qsort time = 9875

Seveda sem jaz sam spisal qsort, ga ročno zoptimiziral in ga malenkost spremenil, tako da se 'lepše' obnaša na zaporedjih kjer se dosti elementov ponavlja. Če dobro pogledate boste opazili en test, kjer je qsort dejansko počasnejši. No, sem vse samo enkrat pognal, tako da morda so winsi kaj tarnali ravno ob tistem testu ;)

Bom dal kodo - jutri.

nevone ::

Se že veselim kode. Bo vsekakor zanimivo videti, kako si optimiziral Quick sort.
Either we will eat the Space or Space will eat us.

nevone ::

>Nevonine meritve so res too good to be true.

Moje meritve so narejene na dveh, v tej temi objavljenih kodah sortov in jih lahko vsak ponovi. Dopuščam možnost, da tisti Quick sort ni optimalno zakodiran, ampak, da bi pa bile zaradi neoptimalne kode takšne razlike pri manj različnih elementih, pa tudi ne verjamem.

Res me zanima, kakšna je ta tvoja optimizacija!

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

Gundolf ::

To, če sem ga zoptimiziral ne vem, ker kakšnih hudih testov nisem delal. Niti ne morem trdit da totalno ne crkne (v hitrosti), če mu podvališ pravilno sortiran, narobe sortiran, itd niz. Navsezadnje je še vedno quicksort s svojo worst case kvadratno kompleksnostjo. Je pa absolutno optimiziran za sortirat enake elemente.

Thomas ::

Hehe ...

Ne vem, zakaj nisi "svojega qsorta" primerjal še z običajnim QuickSOrtom. Tega presežeš še bolj, kot našega Artificiala? Magnificient!

Yeah, right. S kodo na plano, da vidimo, kaj maš za pokazat! ;)
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Seveda je hitrejši od quicksorta s katerim sem štartal (ne, nisem iz glave delal). Če je pa hitrejši od "quicksorta" je pa neumno vprašanje. To je še vedno "quicksort". Samo izbira pivota je malo drugačna (pride v poštev kadar je veliko enakih elementov) in pa lazy swap je uporabljen (to ime sem si glihkar zmislu). Je pa hitrejši na podanih primerih od gccjevega std::sorta, ki me je kar precej razočaral.

Zdej pa lahko to kodo daš kot seed criticallu pa da vidmo kaj bo pogruntu. Ker vem da ni optimalna. Vsaj na enem mestu že točno vem kaj bi se dalo izboljšat. Tudi nima dodanih specializacij za posebne primere. Ampak, ker je že v sedanji obliki hitrejši od asorta se mi za zdaj s tem ne da ukvarjat. Ti pustim Thomas, da se najprej ti in criticall izkažeta.

template <typename T>
void quicksort(T* a, T* b) { 
	T* stack[64*2];
	int stackPos = 0;
	T pivot; 
	
	for (;;) {
		T* b1 = b-1;
		if (a < b1) {
			if (*a < *b1) {
				pivot = *a;
			} else {
				if (*b1 < *a) {
					pivot = *b1;
					*b1 = *a;
				} else {
					T* olda = a;
					for (++a; a < b1; ++a) {
						if (*b1 < *a) {
							pivot = *b1;
							*b1 = *a;
							*a = pivot;
							a = olda;
							break;
						} else if (*a < *b1) {
							pivot = *a;
							*a = *olda;
							*olda = pivot;
							a = olda;
							break;
						}
					}
				}
			}
			
			if (a < b1) {
				T* empty = a;
				for (T *aa = a, *bb = b1;;) {
					for (++aa; !(pivot < *aa) && (aa <= bb); ++aa);
					for (--bb; (pivot < *bb) && (aa <= bb); --bb);
					
					if (aa < bb) {
						*empty = *bb;
						*bb = *aa;
						empty = aa;
					} else {
						*empty = *bb;
						*bb = pivot;
						
						if (bb - a > b - bb) {
							stack[stackPos] = a;
							stack[stackPos+1] = bb;
							a = bb+1;
						} else {
							stack[stackPos] = bb+1;
							stack[stackPos+1] = b;
							b = bb;
						}
						stackPos += 2;
						break;
					}
				}
				continue;
			}
		}
		if (stackPos > 0) {
			b = stack[--stackPos];
			a = stack[--stackPos];
		} else break;
	};
}


Za tiste ki ste tule bolj C kot C++ usmerjeni - klice se ga tko: quicksort(data, data+st_elementov); kjer je data tabela, ki vsebuje točno st_elementov elementov. Torej pointer na prvi element v tabeli in pointer na prvi element, ki ni več del tabele.

Zgodovina sprememb…

  • spremenilo: gzibret ()

Gundolf ::

Aja Sergio sori, spet bo problem z Javo - sicer ni goto stavkov so pa sami pointerji. Čeprav to bi se še dal pomatrat verjetno.

Thomas ::

Uvedba pointerjev v QSort... beh.

A češ da damo pinterje še v ArtificialSort?

A gremo še v assembler?

To je out.
Man muss immer generalisieren - Carl Jacobi

nevone ::

Pri meni test pokaže takole:

size = 10000000, rnd. param = -1000,1000
ArtificialSort: 2047 ms GundolfQS: 2344 ms

Eden ga nekje biksa.

Pospešitev glede na QuickSort pa gre verjetno pripisati uporabi kazalcev.

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

Thomas ::

> Pospešitev glede na QuickSort pa gre verjetno pripisati uporabi kazalcev.

Iu beča! :D
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Vidva sta smešna s temi kazalci. Pospešitev je nikakva v primerjavi z uporabo tabele in offseta. Seveda lahko sama preizkusita... Razlika je tudi v številu primerjanj in assignmentov.

Naredi malo več testov nevone, pa da vidimo, kako je pri tebi res s hitrostjo. In ne pozabi vključiti optimizacij v compilerju. Jaz sem zdajle recimo probal še z izklopljenimi in dobil na istem primeru tole:

size = 10000000, rnd. param = 1000, avg element freq. = 5002.501251
asort time = 1703, qsort time = 1890, gcc 3.4 std::sort = 4485

std::sort je itak pričakovano najbolj nastradal zaradi neuporabe optimizacij. qsort pa malo bolj od asorta. In asort je btw tisti, ki je najbolj podoben assemblerju. Goto stavki in to. Aja, jaz imam Athlona 64 3200+, za katerega ne morem reči da je nevemkakšno čudo tehnike, pa mi sorti laufajo 2x hitreje kot tebi. Kaj pa imaš zaeno mašino?

Thomas ::

Irelevantno je vse kar govoriš. Verzija programa s pointerji je neprimerljiva s programom brez pointerjev.

Hecen si Gundolf.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Thomas> Mene zanima samo to, kako hitro se v praksi izvede nek algoritem.
Thomas malo kasneje> Verzija programa s pointerji je neprimerljiva s programom brez pointerjev.
Nič več te ne zanima hitrost? Zakaj potem criticalla ne naučiš, da ti s pointerji dela, če so tako zelo hitrejši? Oz. zakaj ne prevedeš criticallovega programa tako da bo uporabil pointerje pa bo nascal moj predelan qsort?

Thomas ::

Ajd, Gundolf, mešaš meglo, kot je v tvoji navadi.

Jasno, da mene zanima samo to, kako se izvede nek ALGORITEM, ne implementacija s kazalci (MMX assemblerjem itd).

Pač primerljiva koda, ker zanima nas A L G O R I T E M.

Ko algoritem enkrat imamo, se pa lahko izživljamo z raznimi programerskimi prijemi, kot so kazalci, MMX ipd.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Ti mal mešaš med kazalci in neko low level kodo. Ko bom uvedu MMX v kodo in jo začel optimizirat za delovanje na enem podatkovnem tipu (kot je btw tvoja) se pa lahko pritožuješ. Al uporabljaš kazalce al pa index v tabelo je čist isto. No ni 100% enako v 100% primerov, oboje ima rahle prednosti in slabosti. Ampak razlike v hitrosti delovanja ti v sort algoritmu ne boš našel. Če bi pa bila, bi moral biti pa že std::sort toliko hitrejši, ker - lej ga zlodja - implementiran je s kazalci. Rekel bi celo, da ima tabela + offset tu morda rahlo prednost, ker moderen hardware zna v enem ukazu naredit dereferencirat in dodat offset. Medtem ko implementacija s kazalci je bolj splošna. Jaz samo malo popravim definicijo funkcije pa bo koda delala na tabelah, na std::vector, std::list, na vseh možnih zbirkah podatkov ki implementirajo iteratorje.

Gundolf ::

Samo za Thomasa in vse ki mislite kolk uber hitrejši so pointerji od tabele, še malo mešanja megle iz moje strani (moj modificiran qsort tokrat brez pointerjev v kodi ;)):
template <typename T>
void quicksort(T data[], int size) { 
	int stack[32*2];
	int stackPos = 0;
	T pivot; 
	int a = 0;
	
	for (;;) {
		int b1 = size-1;
		if (a < b1) {
			if (data[a] < data[b1]) {
				pivot = data[a];
			} else {
				if (data[b1] < data[a]) {
					pivot = data[b1];
					data[b1] = data[a];
				} else {
					int olda = a;
					for (++a; a < b1; ++a) {
						if (data[b1] < data[a]) {
							pivot = data[b1];
							data[b1] = data[a];
							data[a] = pivot;
							a = olda;
							break;
						} else if (data[a] < data[b1]) {
							pivot = data[a];
							data[a] = data[olda];
							data[olda] = pivot;
							a = olda;
							break;
						}
					}
				}
			}
			
			if (a < b1) {
				int empty = a;
				for (int aa = a, bb = b1;;) {
					for (++aa; !(pivot < data[aa]) && (aa <= bb); ++aa);
					for (--bb; (pivot < data[bb]) && (aa <= bb); --bb);
					
					if (aa < bb) {
						data[empty] = data[bb];
						data[bb] = data[aa];
						empty = aa;
					} else {
						data[empty] = data[bb];
						data[bb] = pivot;
						
						if (bb - a > size - bb) {
							stack[stackPos] = a;
							stack[stackPos+1] = bb;
							a = bb+1;
						} else {
							stack[stackPos] = bb+1;
							stack[stackPos+1] = size;
							size = bb;
						}
						stackPos += 2;
						break;
					}
				}
				continue;
			}
		}
		
		if (stackPos > 0) {
			size = stack[--stackPos];
			a = stack[--stackPos];
		} else break;
	};
}

Thomas, zdej pa povej kolko je ta verzija počasnejša od prejšnje.

Zgodovina sprememb…

  • spremenilo: gzibret ()

Thomas ::

Bomo pogledali. Zdej maš pač en dialekt QuickSorta, lepo brez kazalcev. Bomo videli, kaj je z njim. Če je kaj konkurenčen.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

BTW, posipam se s pepelom, v obeh kodah, ki sem ju nalepil je majcena napaka:
for (++aa; !(pivot <= data[aa]) && (aa <= bb); ++aa);

bi moralo biti
for (++aa; !(pivot < data[aa]) && (aa <= bb); ++aa);

in podobno za kodo s pointerji. Majhna napaka, ki se mi je prikradla ko sem nadomeščal vse primerjalne operatorje z operatorjem 'manjše'. Sicer algoritem vseeno pravilno dela, le malo počasnejši je s tem bugom. No, vseeno je na moji mašini na pokazanih testih v obeh primerih hitrejši od asorta. Go figure.

edit - obe zgornji kodi sta popravljeni.

Zgodovina sprememb…

  • spremenilo: gzibret ()

Jst ::

Thomas in Nevone, zelo cenim vaš trud v tako s predsodki nabitem področju. Nista pa edina, ki plujeta v tem področju. Tukaj je še intel, kateri je svoj qsort pri Intel c++ compilerju, verzije 9.1, optimiziral za večjedrne procesorje ter sse ukaze.

Ni se mi dalo izumljati randoma, zato sem pri testiranju vzel kar neke vrednosti iz sql tabele in v tabelo dal samo int brez plusa ali minusa, torej ABS.

Zapisov je 900000. Različnih je 810927, najmanjša vrednost, kar se pojavi je 477, največja pa 1890023.

Testiral petkrat zaporedoma.

Asort 270ms; Intel QSort 192ms.
Asort 273ms; Intel QSort 195ms.
Asort 272ms; Intel QSort 193ms.
Asort 273ms; Intel QSort 191ms.
Asort 272ms; Intel QSort 193ms.

Upam, da sem imel kar najmanj obremenjeno mašino. To sem storil tudi s tem, da sem resetiral računalnik in nisem pustil explorerju, da bi se zagnal.

...

Moji rezulati so lahko interpretirani kot goljufanje, saj je Intelov qsort najverjetneje res optimiziran za (intelove) dvojedrne prosecorje s sse ukazi. Je pa zanimiv insight, kako lahko dosežeš boljše rezultate, z uporabo hardware specific funkcijami.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Sayer ::

Povprecje! 20 zaporednih sortov ranga -100000, 100000, items = 10.000.000

1. ASort [latest] = 1054
2. STL Introsort [C++ STL SGI ] = 1213
3. GundolfQSort [table mode] = 1218

CPU: AMD Athlon 64 3000+ [2.01 GHz]


LP

Jst ::

Sicer je pa po mojem mnenju štetje časa izvajanja precej jalov vpogled v sam algoritem. Čeprav sem jaz izrecno prepovedal kakršnokoli optimiziranje, še vedno dvomim, da bo moji rezultati na kakršen koli način primerljivi.

Že pri izbiri različnih compilerjev dobiš drugačne rezultate. Poglejte si recimo nvidin GPUSort. Poseka vse dandanes znane načine, kako urediti neko tabelo. Vendar je spet hardware specific.

Tako se mi zdi najboljši način za primerjanje algoritmov Gundolfov način: štetje operacij nad podatki.


Moja odgovora nista kritika, ampak samo zanimivost.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Sayer ::

Se malo vec info o GPU sortingu:

http://gamma.cs.unc.edu/GPUSORT/results.html


LP

Gundolf ::

Sayer, ti maš počasnejšo mašino, pa ti hitreje sortira kot meni. compiler?

Zgodovina sprememb…

  • spremenilo: gzibret ()

Gundolf ::

Aja Thomas, ti morm priznat, da je vsaj na moji mašini tabelaričen mode tam nekje do 10% počasnejši od pointer moda. Ampak 10% ga še vedno v večini primerov postavi pred asort. Sem pričakoval, da bo razlika 0. Upam da nisem kje zaj.. pri pretvorbi.

gumby ::

copy+paste obeh kod pri meni, v istem .exe:

AS : QS
1328 : 1485
1406 : 1453
1453 : 1453
1516 : 1672
1359 : 1500
1375 : 1516
1328 : 1562
1390 : 1391
1359 : 1391
1344 : 1406

10x zapored pognal, casi so v ms
my brain hurts

WarpedGone ::

jst:

Zapisov je 900000. Različnih je 810927, najmanjša vrednost, kar se pojavi je 477, največja pa 1890023.

Testiral petkrat zaporedoma.


Dej spust oba sorta še nad različnim številom podatkov. Da vidmo če je razmerje med njima konstantno.
Zbogom in hvala za vse ribe

Sayer ::

Gundolf: Compiler je v skupku VS C++ 6.0 ... skompilano je seveda v Release mode-u.

Thomas ::

Tukaj gre debata lahko vsaj v tri veje. Ena je tista, ki jo je začel nicnevem sinoci.

Druga je algoritemska.

Tretja je koderska.

Daleč najbolj me zanima prva. Kaj vse bi bilo mogoče zevoluirati - in kako.

Zaenkrat naj rečem samo to, da se mi še ni uspelo izmisliti kontraprimera. Da se nekaj pa ne bi dalo.

Vprašanje je le, kaj je vredno. Ideje so ...
Man muss immer generalisieren - Carl Jacobi

nevone ::

Gundolf: Ti si implementiral v svojo kodo bistvo prednosti ArtificialSorta (preverjanje že posortanosti segmenta in nekoliko drugačno določanje pivota!) pred standardnim QuickSortom v "svoj" QuickSort!

Skrajno podlo!

Lahko pa daš kakšen link na netu, kjer ima Quick sort implementirano tole Artificialovo finto, če je to že znano.

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

Thomas ::

Bolj kot sort, je hvaležna zadeva za evoluiranje kompresiranje datotek.

Ni kej dost filozofirat. Skomprimira bolj, ali pa ne skomprimira bolj, pa še kode ni treba kazat okoli. Samo en exe, ki dela svoje, pa vsak lahko vidi učinek in samo učinek.

Čist tko, mimogrede.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

> Gundolf: Ti si implementiral v svojo kodo bistvo prednosti ArtificialSorta (preverjanje že posortanosti segmenta in nekoliko drugačno določanje pivota!) pred standardnim QuickSortom v "svoj" QuickSort!
Nevone, v bistvu ne. Čisto tako sem naredil, kot sem že rekel. En lazy swap čez navaden qsort, s čimer sem zmanšal število assignmentov za 1/3, s tradeoffom, da sem dobil mal novih problemov zraven (tega asort ziher nima). Drugo kar je drugače od qsorta je pa le izbira pivota takrat, ko sta oba robna elementa enaka, s čimer sem izboljšal vedenje tam, kjer se elementi fajn ponavlajo. Nobenega preverjanja posortiranosti ni kle (edino shortcut se nardi, če so slučajno vsi elementi v segmentu enaki). Izbira pivota pri asortu je čisto drugačna (aritmetična sredina), tako da tu sploh nimaš kej podobnosti iskat. To, da se z načinom izbire pivota da fajn vplivat na obnašanje qsorta je pa staro kot qsort sam. Tako da podlo od mene je bilo le to, da sem Thomasu (in tebi) to kar s kodo pod nos podvalil.

> Lahko pa daš kakšen link na netu, kjer ima Quick sort implementirano tole Artificialovo finto, če je to že znano.
A to, da se pivot bolj pametno izbere? Google it. Maš sigurno na tone tega na netu. To je tvoja domača naloga ne moja. Jaz sem za zabavo (in zajebancijo) tale qsort mod skupi spravu (ki btw, razen na podanih primerih ni nevem kaj).

Thomas ::

Mau si delal diverzijo, prank, to ti je očitno v veselje, Gundolf.

Medtem ... cenim prispevke ostalih. Tudi tistih, s katerimi se ne strinjam čisto. Da ne bi kdo mislil, da "se mora" vsak kar strinjati z mano. Tiste izjeme v obnašanju sorta, ki jih je navedel jernejl naprimer, so bile zelo dobrodošle. Tako kot vsak prispevek, ki razčiščuje stvari, pa tudi če nekdo (resno!) trdi, da "tale artificial ne dela".

Vse je (lahko) stvar (inteligentne) diskusije.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

> Mau si delal diverzijo, prank, to ti je očitno v veselje, Gundolf.
Ne vem od kje ti ideja o pranku. Kaj si vmes že tako popravil artificial sort da je hitrejši od mojega moda?

Thomas ::

1. "Tvoj" "mod" je nekakšen hibrid med Artificial in Quick.

2. "Tvoj" "mod" ima še vedno šibke točke, ki so pri Artificialu že bile odpravljene, zaradi diskusije z nekaterimi konstruktivnimi ljudmi tule. (Pa ne nujno prijaznimi z mano, da se razumemo!). jernejl je naštel šibke točke 1. verzije in so bile potem fixed, razen tiste, da dela samo do 31 bitov pri 32 bitnih integerjih.

3. Da je "tvoj mod" hitrejši, si izmeril samo ti.

4. Sure, da je že nova, še hitrejša verzija Artificiala.
Man muss immer generalisieren - Carl Jacobi

gumby ::

gundolf: sem probal oba sorta, tvojega iz posta malo visje, thomasovega iz linka v prvem postu - oba copy+paste, brez sprememb. tvoj sort je bil v enem primeru enako hiter, v devetih pa pocasnejsi...
a delam kaj narobe mogoce?
my brain hurts

Gundolf ::

gumby, probi na malo več testih, ampak ne enakih. Različno št. elementov, različen random. Recimo tako kot je bil tisti nevonin al pa moj test.

Thomas> 1. "Tvoj" "mod" je nekakšen hibrid med Artificial in Quick.
Hehe, "moj" mod nima čisto nobene zveze z artificialom. Ti pa zamerim, da ne verjameš da je moj. Očitno misliš da sem artificialu neko idejo 'ukradu'... Bi rad izvedel katero.

> 2. "Tvoj" "mod" ima še vedno šibke točke, ki so pri Artificialu že bile odpravljene, zaradi diskusije z nekaterimi konstruktivnimi ljudmi tule. (Pa ne nujno prijaznimi z mano, da se razumemo!). jernejl je naštel šibke točke 1. verzije in so bile potem fixed, razen tiste, da dela samo do 31 bitov pri 32 bitnih integerjih.
Namiguješ, da nisem bil prijazen s tabo? Ok... Za moj mod vem da ima veliko šibkih točk še. Jaz sem ga spedenal le toliko, da je na teh tistih, ki jih je nevone začela delat (z veliko različnimi velikostmi in random nastavitvami) začel pometat. Se pravi, ko se meri čas in ko se gleda tablee z veliko ponovljenimi elementi.

> 3. Da je "tvoj mod" hitrejši, si izmeril samo ti.
Ja, meni se tudi zdi čudno zakaj nevone kar iznenada ni več objavila malo daljšega testa ampak le en primerček. Do zdaj sem, kolikor sem videl, moj mod obširno primerjal z asortom samo jaz.

> 4. Sure, da je že nova, še hitrejša verzija Artificiala.
Bom pogledal, morda bom pa moral še malo pofrizirat moj mod, da spet ujame/prehiti asort ;)

Gundolf ::

Zadnja verzija je iz 19.3.? S to sem že prej primerjal. Rezultati še držijo.

Thomas ::

Neverjeten je, tale Gundolf.

Ukrasti nima kaj, saj je vse javno objavljeno. Lahko pa si kakšen konček povsem legalno sposodi, vendar ni lepo, da to zanika.


Meri pa tudi precej po svoje.
Man muss immer generalisieren - Carl Jacobi

lymph ::

Ali lahko kdo sploh pove, o točno katerem delu gundolfove kode se govori? Kje je tisti del, ki je iz asorta?
"Belief is immune to counter example."

Thomas ::

Določevanje pivota na neenakost.

if (data[b1] < data[a]) {pivot = data[b1];data[b1] = data[a];
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Če se takšne neenakosti (neposortanosti) ne najde, potem se segment sortira, sicer ne.

To je ena taka kopija, sicer slabša.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Bistvo QuickSorta je v tem, da okoli pivota deliš segment, ne glede na to, če je že posortan.

Uspešno ugotavljanje če bomo sploh sortali, ker je morda že posortano, je pa na netu prvič zaslediti na strani, ki sem jo dal v prvem postu. In izvedeno. V Artificial sortu.

Prej o tem nismo nič slišali, Gundolf je pa že proizvedel en klon.

Sej nič narobe, samo naj to prizna.
Man muss immer generalisieren - Carl Jacobi

jype ::

No, tu pridemo navzkriž. Ta debata je pomembna in nemara za v drugo temo.

Ne moreš biti prepričan, da se ni tega Gundolf prvi spomnil. Ko enkrat vidiš, je stvar očitna, dokler ne, pa lahko traja dolgo (razen s takole pospešeno evolucijo), da na takšno rešitev dejansko pomisliš.

Saj ni nič narobe, če prizna, da je idejo dobil tam, a tudi če ne. V vsakem primeru ideja ne sme biti "izključno njegova" zgolj zato, ker nekdo trdi, da jo je dobil "prvi".

Mimogrede, obstajajo hitrejši algoritmi od umetne evolucije (to je tisto, na kar lahko sklepamo, da tvoj program dela, ker kode ne vidimo). Si že gnetel criticalla samega s seboj?

gumby ::

pri 100M array mi zacne srotat po disku, to ni merodajno...

AS:QS 10M array, -1M/+1M
1390:1625
1375:1563
1391:1562

AS:QS 10M array, -1k/+1k
734:828
734:829
735:812

AS:QS 10M array, -10/+10
312:313
296:313
312:313

AS:QS 100k array, -1M/+1M
0:16
16:15
0:16
tule ocitno je tabela premajhna za karkoli merodajnega

se ponovitev tvojih parametrov, za vsak slucaj:
AS:QS 1M array, -10/+10
32:31
31:31
31:32

AS:QS 1M array, -1k/+1k
78:78
63:94
79:78

AS:QS 1M array, -100k/+100k
109:141
125:141
109:141

AS:QS 1M array, -10M/+10M
125:156
125:156
125:172

AS:QS 10M array, -10/+10
297:312
313:328
297:328

AS:QS 10M array, -1k/+1k
750:829
735:812
750:812

AS:QS 10M array, -100k/+100k
1110:1297
1109:1266
1109:1266

AS:QS 10M array, -10M/+10M
1500:1767
1500:1781
1515:1766

AS:QS 50M array, -10/+10
1531:1578
1531:1578
1594:1625

AS:QS 50MM array, -1k/+1k
3641:4203
3625:4172
3641:4125

AS:QS 50M array, -100k/+100k
5547:6438
5532:6421
5531:6360

AS:QS 10M array, -10M/+10M
8032:9062
8157:9031
8046:9032

a res kaj narobe delam?
my brain hurts


Vredno ogleda ...

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

Quick sort

Oddelek: Programiranje
102371 (1119) drola
»

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

Oddelek: Znanost in tehnologija
141673471 (23640) pietro
»

dos C urejanje po velikosti

Oddelek: Programiranje
81124 (955) klemen22
»

[Turbo Pascal] Pomoč...

Oddelek: Programiranje
131390 (1292) Grey
»

sortirni algoritem v Cju

Oddelek: Programiranje
61359 (1211) GaPe

Več podobnih tem