☰

» »

It means business

It means business

««
«
1 / 8
»»

Thomas ::

Link.

Zajemite sapo, sprobajte in skritizirajte, če mislite, da kaj ni prav.

Several Unique je dobil naslednika, ki povozi QS na celi črti, posebno pa še pri realnih nizih, ki niso čisto random. Vendar je hitrejši še celo tam.

Kar je pomembnejše od razbijanja "znanstvenega konsenza o superiornem QuickSortu", je dejstvo, da je algoritem najden s pomočjo, oziroma z izdatno pomočjo exomind. (Kakor imamo - ali bomo imeli - exoskeleton, že imamo tudi vsaj en exomind - Critticall. Neavtonomno AI, podaljšek našega uma, ki je vsaj toliko močno orodje, kot se vidi rezultatu tukajle.)

Please, do try it at home!
Man muss immer generalisieren - Carl Jacobi

gzibret ::

Odlično :)) Sicer se na genetske algoritme bolj slabo spoznam, ampak očitno je zadeva uporabna.

Koliko časa pa se ti je tole evoluiralo? In, ali si uporabil QS za seed?
Vse je za neki dobr!

Sergio ::

Ena vrstica mi ne da miru

if (right-left<11) {


Ta stvar dela enako dobro na vseh moznih velikostih arrayov?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

Ja. Dela za vse velikosti arrayev.

(Manjši od 11 ... zaenkrat. Bomo videli, kaj se bo naevoluiralo v naslenjih 24 urah ali več.)

"Manjši od 11" pomeni samo to, da segmente manjše od 11 - v arrayu velikem milijon ali kolikorkoli že - obravnava nekoliko drugače od drugih segmentov, ki nastajajo v procesu razvrščanja.
Man muss immer generalisieren - Carl Jacobi

_marko ::

Thomas:
Kaj je bistvena razlika med Several unique sort-om in tem, novim Artificial sort-om?

In še eno bolj splošno vprašanje:
Kaj to pomeni za prihodnost in kaj to dejansko pomeni kaj je Critticall nardil. Vidim, da se v temi v loži že sprašujejo o tem :8)

edit:typo
The saddest aspect of life right now is that science
gathers knowledge faster than society gathers wisdom.

Zgodovina sprememb…

  • spremenil: _marko ()

Thomas ::

> Koliko časa pa se ti je tole evoluiralo? In, ali si uporabil QS za seed?

Zadevi je bilo treba nekoliko pomagati. Ni se zvrtela povsem avtomatsko.

Seed so pa Several Unique, Quick in Bubble. Pomašinani v tole čudo.
Man muss immer generalisieren - Carl Jacobi

Sergio ::

OK, sem hotel primerjati. Pa Java ne zna goto.

Mas slucajno kaksno "precompiler" direktivo, ki bi naredila goto-less kodo? Samo vprasam.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

> Kaj je bistvena razlika med Several unique sorta in tega Artificial sorta?

Several Unique degenerira (ko ni več malo unikatnih rekordov) v Bubble. Artificial degenerira (ko je data random), v nekaj podobnega Quicku. (Jutri ali kaj takega bo še link na demonstracijo random date.)


QuickSort dela formalno, izbira pivot glede na velikost tabele, Artificial pa glede na vsebino tabele. Ne poskuša posortati urejenih segmentov, pač pa le neurejenim izračuna pivot z ozirom na mesto, kjer je urejenost porušena. Kjer je data neposortirana.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> goto-less kodo?

Bo tudi zevoluirana. One of these days.
Man muss immer generalisieren - Carl Jacobi

Sayer ::

Rezultati:

int NumberOfRec = 10000000;
RND function:
array[i] = Rnd(1,100000)-Rnd(1,100000);

VS 6.0 C++ compiler
-----------------------------------------------

AritificalSort - 1201ms
QuickSort (non recursive) - 2188ms
QuickSort (recursive) - 2484ms

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

Je treba se preveriti QuickSort z boljsimi pivotsi ...

Drugace cestitke :)

