» »

It means business

It means business

nevone ::

jype>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š.
jype>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".

Najprej zanikanje, da je Artificial sploh kaj hitrejši od QuickSorta, potem pa kar naenkrat on postane avtor ideje. Are you nuts!

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

jype ::

nevone> Najprej zanikanje, da je Artificial sploh kaj hitrejši od QuickSorta, potem pa kar naenkrat on postane avtor ideje. Are you nuts!

Ne gre za ta specifičen primer, gre za problem, da je on "na nekem drugem forumu" lahko rekel, da se je on to spomnu, "en Thomas" mu je pa ukradel.

Ker je edini verodostojen dokaz o prvenstvu lahko javna objava, kjer datuma objave ni mogoče ponarediti, je nesmiselno govoriti o lastništvu nad idejo, pa še v tem primeru je zoprno vprašanje kaj storiti, če je nekdo nekje že objavil iste reči prej, le da tega ni tedaj nihče opazil.

nevone ::

>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.

Zakaj bi ArtificialSort sploh veliko primerjali z nekoliko poslabšanim ArtificialSortom by Gundolf? :\

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

nevone ::

Ajd jype skini se. Odpri novo temo.

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

jype ::

Naslov te teme je malce preveč zbegan, da bi se lahko uprl pisanju v to temo.

Postavil sem tehtno vprašanje o criticallu, pa odgovora kar ni.

Gundolf ::

> if (data[b1] < data[a]) {pivot = data[b1];data[b1] = data[a];
> Če se takšne neenakosti (neposortanosti) ne najde, potem se segment sortira, sicer ne.
NArobe interpretiraš ta naliman segment. Nisem prepričan, da sploh razumeš princim v mojem qsortu (ali qsortu nasploh ko smo že pri tem). Pravzaprav si tule nalimal en del, ki sploh ni moj. Je čisto originalno iz qsorta. Če je prvi element manjši od drugega je pivot prvi element drugače pa drugi, s tem da se ju koj zamenja. Ti si tule nalimal vrstico ki pravi, če je zadnji element manjši od prvega se ju zamenja...

Nisem ravno impresioniran nad tem tvojim 'ukradel je bistvo asorta'. Next please.

Gundolf ::

Aja gumby, izgleda v redu. Na tvoji mašini je moj sort počasnejši. Upam da je zadnja verzija.

Gundolf ::

Evo sem se potrudil in v zgodovini brskalnika našel moj source, iz katerega sem izhajal: quicksort.h
if (a[high]<a[low]) // ensure that a[low]<= pivot, a[high]>= pivot;
    exchange(a,low,high); // this ensures that the inner loops do not  run out of the range
    T pivot(a[low]);


Očitno je že nekdo pred mano moral posnemat artificial sort. Verjetno je potoval v času naprej, počakal na Thomasa in potem ukradel to sporno vrstico ;)

Thomas ::

Jaz popolnoma razumem, da smo kritični in skeptični do vsake novotarije. Jasno, je treba pogledat.

Ampak ena posebna alergija na to, da bi kakšen Kranjc pogruntal kaj novega (bohnedaj, še s kakšnimi svojimi "grunt geretami") ... je pa sick mentaliteta, predvsem doma v deželah, kjer je praznik, če sosedu crkne krava.

Bohnedaj, da bi imel Thomas prav z Artificialom! Sploh pa Bohnezadeni, da ima prav s Critticallom!

Zato dejmo strpat Artificial nazaj pod varno okrilje QuickSorta!

Ponavljam. Razumem kritiko, razumem meritve ... ampak več pa ne.

Po eni strani imajo polne usta Cankarjevih Hlapcev, po drugi strani so pa prav lepo servilni do zaprašenih belosvetskih (kot bi rekli Srbi), akademikov.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Kakšne so torej razlike med QuickSortom in ArtificialSortom?

Gundolfov "eklekticizem", pustimo ob strani. Oni ni izumil ničesar, nekoliko je poberkoval sem in tja, čeprav zatrjuje da ni. V svoji vnemi za "ne sme biti Artificial boljši od QuickSorta".


Artificial išče eventualno mesto, kjer se v segmentu prekine urejenost.

Quick tega ne počne. Tak ki bi, je pa počasnejši.

Artificial pivota ne umika in ne vrača, Quick ga mora.

Artificial strogo razdeli segment na večje kvečjemu enake od pivota, Quick enake pivotu dopušča tu in tam.

Artificial zato lahko dela s pivotom, ki ni member segmenta.
Man muss immer generalisieren - Carl Jacobi

WarpedGone ::