*edit popravljen rezultat za Aritifical - se vedno hitrejsi

LP

Zgodovina sprememb…

  • spremenil: Sayer ()

drejc ::

Bo tale ThomasSort poslan tut kej v znanstvene kotičke, al bo le podstran na critticall.com ostal?
"Rise above oneself and grasp the world"
- Archimedes of Syracuse

t909 ::

Thomas, kako naredis graficno ponazoritev?

matjash ::

čestitam thomas, na podlagi prvih rezultatov bi na oko ocenil da je tvoje razvrščanje hitrejše skoraj za 40%
... bolje pozno kot nikoli.

Zgodovina sprememb…

  • spremenil: matjash ()

Thomas ::

> Drugace cestitke :)

Hvala. Ampak koda je evoluirala tudi čez noč ... bo še večkrat poupdatana.

> Bo tale ThomasSort poslan tut kej v znanstvene kotičke

Bo poslan ...

> kako naredis graficno ponazoritev?

Jah, to so samo write v array. Taka je praksa teh ponazoritev. Samo da eni delajo v Java, tole je pa gif.

Bo pa mogoče še ena grafična ponazoritev, ki kaže vse.

> bi na oko ocenil da je tvoje razvrščanje hitrejše skoraj za 40%

Mislim, da v najslabšem primeru manj, v najboljšem pa še mnogo več.
Man muss immer generalisieren - Carl Jacobi

lymph ::

Kakšna je pa uporabna vrednost tega?

S čim bolj znanim bi se pa lahko tole primerjalo, ker nekak si ne znam predstavljat, kakšne vrste izboljšava je to - recimo da me zanima, na kaj vse lahko (potencialno) tole vpliva
"Belief is immune to counter example."

Thomas ::

Uporabna vrednost je ta, da se zdaj dajo pohitriti nekateri softwarei. Pač kjerkoli je primerno in možno, lahko ruknejo tole zadevo not. Ne zahtevam nobenih royalities za sam algoritem. Je public tudi kar se bo še znašlo na tisti podstrani.

Ne znam pa oceniti, kolikšna je "masa" vseh potencialnih in dejanskih časovnih izboljšav v bodoče, lahko je kar znatna. Sort je skrajno pomemben proces v "industriji bitnih stringov", skoraj nekaj takega, kot ogenj v kemični industriji. So to speak. Nekoliko boljše segrevanje kemikom ne bi škodilo, samo tega nimam, anede.

Je pa tukajle en algoritem, ki lahko pomaga bitsmithom v lovu na tisočinke in še manj sekund. Kar je precej pomembno, to vidimo vsak dan, posebej ko je teh tisočink milijone in več.

Pomen je pa še nekje drugje. Če je "crknil" sort, kjer naj bi bilo povedano že praktično vse, kar se povedati da, kaj z drugimi algoritmi? Verjetno da so prekomplicirani za človeka. Za človeka z exomind pa niso. To je pa buldožer s šoferjem, namesto kopača s krampom in lopato.

TO je glavni pomen.
Man muss immer generalisieren - Carl Jacobi

Sergio ::

Hehe, ravno zaradi tega me zanima, ce imas slucajno v pripravi kaksno goto-less varjanto te kode, ker bi delovanje rad sprobal v Javi.

Zakaj točno?

Zato:
Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.


Linque
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

Tkole mamo:

Several Unique* --> Quick Sort --> Bubble

Tkole zadeve degenerirajo v nekaterih primerih, kot kažejo puščice.

Kaj pa Artifical? Jah, temu sem razvijal (in razvil) "kapo" kakšen teden nazaj. Ta kapa prepreči QuckSort degradacijo, lahko celo koristi hitrosti na splošno ... vendar ma to še mau da se kuha. But it will come to the site, one nite!

No, ljudje so se precej ukvarjali s preprečevanjem degradacija Quicka, tole je pa njegovo (bistveno) izboljševanje. Antidegradacija Quicka je samo še en problem za Critticall.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Drugače rečeno. Je Artificial enako občutljiv na degradacijo kot Quick?