Dejte mir ;((

Thomas, kolk je kej dela, da se Crittical dodela v "distributed computing friendly" varianto?

Kaj fejst hudo nebi smelo bit. Nucaš en simpl serverčk, ki bo zbiral trenutne zmagovalce, pa mogoče mal usmerjal ostale kliente, da ne rinejo v že raziskane smeri.

Se bi znal kr splačat :)
Zbogom in hvala za vse ribe

Gundolf ::

Mal se moraš pomirit Thomas.
Moj namen je bil (sej sicer mislim, da sem bil v tistem postu ko sem dal kodo al pa v enem prej dovolj jasen o mojih namenih), da ti pokažem, da moraš primerjat primerljive stvari. Ne enga generičnega quicksorta s tvojim sortom na tvojem terenu (in pol sklepat da je tvoj sort generično boljši), zato sem ti dal en qsort, ki mu tvoj teren ni čisto tuj. Sem ti reku, da ga komot izrabiš kot seed za nasledno verzijo tvojga sorta. To, da si se nato bunil, kako ta qsort v bistvu jemlje zamisli iz tvojega artificial sorta kaže le na to kako ti ne znaš kode analizirat. To, da pa zdaj svoje standardne pridige (a la nevoščljivost) ven mečeš je pa sploh mal off.

Da ne bo pomote, ko pravim 'tvoj teren' imam v mislih: sortiranje random elementov, ki se na veliko ponavljajo ter merjenje časa izvajanja ko operiraš z inti.

Gundolf ::

> Artificial strogo razdeli segment na večje kvečjemu enake od pivota, Quick enake pivotu dopušča tu in tam.
Evo če bi to prej reku bi lahko potrdil, da je to v mojem sortu dejansko podobno. Sem pa spremenil preprosto zato, ker moj qsort source ne le da je puščal elemente enake pivotu na obeh straneh (kar je pravzaprav kar pametna stvar in bi rekel da celo prednost in bom poskušal nazaj spraviti v moj sort, če ga bom še kaj poliral), celo premetaval jih je med sabo.

nevone ::

Prosto po Gundolfu naj bi tale quicksort.h uporabljal finto, ki jo uporablja ArtificialSort. V resnici tista koda in tisti izsek, ki ga je citiral Gundolf počne nekaj drugega. Whom are you kidding?

To le pa test Artificial-a in Quicka in omenjenga linka:

NumOfRecords = 10.000.000 Data = Rnd(-1000,1000)

QuickSort      elapsed time = 10015 ms
ArtificialSort elapsed time =  2015 ms

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

Thomas ::

> da je to v mojem sortu dejansko podobno

Kaj je zdej? Si tudi ti izumil kakšen nov algoritem?

Mi je prav žal, ampak noben "tvoj" sort ne obstaja. Še najmanj boljši od Quick ali celo Artificial sorta.

Če pa misliš da je, daj lepo tabelo z rezultati na nek site!
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> Nucaš en simpl serverčk, ki bo zbiral trenutne zmagovalce, pa mogoče mal usmerjal ostale kliente

Včasih se pri naši hiši zatekamo k lowtech rešitvam. V temle primeru že. Samo to v oni, urniški verziji. Poženejo na kakšnih 20 računalnikih sestavljanje urnika, potem pa po 24 urah ali kaj takega, ročno preselijo alfa urnik (en txt file) na 10 "najslabših računalnikov". Kakšnega čez palec ocenijo za perspektivnega in ga ne prekrijejo z alfo. Selijo stvar preko interneta celo, na razne lokacije in se ob tem obilo zabavajo, kot sem že dostikrat videl - in česar sem jih pravzaprav naučil.

Bo pa morda vseeno zdejle enkrat to začelo delovat kar samodejno preko interneta. Ko bo eden precej boljši, bodo tudi drugi namenili nekaj svojega časa vzgajanju alfinih potomcev.

Samo alfa lahko vsak trenutek pade, ga komot prehiti kakšen dark horse - in postane alfa do nadaljnega.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

> Prosto po Gundolfu naj bi tale quicksort.h uporabljal finto, ki jo uporablja ArtificialSort.
Oh ja nevone. Še enkrat premisli vse skupi. Thomas je tule nalimal del moje kode, ki naj bi bil a la artificial sort. Se strinjaš? Jaz sem pokazal ta kos kode v izvornem quicksortu. Se strinjaš? Jaz nisem nikoli trdil da un quick uporablja kakršnokoli finto iz artificiala. Tisto s potovanjem v prihodnost je bil sarkazem ;) Jaz še vedno trdim, da si oba sorta sploh nista podobna.

No tkole še eni rezultati:
Opteron:
size = 10000000, rnd. param = 10, avg element freq. = 526315.812500: asort time = 33, qsort time = 39, gcc std::sort time = 73
size = 10000000, rnd. param = 1000, avg element freq. = 5002.501465: asort time = 84, qsort time = 96, gcc std::sort time = 101
size = 10000000, rnd. param = 100000, avg element freq. = 25.582907: asort time = 138, qsort time = 157, gcc std::sort time = 135
size = 10000000, rnd. param = 10000000, avg element freq. = 1.173663: asort time = 172, qsort time = 197, gcc std::sort time = 154
size = 50000000, rnd. param = 10, avg element freq. = 2631579.000000: asort time = 184, qsort time = 209, gcc std::sort time = 394
size = 50000000, rnd. param = 1000, avg element freq. = 25012.505859: asort time = 431, qsort time = 522, gcc std::sort time = 542
size = 50000000, rnd. param = 100000, avg element freq. = 125.566620: asort time = 703, qsort time = 820, gcc std::sort time = 725
size = 50000000, rnd. param = 10000000, avg element freq. = 1.976009: asort time = 953, qsort time = 1085, gcc std::sort time = 853

Xeon (50M elementov je nažalost malo preveč zanj, zato sem uporabil 40M):
size = 10000000, rnd. param = 10, avg element freq. = 526315.812500: asort time = 34, qsort time = 35, gcc std::sort time = 58
size = 10000000, rnd. param = 1000, avg element freq. = 5002.501465: asort time = 85, qsort time = 88, gcc std::sort time = 96
size = 10000000, rnd. param = 100000, avg element freq. = 25.582907: asort time = 145, qsort time = 152, gcc std::sort time = 141
size = 10000000, rnd. param = 10000000, avg element freq. = 1.173663: asort time = 193, qsort time = 201, gcc std::sort time = 163
size = 40000000, rnd. param = 10, avg element freq. = 2105263.250000: asort time = 134, qsort time = 140, gcc std::sort time = 253
size = 40000000, rnd. param = 1000, avg element freq. = 20010.005859: asort time = 338, qsort time = 352, gcc std::sort time = 394
size = 40000000, rnd. param = 100000, avg element freq. = 100.552032: asort time = 571, qsort time = 595, gcc std::sort time = 568
size = 40000000, rnd. param = 10000000, avg element freq. = 1.762074: asort time = 823, qsort time = 862, gcc std::sort time = 707

Pri obeh je artificial hitrejši. Pa tudi std sort na teh mašinah ni več tako nebogljen. Je pa dobro vprašanje kaj je na moji kišti drugačnega, da je taka razlika (ne samo ta razlika, da je qsort hitrejši ampak tudi da je vse vsaj ene 10x počasnej). Velik hitrejši RAM? Cachea dvomim da ima kaka mašina neizmerno več.

Thomas ::

No, zdej bi bilo lepo videti še source vseh treh. Qsort, Asort in STD::Sorta.

Ker če se uporabljajo kazalci, je to lahko pomembno. Imamo verzijo artificiala s kazalci in je še hitrejši od objavljenega na Critticall.com/underconstruction.html.

Kar je logično. Boljši je algoritem, bolj mu pomagaja steroidi, kot so kazalci assembler in podobno.

Nek MMX SSE assembliran Artificial bi/bo še hujša mašina.
Man muss immer generalisieren - Carl Jacobi

nevone ::

>Thomas je tule nalimal del moje kode, ki naj bi bil a la artificial sort. Se strinjaš?

Ja.

>Jaz sem pokazal ta kos kode v izvornem quicksortu. Se strinjaš?

Ne.

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

Gundolf ::

Mogoče ti bo pomagalo, če veš kaj je ekvivalentno:
data...a
a...low
b1...high
Ostalo kar manjka v moji kodi (da bi bila ekvivalentna tistemu exchangu) je to kar sem imenoval lazy swap. Ne naredim delega swapa takoj. Če se ne strinjaš da je to enako pa napiš kje se razlikuje.

P.S. pri unih opteron in xeon testih je dejansko treba čase z 10 množit. Sem zafrknu pri pretvorbi v linux. Ampak razmerja so prava.

Zgodovina sprememb…

  • spremenil: Gundolf ()

nevone ::

Glej Gundolf, tista tvoja koda upošteva nekaj, kar je izumil Critticall že zdavnaj nazaj. In to je, da veliko enakih elementov se da s ustreznim pristopom bolj efikasno sortirat (Several Unique Sort). Nekaj tega vedenja si ti vkomponiral v svojo verzijo Quick sorta. Vsaj to bi lahko priznal, preden se naprej pogovarjamo.

Ker QuickSorta, za zelo randomizirano dato, smo pospešili v bistvu zanemarljivo. Največji gain tega ArtificialSorta je ravno pri večjem pojavljanju enakih elementov.

Če ti tole ne zadostuje, greva lahko analizirat tvojo kodo naprej.

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

Sergio ::

Uf madona.

Kako "lepo" je videt, ko se v eno prelepo temo usuje bitka Treh Egov.

Zarad mene me ni treba poslusat, in se tut ne mislim vec umesavat, ampak vseeno, si ne morem pomagat:

Ego pustite PRED vrati, in dejmo se pogovarjat na nekem nivoju, madona. Jaz sem precej navdusen nad ASortom, ampak ce bo thread namenjen temu, da se bo metalo blame-throwing in iskalo "krivca" za nekaj, za kar sploh ne mores iskati krivca, se bo ta tema tako hitro izrodila v splosno prerekanje, da bo izgubila svoj smisel.

Dejmo se drzat tega, o cemer se pogovarjamo. Imamo nek nov sort. Vzamimo se kaksen drug sort. Pa tut ce je izpeljan iz ASorta, a je to kej narobe? Sej tega eksplicitno ne prepovedujes, Thomas. Ce pa ne zelis tega, pa napisi na stran, pa je problem resen.

Bistvo je, da dobimo nek kick-ass sort, ki ga svet se ni videl. Personal stories aside, ker samo zavirajo celotno zgodbo.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

gumby ::

gundolf: jaz sem vzel za test drugo kodo, torej tisto brez kazalcev.
my brain hurts

nevone ::

Sergio, a si sprobal ArtificialSort z InsertionSortom v Javi?

Sicer je zdej še vedno en goto noter. No če je to problem, se ga da zelo enostavno rešit, saj se da tisti goto zelo enostavno ukinit, ne da bi kaj bistveno vplivalo na performanse.

Kar se pa Egov tiče. Zakaj bi nekdo dopuščal, da mu serejo na glavo?

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

Gundolf ::

No bistvo te teme je pomoje, da se pokomentira asort. Kode direktno ravno ne mormo komentirat (očitni problemi se kažejo pri komentiranju moje kode). No razen kakšnih pripomb na dokaj očitne stvari, ki smo jih že dal skoz. Tud smo že rekl neki na uporabo merjenja časa kot the merila za primerjavo algoritmov. Spada verjetno že malo preveč v teoretično računalništvo, da bi bilo tule dobro sprejeto. Brezplodno bi bilo nadalje debatirat.

Jaz sem se odločil da se lotim zadeve iz druge strani. Skupi spravim algoritem, ki bo po danih merilih našopal ta asort (ali kot se izkaže je relativna performansa zelo odvisna od platforme). No tu vstopita v igro prva dva ega, ki ne moreta sprejet, da bi lahko bil en enostaven izzivalec na istem nivoju kot asort. Torej mora bit skopiran. Tretji ego seveda ne bo dovolil, da mu očitajo nekaj kar ni res. Z veseljem priznam vse podobnosti med algoritmoma, ki jih kdorkoli najde (Thomasu sem že potrdil, da moj algoritem isto kot asort in drugače kot qsort, sortira na eno stran elemente ki so manjši ali enaki od pivota, na drugo pa elemente ki so večji). Komentarji v tem stilu - ni problema, vse potrdim ali ovržem. Ampak, da mi pa očitata, da je od asorta skopiran nek totalno generičen del kode, oz. še huje - en del kode, ki je popolnoma očitno že vsebovan v algoritmu iz katerega sem jaz izhajal - se mi pa preneumno zdi, da bi bil tiho.