Je.

Obstaja za to zdravilo?

Ja, precej boljše, kot za QuickSorte. Pride zraven, ko podstran ne bo več underconstruction.html.
Man muss immer generalisieren - Carl Jacobi

WarpedGone ::

Kakšna je pa uporabna vrednost tega?


En konkreten primer so podatkovne baze. Ni uporabnega selecta, brez potrebe po sortiranju rezultatov. Res da so tle performanse ponavad IO-limited, ampak vsako milisekundo, ki jo pršparaš pri izvajanju selekta, lahk zato porabiš kje drugje. Vse se pozna.

A obstaja kje kak seznam takšnih *splošno uporabnih* osnovnih operacij / problemov, ki sestavljajo mnogo drugih postopkov?
Iskanje skupnih imenovalcev, ...?

BTW: kolk dalec smo od tega da bo Criticall evoluiral samga sebe?
Zbogom in hvala za vse ribe

Thomas ::

Delovanje programja bazira na nekaj working horse algoritmih. Sort je eden teh konjičkov, zelo razvpit. Dostikrat ravno s pomočjo sorta rešimo kakšen problem bistveno hitreje, kot brez njega. Dostikrat je sort še bolj esencialen. Zaradi narave digitalnega sveta je tudi precej potraten, kar se virov tiče.

Zato tudi že desetletja traja nora dirka, kako čimbolj pospešiti zadevo. Zgleda, da še nismo pri maximumu.

> kolk dalec smo od tega da bo Criticall evoluiral samga sebe?

Eno leto dva človeka dela.
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

tole je v biti en kombo sorting method?
potemtakem niti ni toliko revolucionaren ;)
Abnormal behavior of abnormal brain makes me normal...

Zgodovina sprememb…

  • spremenil: Vesoljc ()

Thomas ::

Dej proč kar je "kombo", pa boš videl.

Je revolucionaren. Vsaj za Quicka.

(Plus še ene 10 "kombo revolucij" zanj imamo v predalu.)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Torej, revolucija je ena večja, plus še ene par manjših.

V kolikor lahko bistveno izboljšavo kultnega algoritma lahko poimenujemo revolucija. :)

Če bi bil pa "samo kombo", bi bil pa tudi revolucija, če bi ugnal Quicka. Da ne bo dvoma.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Sam osnovni algoritem ArtificialSorta je podedovan od Several Unique. V nasprotju s Quick Sortom, pivot niti ni nujno, da obstaja. Pri QuickSortu mora, pri ArtificialSortu pa ... ga niti ni nujno v tabeli, ki jo sortamo. Zato v nasprotju s Quickom, ni nobenega umikanja (in potem vračanja) pivota, pač pa se le na levo in na desno steno nalagajo manjši oziroma večji kvečjemu enaki elementi meje. Na desno stran od zgoraj navzdol večji ali enaki meji, na spodnjo stran manjši od meje. Če niso že tam. Potem se pustijo pri miru, kakor pri Quicku (ali Bubbleu).

Določevanje meje je pri Artificialu kontekstualno. To pomeni, da najprej preverimo vsebino segmenta, če je sploh potrebna sorta in če je, se meja izračuna kot sredina med prvima elementoma, ki nista v pravem zaporedju.

Zdaj bi lahko klicali novo rundo tudi rekurzivno, ampak rekurzija zahtevnostno za computer ni ravno prijazna. Zato meje novih dveh segmentov napišemo na nek stack, da jih podvržemo isti obdelavi, če in dokler treba. Iterativno.

Pa sredina med JANKO in METKA? K. Pa med ABEL in ABECEDA? ABEH.

Kako da tega algoritma še ni nihče poštudiral? Ker ljudje nismo tako pametni, kot si domišljamo. Slab pregled imamo nad abstraktnimi stvarmi. Zato se lahko še marsikaj skriva našim očem, kar recimo Critticall (vse hitreje) vidi.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Iterativni verziji Quicka in Artificiala obe potrebujeta stack, kamor se odlaga informacija o segmentih, ki še potrebujejo obdelavo. Quick gre po vrsti tako, da najprej vedno obdela najmanjšo in zato ni veliko odprtih obdelovalnih površin. Nekako log2 od števila elementov. Stack Artificiala je precej večji (nekaj 1000 elementov stacka za nekaj 1000 odprtih obdelovalnih površin, pri nakaj milijonih elementov sortne tabele). Tudi gradnja tega stacka je bolj komplicirana.

Samo se splača. Nazadnje je manj metanja sem in tja, kar je poglavitno pri sortih.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Povedano najbolj preprosto in najbolj po domače.

Medtem ko je QuickSort obsojen na izčrpavanje vseh (sub)segmentov, ArtificialSort opazi, če je nek večji segment že posortan in se ne ukvarja več ne z njim, ne z njegovimi subsegmenti.

Artificial se inteligentno vpraša - pa je tukaj sploh še kaj početi? Kadar ni, kar je v realnosti pogosto, gre preprosto naprej, v nove delovne uspehe.

Quick pa diligentno spuca (ln2 krat!!) vse končke, tudi tiste, ki sploh niso "umazani". So že urejeni.

To je BISTVENA razlika med obema.
Man muss immer generalisieren - Carl Jacobi

Sayer ::

Testiral sem se z Introsort

ArtificalSort (ASort) se zmeraj hitrejsi ...

Rezultati za 15 000 000 int

5 rezultatov, zmeraj na novo zgenerirana stevila

ASort - 1828 ms
Introsort - 2000 ms

ASort - 1750 ms
Introsort - 1969 ms

ASort - 1860 ms
Introsort - 2000 ms

ASort - 1797 ms
Introsort - 1968 ms

ASort - 1812 ms
Introsort - 1969 ms

hja ... se bo treba sprijaznit.


LP


edit* dodal se en record

Zgodovina sprememb…

  • spremenil: Sayer ()

jernejl ::

Several Unique je dobil naslednika, ki povozi QS na celi črti, posebno pa še pri realnih nizih, ki niso čisto random. Vendar je hitrejši še celo tam.


Torej pri kakšnih nizih bi se naj pokazala prednost tega algoritma v primerjavi z ostalimi?
Morda sem zgornji stavek slabo razumel. Hitrejši še posebno pri realnih nizih, ki niso čisto random ? (zadnji stavek citata se mi namreč ne sklada povsem z njegovim predhodnikom).

In pa, kakšni so taki nizi, ki niso čisto random? Kako morajo torej biti porazdeljene vrednosti?

Namreč kolikor sem na hitro preizkusil algoritem (seveda v primerjavi z nekaterimi ostalimi), je v nekaterih primerih res hitrejši, v drugih pa tudi bistveno počasnejši. Tako da zaenkrat tistega "na celi črti" ne kupim.
Veselilo pa bi me, ko bi me lahko prepričal v nasprotno.


Vsak znani sortirni algoritem ima svoje prednosti in slabosti, saj danes (še) ne obstaja ultimativni algoritem. Zanimalo bi me zato tudi, v kakšnih aplikacijah bi bila možna uporaba točno tega algoritma?

Thomas ::

> Namreč kolikor sem na hitro preizkusil algoritem (seveda v primerjavi z nekaterimi ostalimi), je v nekaterih primerih res hitrejši, v drugih pa tudi bistveno počasnejši.

Kdaj? Povej primer.

> Vsak znani sortirni algoritem ima svoje prednosti in slabosti,

Jasno. Samo tale owna Quicka.
Man muss immer generalisieren - Carl Jacobi

SmeskoSnezak ::

Kakšna je časovna zahtevnost tega algoritma? Kako se obnese pri drevesih? A se lahko izrodi?
@ Pusti soncu v srce... @

Thomas ::

Časovna zahtevnost algoritma je logaritmična, tako kot pri Quicku, vendar je Artificial nekoliko hitrejši, ker "ne puca že (magari slučajno) popucanega". To mu da boost.

Izrodi se pa tako kot Quick, za obratno posortane nize.