In ker splošna publika ni tako neumna, da bi šla naštudirat obe kodi samo zato da vidi a sta podobni al ne, pride do situacije ko lahko mi tule vpijemo en na drugega "ja pa si! ne pa nisem!". Zelo lepo si posegel vmes Sergio, ampak na koncu boš še srečen če boš sam odnesel celo kožo ;)

Nevone: če se strinjaš lahko tole debato preseliva v drugo temo ali pa v zs. ampak temule se ne boš izognila: "Če se ne strinjaš da je to enako pa napiš kje se razlikuje." Tvoj: "Glej Gundolf, tista tvoja koda upošteva nekaj, kar je izumil Critticall že zdavnaj nazaj..." me ne impresionira. Napiši, kje se moja koda (ki jo je nalimal Thomas) razlikuje od generične kode (ki sem jo nalimal jaz) pa pika. Magari vzemi list papirja, predvori imena spremenljivk, da bodo enaka pa primerji.

gumby - ok, samo v obeh sem imel najprej en = odveč. Koda se je zato vmes malo spremenila. Po tem sem te spraševel.

Zgodovina sprememb…

  • spremenil: Gundolf ()

jernejl ::

Se strinjam s Sergiom, sam se pa v debato o tem, čigavo je kaj in kdo je nevoščljiv ali pristranski, ne bom spuščal. Je škoda energije, da bi jo za to zapravljal.

TEST: st.elementov=10000000, array[i] = rand()|(rand()<<15);

Gundolf quicksort Elapsed time = 1984 ms
Optimized Median (Hybrid) QSort Elapsed time = 1391 ms
Artificial Elapsed time = 1469 ms
Radix Sort Elapsed time = 672 ms
STD Sort Elapsed time = 1516 ms
MergeSort Elapsed time = 2219 ms
QSort Elapsed time = 3750 ms

TEST: st.elementov=10000000, array[i] = Rnd(1,100000)-Rnd(1,100000);

Gundolf quicksort Elapsed time = 1422 ms
Optimized Median (Hybrid) QSort Elapsed time = 1250 ms
Artificial Elapsed time = 1078 ms
Radix Sort Elapsed time = 594 ms
STD Sort Elapsed time = 1359 ms
MergeSort Elapsed time = 2125 ms
QSort Elapsed time = 2750 ms

Procesor: AMD Athlon64 3500+ (2200MHz), g++ optimizacija: -O3

Tudi jaz ne morem potrditi, da bi bil algoritem, ki ga je podal Gundolf, kaj hitrejši od Artificial sorta (vsaj iz teh meritev, ki sem jih izvedel. Njegovo kodo sem iz foruma skopiral danes, in sicer tisto brez kazalcev).

Bom povedal še tretjič (in zadnjič), da se mi zdi ena vrstica v Artificial sortu še posebno problematična.
meja = ( temp1 + temp2 + 1 ) >> 1;
Dokler bo tale vrstica v algoritmu, algoritem ni in ne more biti splošen algoritem urejanja s primerjavami, zaradi tega je potrebno primerjave s quicksortom jemati z rezervo.

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.


Kar se tiče algoritmov stiskanja podatkov (Thomas je verjetno mislil na brezizgubne tehnike stiskanja), pa tudi tam zadeva ni tako enostavna, kakor se jo želi predstaviti. Za algoritme stiskanja je prav tako pomembna hitrost izvajanja. Pravzaprav se tukaj ločujeta dve hitrosti: hitrost kompresije in hitrost dekompresije. V določenih aplikacijah je pomembneje, da zna algoritem podatke hitreje stisniti, pri drugih je pomembneje, da je hitrejša dekompresija (odvisno od tega, ali se podatke pogosteje stiska, ali pa se stisnjene podatke pogosteje uporablja - en primer, kjer je stiskanje bistveno počasnejše in zahtevnejše od dekompresije, je lahko digitalni video).
Druga zadeva je prostorska zahtevnost takih algoritmov. Algoritmi stiskanja uporabljajo drevesa, slovarje, ... in velikost slovarjev lahko zelo naraste, zato jih je treba omejiti - to pa spet vpliva na faktor stiskanja.
In še tretje: faktor stiskanja je odvisen tudi od tega, kakšni so podatki (podobno, kakor je s hitrostjo urejanja). Različni algoritmi se tukaj različno obnesejo.

Zaradi tega se tudi pri stiskanju uporabljajo različni algoritmi z različnimi parametri, odvisno od zahtev okolja, kjer se uporabljajo. Vsekakor pa faktor stiskanja večinoma ni edino merilo (je glavno, ne pa edino).
Bo pa zagotovo zanimivo, če boste z evolucijo poskusili tudi v tej smeri.

Zgodovina sprememb…

  • spremenil: jernejl ()

nevone ::

Evo eno animacijo treh sortov v naslenjem zaporedju:

QuickSort | ArtificialSort | GundolfSort

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

nevone ::

Še nekaj raziskav:

-----------------------------------------------------------------------------------------------------
NumberOfRec = 30.000.000         NumberOfRec = 10.000.000         NumberOfRec = 10.000.000
-----------------------------------------------------------------------------------------------------
Data = Rnd(-10000000, 10000000)  Data = Rnd(-10000000, 10000000)  Data = i + Rnd(-10000000, 10000000)
 ArtificialSort = 12703 ms        ArtificialSort =  4000 ms        ArtificialSort =  3969 ms
 GundolfSort    = 14109 ms        GundolfSort    =  4563 ms        GundolfSort    =  4641 ms
                                 
Data = Rnd(-1000000, 1000000)    Data = Rnd(-1000000, 1000000)    Data = i + Rnd(-1000000, 1000000)               
 ArtificialSort = 10703 ms        ArtificialSort =  3641 ms        ArtificialSort =  3734 ms               
 GundolfSort    = 11984 ms        GundolfSort    =  4047 ms        GundolfSort    =  5282 ms               
                                                                                                          
Data = Rnd(-100000, 100000)      Data = Rnd(-100000, 100000)      Data = i + Rnd(-100000, 100000)        
 ArtificialSort =  8766 ms        ArtificialSort =  2906 ms        ArtificialSort =  3375 ms             
 GundolfSort    =  9828 ms        GundolfSort    =  3250 ms        GundolfSort    = 12750 ms               
 
Data = Rnd(-10000, 10000)        Data = Rnd(-10000, 10000)        Data = i + Rnd(-10000, 10000)
 ArtificialSort =  7063 ms        ArtificialSort = 2453 ms         ArtificialSort =  2937 ms  
 GundolfSort    =  8266 ms        GundolfSort    = 2687 ms         GundolfSort    ne deluje
                                 
Data = Rnd(-100, 100)            Data = Rnd(-100, 100)            Data = i + Rnd(-100, 100)    
 ArtificialSort =  3813 ms        ArtificialSort = 1266 ms         ArtificialSort =  2203 ms  
 GundolfSort    =  4265 ms        GundolfSort    = 1453 ms         GundolfSort    ne deluje
                                 
Data = Rnd(-10, 10)              Data = Rnd(-10, 10)              Data = i + Rnd(-10, 10)     
 ArtificialSort =  2156 ms        ArtificialSort =  813 ms         ArtificialSort =  2125 ms 
 GundolfSort    =  2485 ms        GundolfSort    =  844 ms         GundolfSort    ne deluje
====================================================================================================
====================================================================================================

NumberOfRec = 10.000.000  
Data = urejeno naraščajoče + 100 random zamenjav dveh naključnih elementov

 ArtificialSort =  484 ms                                 
 QuickSort      = 1109 ms
 GundolfSort    ne deluje

----------------------------------------------------------------------------------------------------

NumberOfRec = 10.000.000  
Data = urejeno padajoče + 100 random zamenjav dveh naključnih elementov

 ArtificialSort =  579 ms
 QuickSort      = 2062 ms
 GundolfSort    ne deluje
====================================================================================================

Edit: Problem pri ArtificialSortu za zadnji primer date je fixed.

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

Zgodovina sprememb…

  • spremenila: nevone ()

Thomas ::

@sergio:

Zakaj misliš, da je spremenljivka ego kakšen faktor pri sortu? Ni, je samo off topic distraction.

@jernejl:

Čistunstvo, ki ga zagovarjaš glede aritmetične sredine pri Artificialsortu je nekoliko licemerno. Namreč QuickSort prav tako računa aritmetično sredino dveh indexov. Če imamo posortati milijardo in pol recordov, potem že ni mogoče izračunati middle spremenljivke za segment nekje proti koncu. Vsota dveh indexov okoli milijarde in pol - da okoli minus milijardo pri 32 bitnem int tipu.

Pa ni samo QuickSort ali ArtificialSort omejen na neko poddomeno delovanja, že programčič za izračunavanje vsote dveh 32 bitnih števil NE funkcionira za vse 32 bitne integerje. To je NORMALNA situacija za vse implementacije vseh algoritmov, da imajo neko poddomeno domene osnovnih tipov, kjer so veljavni. Tega bi se morali naučiti že v programerskem vrtcu, ne pa da opletamo tukaj s tem. Ja?

Kar se tiče "urejanja vseh tipov", je to spet ena taka zmota in iluzija. Če nad tipom spremenljivke ni definirana relacija urejenost "večje, enako, manjše", potem noben sort nima niti kaj počet.

Vendar za tip integer (kolikor bitni že) in za tip float, je zadeva jasno definirana. Za tip string ali tip char, pa jo definiramo z neko funkcijo. Natančno sem povedal, kako se potem lahko za tak tip določi povprečje.

Tudi o tem je bilo škoda sploh zgubljati besed.

Po drugi strani mi pa ni jasno, kaj počneš z Radixom, ker za ta tip že float ne dela. To da si rekel, da "ga predelaš", pa temu ni tako. Float tip števila niso enakomerno posejana po realni osi!!! Prevedba v bite, da bi lahko porabil Radix sort, bi zahtevala najmanj bistveno več bitov, za opis vseh s floatom kritih vrednosti.

Mi je prav žal.

Si pa lepo dal izjeme, pri katerih bi Artificial pokleknil, če ga ne bi malko popeglali. Za to opozorilo ti pa credit gre, hvala lepa.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

No evo nevone, tko se diskreditira en algoritem, da se mu primer kjer totalno pogori :)

Thomas, kar se tiče poddomene delovanja - še vedno se za vsak algoritem vzame čim večjo poddomeno. In ta je ponavadi v primeru sortov kar enaka domeni. In razlika s seštevanjem - tam je rezultat vedno v drugi domeni kot operanda (ima en bit več), medtem ko pri sortu to ni tako. Tebe ne bi prav nič stalo, če bi aritmetično sredino izračunal naprimer kot "right - ((right - left) >> 1)". Pa maš inte pokrite.

Glede radix sorta pa raj ne bom komentiral. Se raj ne zapletam še v eno kontraverzijo.

Thomas ::

> tam je rezultat vedno v drugi domeni kot operanda (ima en bit več)

Za seštevanje dveh to že mogoče gre. Kaj pa množenje dveh? To je še bolj omejeno, saj se število bitov dveh cirka sešteje.

Kar je pa POPOLNOMA NORMALNO.
Man muss immer generalisieren - Carl Jacobi

Fave ::

Thomas: Tule imaš po mojem zamenjana napisa pod slikama.
My mind's a hyper tool that fixes everything.