Če nima kape, ki sem jo že bil omenil, seveda. Potem mu tudi to nič hudega ne more.
Man muss immer generalisieren - Carl Jacobi

WarpedGone ::

kakšno "kapo" maš v mislih?
Zbogom in hvala za vse ribe

Thomas ::

Čisto preprosto. Obrne, zarotira vse kontraposortane segmente.

Ali pa randomizira, kot to že delajo nekatere verzije Quicka, za svoje potrebe.

BUT!

Če jih obrne, to Artificial LAHKO obrne v svoj prid. Kako najbolje pa še ne vem, ker se še ni zevoluiralo do konca.

Mislim, v svoj prid tudi, če je bil input random!

Sicer mi pa ni do tega, da bi čisto vedno in povsod bil najhitrejši. Samo v ene 99,99% primerov.
Man muss immer generalisieren - Carl Jacobi

root987 ::

Glede na to da se je Artificial zevoluiral me zanima kje je meja tega samo-evoluiranja? Je ni? So to fizikalne/praktične omejitve v stilu da se časovno ne splača v neskončnost iskati naslednika ali kaj podobnega?
"Myths which are believed in tend to become true."
--- George Orwell

Tr0n ::

Radix sort ftw.

Thomas ::

Meja je fizika. Druga meja - nekoliko strožja - bi bila ekonomija. Ekonomija v najširšem pomenu besede. Dve znanosti, do katerih imam (poleg biologije) kaj spoštovanja.

Povsem ugibam. Sicer si domišljam, da je to educated guess, vendar je le guess. Ugibam torej, da optimalni sort vendarle ni tako daleč, da nam ne bi bil dostopen. Verjetno ga izračuna manj kot 10^18 ciklov Critticalla. Tako, da to ne bi bila predraga naloga.

Pravzaprav so optimalni sorti za do nekaj elementov že izračunani tukaj.

Milijon ali milijarda elementov ni tako daleč, prav gotovo pa je tudi kakšen vzorec.

Računam, da je optimalni sort 2-3 krat hitrejši od trenutnega rekorderja - Artificiala. Mislim tudi, da se ga da izračunati za manj kot za milijardo dolarjev virov.

Samo to je guess. Vseeno.

Mi je pa povsem vseeno, če izračunamo sort, ki ima le 99% performansa optimalnega. Približna rešitev bi čisto zadostovala.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> Radix sort ftw.

Radix NE deluje na floate. Radix zahteva 31 prehodov za posortanje niza {2000000000,0,1}.

Forget Radix, razen za specifične primere!

P.S.

A češ s Critticallom modificiran (hitrejši) Radix? ;)
Man muss immer generalisieren - Carl Jacobi

jernejl ::

Žal nisem dobil odgovora, pri kakšnih nizih (porazdelitev?, podatkovni tip?) bi naj bil tale algoritem boljši od ostalih.
Zato sem gledal bolj splošno.

Najprej naj opozorim, da algoritem zaenkrat ne deluje z vsemi vrednostmi, ki jih lahko spravimo v tip int.
Če polnimo polje z:
array[i] = rand()|(rand() << 16);
zadeva ne deluje. Verjamem pa, da boste to malenkost do končne verzije odpravili.

Prav tako algoritem ne deluje dobro pri padajočem zaporedju (OK, za to je avtor rekel, da bo poiskal rešitev).

Na kupu sem na hitro zbral nekaj različnih algoritmov in jih nekajkrat pognal.
Vsi algoritmi so pri polnjenju z
array[i] = rand()|(rand() << 16);
pravilno delovali (izvzemši tega artificial sorta).

Teste sem nekajkrat zagnal, a se mi ne da delati povprečij, ker so vrednosti vsakega zagona dokaj podobne (ni večjih

odstopanj), zato bom prilepil vrednosti za en zagon.

TEST: PADAJOČE ZAPOREDJE, VELIKOST POLJA=100000

QSort optimized Elapsed time = 828 ms
Optimized Median (Hybrid) QSort Elapsed time = 16 ms
Artificial Elapsed time = 10000 ms
Radix Sort Elapsed time = 0 ms
STD Sort Elapsed time = 0 ms
MergeSort Elapsed time = 0 ms
Another MergeSort Elapsed time = 16 ms
QSort Elapsed time = 15 ms


TEST: NARAŠČAJOČE ZAPOREDJE, VELIKOST POLJA=10000000

QSort optimized Elapsed time = 579 ms
Optimized Median (Hybrid) QSort Elapsed time = 296 ms
Artificial Elapsed time = 32 ms
Radix Sort Elapsed time = 1468 ms
STD Sort Elapsed time = 406 ms
MergeSort Elapsed time = 1125 ms
Another MergeSort Elapsed time = 1156 ms
QSort Elapsed time = 1547 ms


TEST: NAKLJUČNO ZAPOREDJE (ŠTEVILA IZ MNOŽICE {0..999}) (PONAVLJANJE!), VELIKOST POLJA=10000000

QSort optimized Elapsed time = 953 ms
Optimized Median (Hybrid) QSort Elapsed time = 844 ms
Artificial Elapsed time = 671 ms
Radix Sort Elapsed time = 516 ms
STD Sort Elapsed time = 953 ms
MergeSort Elapsed time = 1750 ms
Another MergeSort Elapsed time = 1641 ms
QSort Elapsed time = 1562 ms


TEST: NAKLJUČNO ZAPOREDJE (array[i] = Rnd(1,100000)-Rnd(1,100000)), VELIKOST POLJA=10000000

QSort optimized Elapsed time = 1266 ms
Optimized Median (Hybrid) QSort Elapsed time = 1172 ms
Artificial Elapsed time = 1093 ms
Radix Sort Elapsed time = 547 ms
STD Sort Elapsed time = 1219 ms
MergeSort Elapsed time = 1984 ms
Another MergeSort Elapsed time = 1969 ms
QSort Elapsed time = 2547 ms


TEST: NAKLJUČNO ZAPOREDJE (array[i] = rand();), VELIKOST POLJA=10000000

QSort optimized Elapsed time = 1156 ms
Optimized Median (Hybrid) QSort Elapsed time = 1063 ms
Artificial Elapsed time = 937 ms
Radix Sort Elapsed time = 531 ms
STD Sort Elapsed time = 1125 ms
MergeSort Elapsed time = 1937 ms
Another MergeSort Elapsed time = 1782 ms
QSort Elapsed time = 2218 ms


TEST: NAKLJUČNO ZAPOREDJE S TENDENCO PADANJA, VELIKOST POLJA=10000000

QSort optimized Elapsed time = 1406 ms
Optimized Median (Hybrid) QSort Elapsed time = 1063 ms
Artificial Elapsed time = 2234 ms
Radix Sort Elapsed time = 578 ms
STD Sort Elapsed time = 1156 ms
MergeSort Elapsed time = 1860 ms
Another MergeSort Elapsed time = 1734 ms
QSort Elapsed time = 2859 ms


TEST: NAKLJUČNO ZAPOREDJE S TENDENCO NARAŠČANJA, VELIKOST POLJA=10000000

QSort optimized Elapsed time = 1875 ms
Optimized Median (Hybrid) QSort Elapsed time = 1047 ms
Artificial Elapsed time = 3313 ms
Radix Sort Elapsed time = 578 ms
STD Sort Elapsed time = 1140 ms
MergeSort Elapsed time = 1875 ms
Another MergeSort Elapsed time = 1750 ms
QSort Elapsed time = 2813 ms


TEST: ODSEKOMA NARAŠČAJOČE ZAPOREDJE (ODSEKI DOLŽINE 1000 ELEMENTOV), VELIKOST POLJA=10000000

QSort optimized Elapsed time = 797 ms
Optimized Median (Hybrid) QSort Elapsed time = 687 ms
Artificial Elapsed time = 500 ms
Radix Sort Elapsed time = 516 ms
STD Sort Elapsed time = 781 ms
MergeSort Elapsed time = 1219 ms
Another MergeSort Elapsed time = 1188 ms
QSort Elapsed time = 1703 ms