Thomas ::

Ne, ni zamenjano. To je primer, ko je Quick hitrejši. Oziroma ima pri tem (malem) random sampleu vsaj manj pisanja, kot Artificial.

Hvala za opozorilo, vseeno.
Man muss immer generalisieren - Carl Jacobi

Sergio ::

>> Zakaj misliš, da je spremenljivka ego kakšen faktor pri sortu? Ni, je samo off topic distraction.

@Thomas: Exactly. Tocno to sem hotel povedati. Da je off topic, in da je distraction.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

gumby ::

gundolf: popravljeno verzijo mam, brez odvecnega enacaja
my brain hurts

Thomas ::

A chat with my imaginary friend Kroft, about the Artificial sort.

Kroft: Hi Thomas, kako si?

Thomas: Hvala lepa, je bilo že slabše. Pa ti, moj namišljeni prijatelj, kako si?

Kroft: Kako naj pa bo izrodek domišljije? Zadnje čase mi je zelo primanjkovalo substrata na katerem živim. Ciklov tvojega uma.

Thomas: Jah oprosti, sej veš kako je, mam tolk za mislit drugih reči. Še dobro, da imam Critticall, preložim nekatere zadeve tudi nanj.

Kroft: Tale sort, ta me zanima. Kako je nastal, dobil ime in tako naprej?

Thomas: Nastal je pravzaprav kot generalizacija Several Unique Sorta, ki sem ga zagledal na ekranu že par let nazaj. Samo tisti je hitro deloval SAMO za malo unikatnih recordov, Artificial se pa uspešno kosa s Quickom tudi povsod, kjer ga ne pusti v prahu za seboj.

Kroft: Torej si hotel odpraviti to pomakljivost Several Uniquea?

Thomas: Hotel sem narediti splošni kompres, za install programa. Da potlači tiste fajle v en čimmanjši exe. Free instalerja nočeva z nevone več uporabljat, deluje nekoliko ceneno.

Kroft: In hočeš reči, da si hotel s Critticallom narest kompres, pa je ven padel sort? Are you nuts?

Thomas: Sort in compress sta deep down essentially interconnected. Informacijska entropija, pa tiste vaje, sej veš. No in jaz sem v enem vikendu, kolikor sem si vzel za to, da naredim compress, da ga nevone vgradi v install, naredil samo polovico dela. Sort je polizdelek kompresa.

Kroft: Aha, torej installer je še tastari, sort pa že tanovi?

Thomas: Ne, ni. Nevone je vzela kar tisti LWZ, LZW, al kako se mu že reče, pa tudi dela. Malo slabše, ampak ni kritično. Sort je pa poimenovala ona. V Artificial. In sploh bila pomagavna, kot zmeraj.

Kroft: Bral sem temo na Slotechu. Čudno, na kaj vse naletiš v takem zakotju, kot je Slovenija. Nepoznavalcu tematike, se mora zdeti vse skupaj kot kakšna pretirana znanstvena fantastika ali pa še en scam.

Thomas: Tako nekako se zdi še celo poznavalcem. Ne vsem, eni komot prebavijo, nekaterim pa ja. Bi jih koštala preveč nujna preureditev njihovega memeplexa.

Kroft: Misliš, da se težko odrečejo temu, s čemer so rasli gor? Ideji, da je QuickSort pač najboljši teoretično možni sort?

Thomas: Ta mantra je samo vrh ledene gore. Že ta je dovolj masiven, pod vodo pa se skrivajo še ene težje zadeve. Nekako bi (morda) celo prenesli, da je smart ass kot Thomas ukanil vse doktorje sortiranja zadnjih desetletij. Če že ne gre drugače. Bolj je problem to, da to ni zraslo v njegovem zelniku, pač pa v zelniku nekakšnega njegovega AIja. To je pa že preveč scary.

Kroft: Maybe to poveča tudi verjetnost, da imaš še marsikje drugje prav?

Thomas: Tudi nekoliko.

Kroft: Kje je meja sortov?

Thomas: Podvojitev do potrojitev hitrosti za 50 milijonov recordov, če ga nabildamo s MMX in podobnimi steroidi, poleg še vsaj dveh algoritemskih izboljšav, ki sta že najdeni, pa še neobjavljeni.

Kroft: Samo tebe ne zanima sort, prav zelo.

Thomas: Ne. Ne preveč.
Man muss immer generalisieren - Carl Jacobi

Fave ::

Thomas: :D

Ko ti je vsega dovolj, je to še najboljša možnost...
My mind's a hyper tool that fixes everything.

svencbir ::

Cestitke Thomasu.

Kapo dol, naredu si vrhunsko zadevo. Kdaj lahko pričakujemo dr.Thomasa z castnim doktoratom?

gumby ::

thomasa bi moral sprocesirat critticall... me prav zanima, kaj bi nastalo:)
my brain hurts

lymph ::

AThomas bi ven prišel, še boljši in hitrejši. Pa grizel bi
"Belief is immune to counter example."

Thomas ::

Ah, jaz sem samo preprost kramar, ki prodaja svojo robo. Artificial šenkujem za reklamo in za zastraševanje. Zastraševanje v smislu - ej, brez naše robe si nekonkurenčen, poglej si samo sortarje, kako niso mogli naprej, dokler ni prišel ljubljeni Critticall na tržišče.

No more, no less.
Man muss immer generalisieren - Carl Jacobi

jernejl ::

Thomas, mislim da me nisi povsem dobro razumel, zato bom poskušal še enkrat pojasniti.

Čistunstvo, ki ga zagovarjaš glede aritmetične sredine pri Artificialsortu je nekoliko licemerno. Namreč QuickSort prav tako računa aritmetično sredino dveh indexov. Če imamo posortati milijardo in pol recordov, potem že ni mogoče izračunati middle spremenljivke za segment nekje proti koncu. Vsota dveh indexov okoli milijarde in pol - da okoli minus milijardo pri 32 bitnem int tipu.