TEST: ODSEKOMA PADAJOČE ZAPOREDJE (ODSEKI DOLŽINE 1000 ELEMENTOV) (NEGATIVNA ŠTEVILA!), VELIKOST POLJA=10000000

QSort optimized Elapsed time = 812 ms
Optimized Median (Hybrid) QSort Elapsed time = 735 ms
Artificial Elapsed time = 11234 ms
Radix Sort Elapsed time = 516 ms
STD Sort Elapsed time = 812 ms
MergeSort Elapsed time = 1609 ms
Another MergeSort Elapsed time = 1235 ms
QSort Elapsed time = 1765 ms

Zgodovina sprememb…

  • spremenil: jernejl ()

jernejl ::

Meja je vsekakor globalni optimum - optimalni algoritem urejanja.

Če ga bodo našli, je seveda vprašanje, saj je odvisno od tega, kakšne kriterije uporabljajo za ocenjevanje rešitev. Najbolj verjetno pa je, da sploh ne obstaja en algoritem, ki bi bil ultimativen - najhitrejši (in najmanj prostorsko potraten) v vsakem primeru.

Po moje je iskalni prostor malo prevelik, kvečjemu lahko najdejo kak lokalni optimum. Po mojem mnenju z genetskim programiranjem še nismo tako daleč, da bi se lahko ukvarjali s takimi zadevami.
Vsaj ne za resne namene.

Thomas ::

Hja, Artificial se ne obnese v nekaterih posebnih primerih padanja, ker nima kape. Vendar do konca tedna jo bo imel in bo tudi tam superioren vsem, razen neuniverzalnemu Radixu.


> Po mojem mnenju z genetskim programiranjem še nismo tako daleč, da bi se lahko ukvarjali s takimi zadevami.

Vi niste, mi smo.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

> array[i] = rand()|(rand() << 16); zadeva ne deluje.

To je stvar C++, ne algoritma. Irelevantno, ker do 31 bitov dela prav, do 32 pa ne. Zakaj? Zato ker se vsota dveh pozitivnih 32 bitnih števil pretvori v negativno število, ker so konstruktorji C++ kompajlerja tako hoteli. Irelevantno, vzemi 64 bitov (ali pa 37) pa bo prav sortalo tudi tvoj primer!

Radix NE šteje, ker ni univerzalen.

Obratno posortani segmenti so pač faktor degeneracije v kvadratno zahtevnost, to sem povedal že na začetku.

Pustimo distrakcije, čeprav teli z obratnim posortanjem bo ugodeno. For Artificial it's an asset not a liability!

Pustimo posebne primere in druge distrakcije ob strani.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

So pa vsekakor zanimive tele izjeme, ko Artificail ni najhitrejši. Evolucijske kanone usmerjamo v to smer.

Moram pa reči, da kakršenkoli algoritem za kompres podatkov imaš, VEDNO se bo neka data razširila, ne skrčila. S sortom je ISTO. Vedno obstaja neugodna data.

No, da bi pa spravili s poti nekatere možne in realne date, pri katerih je Artificial suboptimalen, je pa že na tričetrt narejeno. Be tuned for that!
Man muss immer generalisieren - Carl Jacobi

jernejl ::

To je stvar C++, ne algoritma. Irelevantno, ker do 31 bitov dela prav, do 32 pa ne. Zakaj? Zato ker se vsota dveh pozitivnih 32 bitnih števil pretvori v negativno število, ker so konstruktorji C++ kompajlerja tako hoteli. Irelevantno, vzemi 64 bitov (ali pa 37) pa bo prav sortalo tudi tvoj primer!


Poglej, tip int ima (vsaj na mojem računalniku in prevajalniku) 32 bitov. Vse, kar bi želel napraviti je, da sortirnemu algoritmu pošljem polje dolžine N (vsak zapis ima 32 bitov), ki mi jih naj uredi po velikosti. Noben element polja ne vsebuje več kakor dovoljenih 32 bitov, niti ne vsebuje nikakršnih neveljavnih vrednosti - samo 32 bitov (ničel in enic). Nikjer ne uporabljam nikakršnih vsot in me tudi ne zanima, kaj se kje pretvori v negativno in kaj ne. Gre samo za 32 bitov. Če je MSB 1 in operiraš s signed tipi, gre pač za negativno vrednost. Vseeno pa bi algoritem to moral znati urediti.
Ali pa želiš povedati da z določenimi veljavnimi vrednostmi tipa int, algoritem ne deluje tako, kot bi moral?


Radix NE šteje, ker ni univerzalen.

Je pa vseeno prilagodljiv in se ga da marsikje uspešno uporabiti, ne samo pri urejanju celih števil. Sicer pa obstajajo tudi druge variante, npr. bucket sort ipd.

So pa vsekakor zanimive tele izjeme, ko Artificail ni najhitrejši. Evolucijske kanone usmerjamo v to smer.

Teh izjem po mojem ni tako zelo malo. Če jih ocenitvena funkcija ne upošteva, jih bo z evolucijo težko odpraviti. Če bi želeli dobiti bolj splošni algoritem, bo treba napraviti tudi bolj kompleksno ocenitveno funkcijo.

Moram pa reči, da kakršenkoli algoritem za kompres podatkov imaš, VEDNO se bo neka data razširila, ne skrčila. S sortom je ISTO. Vedno obstaja neugodna data.

Torej bi lahko govorili o "no free lunch" teoremu v prostoru sortirnih algoritmov? :)

Thomas ::

Everything fixed. Bo online tonite.
Man muss immer generalisieren - Carl Jacobi

kopernik ::

Tip sorta je lahko zelo odvisen od a) tipa podatkov in b) okoliščin. Določeni sorti sploh ne znajo sortirati "in-place", kar je lahko huda omejitev. Quicksort (vsaj njegova najbolj znana implementacija) je dober ravno v takih primerih, ko se zahteva "in-place" sortiranje. V drugih primerih taka omejitev ni pomembna. Se pa da v mnogih primerih že shranjevati podatke na urejen način, tako da silnih sortov niti ne potrebuješ.

Zgolj en intermezzo, da ne bo vedno govora samo o temu qsortu kot o svetem gralu.

EDIT: Seveda moram pohvaliti thomasa in njegova prizadevanja na tem področju. Stvari so vsaj zame zelo zanimive.

Zgodovina sprememb…

  • spremenil: kopernik ()

Thomas ::

Online next step.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

_marko ::

"Yet, it's quite simple and well defined algorithm for a special niche." (SUS)

Kar mene zanima je, kdaj bo tole nehalo držati!? (glede "special niche" in bo postalo splošno uporabno)
The saddest aspect of life right now is that science
gathers knowledge faster than society gathers wisdom.

sverde21 ::

@Thomas: goto stavki so še zmeraj not :| , tak da portanje na Javo in podobno odpade zaenkrat.
<?php echo `w`; ?>

Thomas ::

Marko,

Artificial je splošen algoritem. Ni več nišni, tako kot je bil SUS. V 99+% primerov se Artificial odreže najbolje. Samo izšel je iz SUS, kar pa je pravzaprav vedno manj pomembno.

sverde,

Verzija brez goto bo.
Man muss immer generalisieren - Carl Jacobi
««
«
1 / 8
»»

Vredno ogleda ...

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

Quick sort

Oddelek: Programiranje		102515 (1263) drola
»

Digitalna evolucija (strani: 1 2 3 4 … 26 27 28 29 )

Oddelek: Znanost in tehnologija		141675764 (25933) pietro
»

dos C urejanje po velikosti

Oddelek: Programiranje		81206 (1037) klemen22
»

[Turbo Pascal] Pomoč...

Oddelek: Programiranje		131477 (1379) Grey
»

sortirni algoritem v Cju

Oddelek: Programiranje		61447 (1299) GaPe

Več podobnih tem