Razlika med QuickSortom (QS) in Artificial (AS) je v tem, da določene izvedbe QS računajo aritmetično sredino dveh indeksov (!), medtem ko AS računa aritmetično sredno dveh osnovnih tipov (osnovni tip naj bo tip podatkov, ki jih urejamo).
Za razliko od QS mora biti pri AS razen relacije urejenosti nad osnovnim tipom definirana še operacija seštevanja itd (tako da lahko izračunamo aritmetično sredino). Zaradi tega AS niti ne spada več v definicijo urejanj s primerjavami, za katera je postavljena meja O(n log n).
Dokler urejamo tip "int", tukaj ni večjih težav. Za ta tip je že Gundolf pojasnil, kako se izračuna aritm. sredina dveh pozitivnih indeksov brez prekoračitve.
Ko (in če) bo AS splošen (verjetno implementiran s predlogami), pa ne bo mogel več računati aritmetične sredine osnovnih tipov; in če vseeno bo, ga ne moremo več neposredno primerjati s QS.

Pa ni samo QuickSort ali ArtificialSort omejen na neko poddomeno delovanja, že programčič za izračunavanje vsote dveh 32 bitnih števil NE funkcionira za vse 32 bitne integerje. To je NORMALNA situacija za vse implementacije vseh algoritmov, da imajo neko poddomeno domene osnovnih tipov, kjer so veljavni. Tega bi se morali naučiti že v programerskem vrtcu, ne pa da opletamo tukaj s tem. Ja?

To (delovanje na le neki poddomeni osnovnih tipov) vsekakor NI normalna situacija za vse implementacije vseh algoritmov! Določeni algoritmi so res lahko omejeni, vsi pa prav gotovo ne. Osnovni QS prav lepo dela s celotnim razponom osnovnih vrednosti, prav tako ostali znani algoritmi urejanja. Morda si tukaj nekaj zamešal, in sicer ravno to, o čemer govorim v prejšnjem odstavku. Osnovni QS ne računa aritmetične sredine dveh osnovnih tipov, kvečjemu aritmetično sredino dveh indeksov. Če je torej kje omejen, je lahko tukaj. A seveda ni, saj je že Gundolf povedal, kako se to napravi brez prekoračitve. Prav tako polje ne more biti neskončno dolgo, temveč mora vedno obstajati tip, v katerem je maksimalna dolžina polja predstavljivo število (v c/c++ je to size_t in je navadno enak kar unsigned int). Zaradi tega se ne more zgoditi, da ne bi mogli izračunati aritmetične sredine dveh indeksov polja.

Kar se tiče "urejanja vseh tipov", je to spet ena taka zmota in iluzija. Če nad tipom spremenljivke ni definirana relacija urejenost "večje, enako, manjše", potem noben sort nima niti kaj počet.

Vendar za tip integer (kolikor bitni že) in za tip float, je zadeva jasno definirana. Za tip string ali tip char, pa jo definiramo z neko funkcijo. Natančno sem povedal, kako se potem lahko za tak tip določi povprečje.

Ravno to je nenavadno. Za urejanje namreč ni običajno, da bi moralo biti definirano tudi povprečje, ampak je običajno dovolj, da je definirana relacija urejenosti (in to velja za urejanje s primerjavami, tudi za QS).

Po drugi strani mi pa ni jasno, kaj počneš z Radixom, ker za ta tip že float ne dela. To da si rekel, da "ga predelaš", pa temu ni tako. Float tip števila niso enakomerno posejana po realni osi!!! Prevedba v bite, da bi lahko porabil Radix sort, bi zahtevala najmanj bistveno več bitov, za opis vseh s floatom kritih vrednosti.

Radix prav lepo dela za tip float (implementacije za c++ se da na googlu najti brez težav).
Implementacijo radix sorta je treba prilagoditi tipu (odvisno od tega, ali urejamo unsigned int, int, float s pozitivnimi vrednostmi, float).

Thomas ::

Utter nonsense you speak, my friend.

> Za urejanje namreč ni običajno, da bi moralo biti definirano tudi povprečje

> Radix prav lepo dela

A štetje pojavitev je pa običajno, kar Radix počne v srcu algoritma?

Tudi ni bil stack "običajen", dokler je obstajal samo Bubble. Ko pa je prišel QuickSort ... je bil nujen. Tako kot je štetje nujno za Radix.

Lej jernejl ... ti nisi nekdo, ki bi ga jaz skušal prepričati. Ali boš sam počasi prišel do tega, ali pa bom zate rekel "I had to left him behind".

Ker kramarji nimamo časa, da bi se kaj dosti preklali z "akademiki". Samoljoti morajo leteti, ne glede na to, kaj pravi kraljevski astronom gospod Newcomb.
Man muss immer generalisieren - Carl Jacobi

donfilipo ::

Hja a nej še enkrat čestitam (sem že pred 5 leti) al naj pojasnim Thomas?
Pa bom raje drugo, v upanju da ta offtopic zabeli temo in jo naredi res strupeno.
Thomas je čuden tič. Malce neverjeten. To vemo vsi, ki ga poznamo že 30 let in več.
Torej naredil je zmaja, ki je večji od vseh ljubljanskih...sicer ne leti, je pa lep. In naredil je Critticall.... slovenski AI, ki ni lep (razen morda za programerje), ampak leti. Zakaj ni cvetja in majoretk ob prvih vzletih in junaških podvigih, zakaj ni vzpodbud gospode Janezov in ostalih svetnikov, da o grešnikih z denarjem ne govorim. Veste, morda bi se moral najti svetovalec z računalniške prižnice, ki bi svetnikom pojasnil, kaj dogaja. Pa sem se čudil kako hudiča lahko ti učeni svetovalci futrajo muca, za hrbtom jim pa zaenkrat še samo prdi lev? Mislim, da zdaj vem. Ta gospoda bodo vendarle sluge pretorianski gardi, le redek bo samostojni kramar, ki bi tu videl izziv. In veste dolgotrajne študije pretoriancev ali kot se danes kličejo administracije in režije, so pokazale, da niso ne neumni, ne zlobni niti zlonamerni nič bolj kot ubogi zamorc...samo veliko več se praskajo po jajcih>:D
Ampak, če sem čisto iskren se mi vendarle zdi, da tokrat nekdo bo spoznal, da se bliža tank...in se ne bo drl: "ata spet eden s traktorjem čez našo njivo!">:D
In times of Universal Deceit, telling the truth
becomes revolutionary act. Orwell

Fave ::

Glejte. Ta forum je ena boljših zadev, kar se tiče slovenskega internetnega forumstva. Tema ZT pa to je (ali vsaj zelo blizu(no, kakor za koga)).

Thomas ima VELIKE zasluge, da je temu tako.

S to izjavo nisem nikogar postavil na stranski tir in vse, ki sodelujete na tem forumu cenim. Vsi imamo nekaj od tega.

Je pa škoda, da debata dobiva povišan glas. Neprijetno za branje.

Verjamem pa, da močni umi, kot ste nekateri tu, veste zakaj vztrajate pri svojem.

Thomas said (v drugih temah): Že stokrat sem rekel da sem Pro-Science in Treba se je klat z idejami... (nekaj v tem smislu).

IMHO, če si v nekaj 100% prepričan, ne boš poslušal drugega. Ampak te lahko to kasneje veliko stane, če se izkaže da nisi imel prav.

Sergio je par povstov nazaj lepo povedal. Misel je dobra. Držimo se je vsi.

Krasno je to, da se na tak način pegla in brainstorma nova zadeva. Zsluge kaj je od koga in kaj ne so itak vidne iz prispevkov, ki so datirani. Pa to tud sami že veste.

Nč ne rečem. Če se mnenja krešejo ni nič narobe. Ampak po moje nekdo nima prav.

Zdaj pa lahko vsak tumba svoje, ali pa (kot bi se v taki konstruktivni debati (in takem resnem forumu) pričakovalo), vsak navrže argumente zakaj to ni ok (ali vprašanja Thomasu (glede na to, da je on oče AS in te teme)).

In to bi se IMO dalo tud brez vmešavanja starih zamer iz drugeih tem / ega / ..., pa bi zdeva hitreje in mirneje tekla.

Za dobro vseh nas.
My mind's a hyper tool that fixes everything.

nevone ::

>IMHO, če si v nekaj 100% prepričan, ne boš poslušal drugega. Ampak te lahko to kasneje veliko stane, če se izkaže da nisi imel prav.

Bistvo napredka je, da nekdo nekaj 100% ve, in pri tem vztraja. Moraš vedeti, da Thomas je površen tip, ko gre za malenkosti, ampak osnove ima pa zelo dobro premišljene. Zato ne more dopustiti, da se ga vleče na stranski tir, samo zato, da se mu dokaže, da ga TUDI ON nekje biksa.

>Verjamem pa, da močni umi, kot ste nekateri tu, veste zakaj vztrajate pri svojem.

Ja vedo zakaj.

>Je pa škoda, da debata dobiva povišan glas. Neprijetno za branje.

Kaj je tako neprijetnega v tej temi za vas? Ta tema prinaša novo vrednost, vi se pa obešate na to, da pač avtor, in tisti, ki mu pomagamo, skušamo čim bolj razčistiti kaj je prednost AS, tudi kdo ali kaj je to prednost izumil/o. Zakaj to drugo ne bi smelo biti pomembno ne vem. Verjetno se moramo vsi stopiti v neko enovito formo in nihče ne sme izstopat.

Kar se pa tiče Sergiotovega izpostavljanja ega ... mislim, da ima on kar precej velikega (ego namreč ;)).

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

Thomas ::

Hvala vam za vse prijazne besede. Še bolj hvala za vse tehnične pripombe, tehtne ali ne. Je na en način čisto vseeno, pripomniti moraš kar misliš.

Hvala vam tudi za vse moralne korekcije, ampak to se me itak nič ne prime, tako da ta trud pa je zaman.

Meanwhile ... gremo novim digitalnim evoluiranjem nasproti. Todo lista je dolga.
Man muss immer generalisieren - Carl Jacobi

gzibret ::

Hmja, ena ideja.....

Obstajajo simulatorji nevronskih mrež (ANN), ki popolnoma naterenirano ANN izvozijo v C kodi (recimo dodatek za Mathlab). Bi bilo zanimivo to malo evoluirat. Itak z ANN lahko dobimo izredno dobre simulacije, če bi se še malo poevoluiralo, mi lahko morda šli še dlje?
Vse je za neki dobr!

Thomas ::

Verzija za optimiziranje dialekta C kode je na netu.

To je še ena uporaba Critticalla.

Samo ljudje v splošnem mislijo, da so sami pametnejši. Kar je sicer normalno, ampak ni več vedno res.

Fritz in Critticall sta pustila, vsak na svojem področju, ljudi zadaj. Eni drugi programi so jih sicer že prej, vendar vrhunski šah in vrhunsko izmišljevanje algoritmov se je zdelo dolgo nedosegljivo.

Je pa res, da Critticall rabi precej brihtno človeško bučo ob sebi, da ga pedena.
Man muss immer generalisieren - Carl Jacobi

Valentin ::

Zakaj pa je tu ArtificialSort počasnejši od QuickSorta ?


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