Warum ist die Laufzeit bei Bubblesort nicht gleich steigend?

[Dizzy_Ti]

Hi,
hier erstmal der Quellcode zum sortieren:

void sort()
{
T Temp; // Templete Variable
for (int i=0;i<this->maxposition;i++)
for (int o=i+1;o<this->maxposition;o++)
{
if(this->Inhalt[i]>this->Inhalt[o])
{
Temp=this->Inhalt[i];
this->Inhalt[i]=this->Inhalt[o];
this->Inhalt[o]=Temp;
}
}
}

Laufzeit:

Elemente Anzahl der Ms
900 16
1900 16
2900 63
3900 109
4900 156
5900 232
6900 328
7900 422
8900 515
9900 656

Warum verläuft der Algorithmus nicht linear(z.B bei 2900 die 63 ms und bei 5800 126 ms)?
Wie könnte man den Algorithmus weiter optimieren?

[i_hasser]

Erstmal musst du den Aufwand von deinem Alg bestimmen. Der ist:

for(i=1;i<=n;i++) O+=i

Naja gut, die mathematische Schreibweise ist da doch etwas eindeutiger (Summe i für i von 0 bis n).

Das kann man glücklicherweise auflösen zu

O= (n(n+1)) / 2

So, also sieht der Aufwand so aus:


O=
900 0.4M
1900 1.8M
2900 4.2M
3900 7.6M
4900 12.0M
5900 17.4M
6900 23.8M
7900 31.2M
8900 39.6M
9900 49.0M


So, und Zeit/O sieht dann ungefähr so aus:


O= t/O*1.0M*1.0k
900 0.4M 40
1900 1.8M 8.88
2900 4.2M 14.65
3900 7.6M 14.34
4900 12.0M 13
5900 17.4M 13.33
6900 23.8M 13.78
7900 31.2M 13.53
8900 39.6M 13.01
9900 49.0M 13.39



Du siehst also mit deinem Alg ist alles in Ordnung ;)
Für jedes O benötigt der ungefähr 13.5ns.

Die Zeit hängt natürlich auch davon ab wie oft umgestellt werden muss, und dafür lässt sich nur ein Worst Case Wert angeben.

[Sargnagel]

Wie intel_hasser schon schrieb, ist Bubblesort ein Algorithmus mit quadratischer Komplexität. Hier (http://www.soft.uni-linz.ac.at/Teaching/Begleitmaterial/Vorlesungen/_Algorithmen_und_Datenstrukturen_1/Folien%20zur%20Vorlesung/Algo-PI-VL-05.pdf) sind ein paar schöne Graphen zu den Laufzeiten von Algorithmen verschiedener Komplexität dargestellt. Nur bei wenigen zu sortierenden Zahlen ist Bubblesort noch recht fix, d.h. mit einem linearen Algorithmus vergleichbar. Sobald man es aber mit sehr vielen Zahlen zu tun haben, spürt man die hohe Komplexität von Bubblesort.
Man kann an dem Algorithmus kaum was verbessern. Folgende Version hatte ich mal spaßeshalber geschrieben:

#define COMP_SWAP(x,y) if(*x > *y) {int tmp = *x; *x = *y; *y = tmp;} x = y++;

void duffbubblesort(int array[], int length)
{
if(--length < 2)
return;
do
{
int *current = array;
int *next = array+1;
int n=(length+7)>>3;

switch(length&7)
{
case 0: do{ COMP_SWAP(current,next)
case 7: COMP_SWAP(current,next)
case 6: COMP_SWAP(current,next)
case 5: COMP_SWAP(current,next)
case 4: COMP_SWAP(current,next)
case 3: COMP_SWAP(current,next)
case 2: COMP_SWAP(current,next)
case 1: COMP_SWAP(current,next)
}while(--n);
}
}while(--length);
}

[i_hasser]

Na was sehen meine müden Augen denn da für ein erfrischendes Konstrukt *buck*

Duff ist eben allgegenwärtig ;)

EDIT: hmm.... ich überleg da gerade an einem Alg. Irgendwo bei O=n, vielleicht sogar genau O=n.

Hab aber dummerweise gerade keine Zeit wirklich weiterzuüberlegen :(

[Sargnagel]

Original geschrieben von intel_hasser
Na was sehen meine müden Augen denn da für ein erfrischendes Konstrukt *buck*

Duff ist eben allgegenwärtig ;)

Ich wußte doch, daß Dir das gefallen würde. ;D

Original geschrieben von intel_hasser
EDIT: hmm.... ich überleg da gerade an einem Alg. Irgendwo bei O=n, vielleicht sogar genau O=n.

Hab aber dummerweise gerade keine Zeit wirklich weiterzuüberlegen :(
Immer raus mit den Gedanken. In ca. einer Woche habe auch ich wieder Zeit, mich mit sowas zu beschäftigen ... hoffentlich.

[i_hasser]

Die Hälfte von meinem Alg hab ich leider wieder vergessen :]

Für Objekte mit sehr begrenzt vielen verschiedenen Zuständen ist ein O=n Alg aber einfach (zb. für einen 16bit Integer).

Wir nehmen einfach ein Array der Form "int a[65536];" und setzen alles auf 0. Dann gehen wir die Werteliste durch und erhöhen den dem Wert des Listeneintrags entsprechenden Indiz im Array um 1, also "a[liste[i]]++;".
Und dann gehen wir a von 0 bis 65536 durch und schreiben die Werte in eine neue Liste.

Aufwand: O=na+65536(b+c), a, b und c sind dabei irgendwelche konstanten Werte.

Jetzt müsste man es dynamisch implementieren, also die Reindizierung (mehr ist es ja nicht) auch für zb. floats umsetzen. Der Alg oben liefert für Listen aus 16bit Integern jedenfalls schonmal O=n ;D

[Sargnagel]

Original geschrieben von intel_hasser
Die Hälfte von meinem Alg hab ich leider wieder vergessen :]

Tja, man sollte immer mindestens Bleistift und Papier parat haben. ;D

Original geschrieben von intel_hasser

Für Objekte mit sehr begrenzt vielen verschiedenen Zuständen ist ein O=n Alg aber einfach (zb. für einen 16bit Integer).
[...]

Der Algorithmus nennt sich auch BucketSort (http://www.sortieralgorithmen.de/bucketsort/index.html). ;)

[i_hasser]

Wenn wir mit einem statischen Index zuviel Speicher verschwenden (zb. mit a[2^32]), warum gestallten wir den Index dann nicht einfach dynamisch? ;D

Dazu eine ordentliche Translation Table und der Aufwand zum Heraussuchen des richtigen Index beträgt ein bestimmtes Maximum.

Ich werd da einfach mal mit dem Implementieren anfangen ;)

[PuckPoltergeist]

Von welchen Speichergrößen sprichst du? Häufig lohnt ein free/delete nicht, der Speicher wird eh nicht frei gegeben.

[i_hasser]

Der Index wird bei bedarf erstellt und erreicht maximal die Größe der Liste (logisch, mehr kann man ja net indizieren ;)). Durch die Translation Table macht das nochmal ca. 10% mehr (weis ehrlich gesagt noch nicht wie groß ich die machen werde).

Maximal müssen also n Indexe neu allokiert werden (im gesamten Verlauf), was auch O=n bedeutet.

[PuckPoltergeist]

Noch was zur Laufzeit, IMO gibt es keine Sortieralgorithmen mit linearer Laufzeit. Das kleinste ist O(n*log(n)).

edit: Ok, ist falsch. Es gibt spezielle Algorithmen mit linearer Laufzeit.

[i_hasser]

Na der BucketSort ist linear, und dazu noch extrem einfach.
Dummerweise ist der Speicherbedarf eben ziemlich extrem, wenn es um größere Werte geht. Und IA32 setzt schon bei 32bit Integern den Riegel vor.

Allerdings könnte man hier extrem gut mit Paging arbeiten - man reserviert einfach die virtuellen 4GB (zb. in einem extra Segment... jaaaaa ich weis, Puck ;)) und allokiert nur da Pages wo auch wirklich Werte sind.

[PuckPoltergeist]

Original geschrieben von intel_hasser
Na der BucketSort ist linear, und dazu noch extrem einfach.
Dummerweise ist der Speicherbedarf eben ziemlich extrem, wenn es um größere Werte geht. Und IA32 setzt schon bei 32bit Integern den Riegel vor.

Nein, Bucketsort ist nicht linear. Die Komplexität beträgt n*log(n).



Allerdings könnte man hier extrem gut mit Paging arbeiten - man reserviert einfach die virtuellen 4GB (zb. in einem extra Segment... jaaaaa ich weis, Puck ;)) und allokiert nur da Pages wo auch wirklich Werte sind.

Du mischt hier schon wieder viel zu viel durcheinander. Paging und Segmentation ist Sache des OS. Da hat aber der Sortieralgorithmus nix verloren, schon gar nicht in der Speicherverwaltung.

[i_hasser]

Der Alg den ich oben vorgeschlagen hab für 16bit Ints ist in jedem Fall linear!

Damit kannst du Listen mit Millionen von Einträgen in linearer Zeit durchsortieren, ich schreib dir dazu auch gerne die Realisierung.


Nichtsdestotrotz könnte man meinen Alg oben auf einem IA32er auch für 32bit Integer realisieren. Klar, dass das nicht so ohne weiteres geht - aber so hast du lineare Ausführungszeiten.


E: So, die Initialisierung steht schonmal. Sind "nur" 75 Zeilen...

[i_hasser]

So, also der Alg nährt sich dem Ende.

Allerdings ist er (noch?) nicht O=n, zumindest nicht im worst case. Die Reihenfolge der Werte spielt dabei keine Rolle, sondern die Verteilung (eine absolut homogene Verteilung sorgt für O=n).

[PuckPoltergeist]

Original geschrieben von intel_hasser
So, also der Alg nährt sich dem Ende.

Allerdings ist er (noch?) nicht O=n, zumindest nicht im worst case. Die Reihenfolge der Werte spielt dabei keine Rolle, sondern die Verteilung (eine absolut homogene Verteilung sorgt für O=n).

Die Big-O Notation ist worst-case. Insofern ist das da oben also redundant. ;D

[i_hasser]

Möglicherweise bekomme ich den auch für den worst case auf O=n. Da brauchen wir nur ein paar Bäumchen.

Momentan ärgere ich mich noch mit einige Zeigern rum (und sowas lässt sich ja hervorragend debuggen :P).

Ich glaub das nächste mal verzichte ich auf das allerletzte bisschen Geschwindigkeit und nehme Vektoren.

[i_hasser]

So, also ich hätte es ja selbst nicht gedacht, aber der Alg scheint zu funktionieren *buck*

Die letzten 20 Minuten hab ich damit verbracht eine einzige Stelle zu debuggen, weil ich beim Copy'n Paste vergessen hab aus einer 0 eine 1 zu machen.

Die Zeiten können sich auf jeden Fall sehen lassen. Hab dazu mal einen n^2 Bubblesort geschrieben - für eine Liste mit 10'000 Integern braucht der 1.5s, mein neuer Alg wird mit 0.0s gemessen.

Bei 20'000 Zahlen braucht der Bubblesort schon 4.61 Sekunden, meiner wird mit 0.01s gemessen.

Die Ergebnisse hab ich natürlich verglichen, der Bubble Sort liefert die selben Resultate wie mein Alg. Gerade läuft 40'000 durch... 18.7s vs. 0.03s - kann sich doch sehen lassen ;D

Wie gesagt, bei einer homogenen Verteilung der Zufallszahlen (sprich das arithmetische Mittel aller Zahlen liegt im Schnitt bei maxZufallsZahl/2) ist O=n.

EDIT: Mir ist eben nochwas aufgefallen - für n(Listenlänge) -> 2^32 gilt auch O->n für den Worst Case (also bei 4 Milliarden Elementen in der Liste ist der Aufwand auch im Worst Case linear).

Und ein paar Zeiten will ich auch noch geben:


Listenlänge Zeit
160k 0.15s
320k 0.33s
640k 0.72s
1.28M 1.42s
2.56M 3.21s
5.12M 7.10s
10.2M 15.64s


Die schlechten Zeiten (nicht linear) kommen durch den (noch) relativ hohen Speicherbedarf. Bei 10 Millionen Einträgen hat er ca. 700MB Ram gefressen.

hmm... und irgendwo ist da ein BUG drinnen, so viel Speicher sollte er nicht fressen. Bei 10 Millionen sollten gerade mal ~80MB Speicher draufgehen.

[i_hasser]

Also ich hab aus Spaß mal meinen HP 49g+ an den Ergebnissen hacken lassen - danach beträgt der Aufwand O=n^1.1

Mir ist aber auch noch eine gute Optimierungsmöglichkeit für weniger homogene Verteilungen eingefallen - braucht glücklicherweise auch nur linearen Aufwand (das ist das Schöne, solange der Aufwand linear bleibt können wir die komplexesten Berechnungen anstellen ;D).

Das Prinzip hinter der Optimierung schreit regelrecht nach einer noch stärkeren Anwendung, aber ich will das alles erstmal mit vektoren realisieren bevor ich da irgendwas großartig abändere.
Der Code sieht ziemlich übel aus, und so eine verkettete Liste hat man ja schnell durch einen Code-Fehler kaputtgespielt ;)

[DarkAvenger]

Sortierverfahren, die auf paarweisen Schlüsselvergleichen beruhen *können* nicht schneller als n*log(n) sein. (Schreibweise \Omega(n*log(n))) Das ist theoretisch bewiesen worden. Damit ist mergesort optimal, wenn auch der Speicherverbrauch 2*n beträgt. Es gibt auch eine schöne parallele Variante von mergesort: pipelined mergesort, die auf n CPUs in Zeit log(n) sortiert, also der Aufwand gleich bleibt.

Bei allen linearen Vf oder ähnl, muß der Wertebereich explizit vor der Sortierung bekannt sein. (Bucketsort, Radixsort)

Wer jertzt denkt, daß der einfach einmal die Liste durchgeht und min und max bestimmt und dann einen lin Alg losläßt der hat sich i.a. geschnitten, wenn min und max seeeeehr groß resp klein sind, also max>>min (das ist nicht der bit shifter...).

[i_hasser]

Also eine min/max Bestimmung braucht immer nur O=n - wir setzen min und max auf den 1. Wert und gehen dann einmal linear die Liste durch und aktualisieren min/max.

Übrigens hab ich meinen Alg mit dem C Zufallsgenerator ausprobiert - der spuckt Zahlen im Bereich 0 bis 2^31 aus, also max-min beträgt auch 2^31 - groß genug? ;)

Mir ist eine Bereichsoptimierung eingefallen, mit deren Hilfe man das deutlich schneller bekommt bei nicht homogenen Verteilungen, wie gesagt will ich das aber erstmal nach C++ portieren (Vektoren werd ich mir aber sparen (müssen), weil die beim Einsetzen neuer Werte zu langsam sein dürften - ein Vektor ist ja linear indiziert).

Ach ja, nochwas - der Speicherverbrauch von meinem Alg ist ziemlich hoch. Müsste bei (sizeof(T)+4*4)*n liegen (bei n Elementen der Klasse T). Also bei 10 Millionen Integern macht das schon 200MB Speicher. Dafür ist es verdammt schnell ;D

Wenn ich meinem HP 49g+ noch die 0:0 gebe (ist ja logisch, für nix braucht er nix ;)) spuckt der mir übrigens eine lineare Gleichung aus :)

[Devastators]

Original geschrieben von Dizzy_Ti
Hi,

Wie könnte man den Algorithmus weiter optimieren?


der bubble Sort ist so mit der einfachste und auch ziemlich langsamste Sortieralgorithmus den es gibt. Laufzeit ist halt n² wie schon beschrieben.

optimierungen gibt es, ändern aber faktisch nichts an der Laufzeit:

Du könntest das Feld "gleichzeitig" von vorne und von hinten durchlaufen und Sortieren. (optimierter BubbleSort)
als weiter optimierung kannst Du in den Schleifen jeweils ein Abbruchflag setzen. Es kann ja sein, dass das Feld bereits sortiert ist... dann müssen die Schleifen nicht weiter durchlaufen.


Mehr Verbesserungen fallen mir nicht ein. "Knackig" und schön finde ich den (rekursiven) QuickSort oder den aufwändigen HeapSort. (beide O = n*log(n))

[i_hasser]

Original geschrieben von Devastators
"Knackig" und schön finde ich den (rekursiven) QuickSort oder den aufwändigen HeapSort.

Schade... knackig ist meiner bestimmt nicht *buck* (zumindest nicht in der C-Version - ich schreib gerade an C++). Aber das wird vielleicht auch - ich find den Alg elegant ;)

[DarkAvenger]

Es mag zwar sein, daß du im average case nahe der linearen Laufzeit kommst, aber im *worst case*, ist das unmöglich bei Vf, die nur Schlüssel *vergleichen* (bubblesort, quicksort, mergesort etc) und nicht den Schlüsselwetr als solches benutzen. Dein Vf ist eher Radix/Bucketsort gleichzusetzen, wobei du die Effizinz offensichtlich gesteigert hast. 2^31 ist vom theor. Betrachtucngsweise uninteressant. Probier es mal mit 2^128 oder mehr...(eiegntlich auch uninteressant, aber naja ;))


Quciksort ist O(n^2), average case ist O(n*logn). Heapsort ist O(n*log n), aber ia komplexer als Mergesort, dafür läßt sich heapsort in-situ realisiseren, also braucht nur n und nciht 2*n SPeicherplatz.

[i_hasser]

Original geschrieben von DarkAvenger
Es mag zwar sein, daß du im average case nahe der linearen Laufzeit kommst, aber im *worst case*, ist das unmöglich bei Vf, die nur Schlüssel *vergleichen* (bubblesort, quicksort, mergesort etc).

Du kennst meinen Alg doch garnicht ;). Und der Sort Alg den ich oben schonmal angesprochen hab (Zählarray[max-min]) ist definitiv immer linear! Dummerweise frisst der extremst viel Speicher.

Bei einer homogenen Verteilung (lass dir das mal auf der Zunge zergehen ;) - im Gegensatz zu anderen Algs können die Werte wild durcheinander stehen, hauptsache es gibt von allen ungefähr gleich viele, also nicht sowas wie 10mal 1 und 1mal 10) ist O=n und bei der worst case Verteilung ist O noch n^2 - noch.
Mir ist nämlich eine super Methode eingefallen, wodurch die Verteilung nur in sehr kleinen Intervallen homogen sein muss (also zb. 100mal 2, 100mal 3, 10mal 5, 10mal 6, 123456mal 1001 und 123456mal 1003) und trotzdem schon O=n gilt (denkbare Intervallgrößen wären (max-min)/100, es ist aber auch kein Problem die Intervallgrößen dynamisch der Verteilung anzupassen (das werd ich später auch implementieren))).

Wo ich die ganze Zeit am Überlegen bin ist, ob man diese Optimierung nicht sogar komplett dynamisch gestallten kann, so dass es nur noch einige ganz ganz ganz wenige Fälle gibt in denen O>n ist.
Und der praktische Nutzen wäre enorm.


Hat zufällig jemand die Sortierzeiten der O=n*log(n) Algs da? Würd gern mal vergleichen, meinen popeligen BubbleSort steck ich ja schon locker in die Tasche (und wegen einiger Optimierungen (da fällt mir ein, dass ich bisher immer nur Debug Code genommen hab) arbeitet mein Alg momentan sowieso erst ab einer Listenlänge >320k Einträge, da macht der Bubble Sort schon viel früher schlapp).

[DarkAvenger]

Du kennst meinen Alg doch garnicht . Und der Sort Alg den ich oben schonmal angesprochen hab (Zählarray[max-min]) ist definitiv immer linear! Dummerweise frisst der extremst viel Speicher.



Das brauche ich auch gar nicht. :) Das ist das schöne an Mathematik: Was algemein bewiesen wurde, läßt sich nciht umschiffen. Bei Physik ginge das noch (etwa mit "schneller als c").


Das du extrem viel Speicher brauchst ist auch klar.

Ich frage mal anders: Kannst du floats sortieren?

Integer allein sind langweilig. Wie gesgat, du bastelst einen Alg, der die *Information* der Schlüssel benutzt. Da schafft man es gegen O(n) zu kommen. Aber Vf, die nur die *Ordnungsrelation* ausnutzen, können nimmer unter O(n*log(n)), denn die Schranke \Omega(n*log(n)) ist "scharf".

Ich hätte eine mergesort Implementation, aber das kann du sicher auch ohne Probs in 10 min selbst (und mit perverseren Optimierungen als ich ;)).

[DarkAvenger]

Evtl solltest du dir hashing angucken. Ich denke, das könnte dir helfen.

[i_hasser]

Das tolle an dem Alg ist, dass wir praktisch keine Werte vergleichen müssen ;). Das mag zwar stimmen (dass man bei vergleichend sortierenden Algs nicht unter O=n*log(n) kommen kann), aber genau desswegen vergleichen wir auch nicht ;).

Und ja - ich kann floats sortieren. Der Alg kann jede skalare Größe sortieren, bzw. alles, was man auf eine skalare Größe reduzieren kann.

Wenn die C++ Implementierung steht werd ich den Alg mal posten, allerdings dann unter meinem Copyright ;D ;)

EDIT: Bei Integer-Werten sieht die Geschichte mit dem Worst Case doch wesentlich besser aus - wenn es da im besten Fall O=n ist, ist es im schlechtesten Fall O=(max-min)/m*n, wobei m eine Konstante ist.

[i_hasser]

Ha, Rechnung ohne die C++ OO Verwaltung gemacht. Hab für so einiges Klassen genommen, und die sind extremst langsam.
Darf das jetzt zu structs umändern :(

[DarkAvenger]

Naja, nur ich glaube trotz alle dem, daß wenn ich eine Werteliste habe, die etwa 512MB verschlingt, daß diese mit heapsort oder mergesort immer noch schneller sortiert wird, als mit deinem Alg, weil dir der Speicher ausgeht oder gar der swap space. :D

Implementier mal wirklich den mergesort und vergleiche die Laufzeit, insbesondere für große Listen.

Ein Informatiker würde sagen, dein Alg hat exponentielle Laufzeit, weil der von O(max) abhängt, denn man würde in diesem Fall nach Binärstellen gehen. Dagegen juckt merge/heapsort die Größe der Zahl nicht wirklich, solange < bzw > nicht von der Zahlengröße abhängt.

[i_hasser]

Die größe der Zahl juckt meinen Alg prinzipiell auch nicht ;)

EDIT Nein, es war ein Fehler im Alg. C++ hat damit nix zu tun und ist hier genauso schnell wie C.

Dabei ist das worst-case Szenario für den 1. Alg eingetreten (allerdings hab ich damit auch die Bereichserkennung ausgehebelt) - anstatt der Zufallszahlen hab ich ihn die Zahlen von 0 bis Listenlänge sortieren lassen.


Der Alg ist sogar schneller als meine ursprüngliche C Implementierung und braucht noch weniger Speicher. 1.5 Sekunden für 1.6M und dabei braucht er 20MB Speicher (die Liste selbst belegt aber auch schon ~6MB Speicher, also es läuft auf 10/3*n hinaus).

Eine besondere Eigenschaft von dem Alg ist übrigens, dass man auch im Nachhinein noch Werte in die Liste eintragen kann - ohne großen Aufwand. Also ich kann in die Sortierte Liste zb. noch eine 5 einsortieren lassen.

[DarkAvenger]

Ja ja, max-min, nur könnte das im Zweifelsfall seeehr groß werden.

[i_hasser]

Ich hab doch schon geschrieben, dass max-min 2^31 ist (ja, bei der Liste wo der Alg normal schnell läuft). Größer geht es bei 32bit Integern garnicht.

In diesem Bereich sind die Zahlen homogen verteilt. Wenn ich allerdings die Zählervariable sortieren lasse sind die Zahlen in diesem Bereich absolut nicht homogen verteilt, desswegen war der Alg auch so lahm.

Mit der Optimierung die ich noch reinsetzen will ist sowas aber auch kein Problem mehr, dann müssen eben nur noch sehr kleine Bereiche homogen sein - aber das hatte ich eben noch nicht implementiert ;).

[DarkAvenger]

2^31 ist doch 2GB, wenn ich mich nciht irre? Wie groß ist denn m etwa? Iuch galueb da würde sich ein P4 EE gut machen, wenn man soviel im SPeicher rumschieben muß. ;D

[i_hasser]

Wieviele Werte es sind hab ich ja immer angegeben (zb. 1.6 Millionen). Die verteilen sich dann gleichmäßig im Bereich 0..2^31. m hab ich einfach mal auf Listenlänge/10 gesetzt, damit würde der max. Aufwand bei 32bit Integern O=2^32/ (n/10) * n betragen, also 2^32*10 ~ 2^(35.4).

Die Anzahl spielt dabei keine Rolle mehr. Allerdings dürfte es eine Ewigkeit dauern, bis man den Aufwand mit einem quadratischen Alg erreicht und höhere m produzieren an einer anderen Stelle einen linear steigenden Aufwand (also unendliche Listen brauchen trotzdem unendliche Zeiten).

[i_hasser]

So, jetzt gibts erstmal die Hintergründe zum Alg selbst. Die Optimierung hab ich noch nicht fertig implementiert, aber hab jetzt auch erstmal keine Lust.

Und wie gesagt, momentan ist der Alg noch (c) by me ;) (muss mich mal umschauen, vielleicht könnte man da sogar was drauf anmelden? ;D).

Ausgang ist der BucketSort - also wir haben ein array[max-min] und zählen da wie häufig irgendwas vorkam.
Von der Sache her ist der Alg ja schon ideal, da O=n. Bei großen Bereichen (max-min ist ziemlich groß) frisst der allerdings zuviel Speicher, und bei zb. Floats kann man ihn garnicht (bzw. nicht wirklich) einsetzen.

Wenn wir den Alg aber auf einen 2^31 Bereich anwenden fällt eins ziemlich schnell auf - extrem viele Arrayelemente sind 0, selbst wenn wir eine Liste der Länge 2^32 haben ist im Schnitt jeder Eintrag gerade mal auf 2.

Schön wäre es jetzt also, wenn wir uns die Indizies die 0 sind sparen könnten. Damit hätten wir nur noch ein Array[Listenlänge] oder noch kleiner.

Das Problem ist dann aber, dass wir nicht mehr sagen können array[xyz] korrespondiert zur Zahl abc - logisch, weil sich das Array ja dynamisch ändert (wenn wir das als verkettete Liste nehmen und während der Laufzeit Indizies für neue Zahlen einfügen).

Ziel müsste es jetzt also sein, dynamisch neue Indizies einfügen zu können aber trotzdem sagen zu können Index xyz korrespondiert zu Zahl abc - bzw. umgekehrt Zahl abc (über die wir in der Liste stolpern könnten) korrespondiert zu Index xyz (und entsprechend würden wir den Array Eintrag für xyz um 1 erhöhen und uns der nächsten Zahl in der Liste zuwenden).

... es würde ja aber eigentlich auch ausreichen, wenn wir wissen abc korrespondiert ungefähr zu Index xyz.

Die Abweichung müsste dabei von der Listenlänge abhängen (für n++ wird die Abweichung kleiner), dann wäre O trotzdem linear.

Tja, und wie schaffen wir das? Wir kombinieren einfach was wir brauchen - ein statisches Array um abc auf xyz umrechnen zu können und eine dynamische Liste um bei Bedarf neue Indizies einfügen zu können ;D.

Erstmal zu der verketteten Liste. Wir fangen nicht mit einer leeren Liste an, sondern legen einige Einträge schon fest - zb. Listenlänge/10.

Der Eintrag speichert nebst den Nachbarn zu welchem Index er Daten speichert (also zu welchem xyz) und die Daten selbst (also array[xyz] bzw. wie oft die zu xyz korrespondierende Zahl schon aufgetreten ist).

Initialisieren tun wir die Einträge linear aufsteigend - also Eintrag 1 -> Index ist 1 / (listenlänge/10), Eintrag 2 -> Index ist 2 / (listenlänge/10) usw.

Dann bilden wir die Liste in ein statisches Array ab. Das statische Array enthält also nur Zeiger auf die Listenelemente und nicht die Elemente selbst. Da wir die Liste linear durchinitialisiert haben wissen wir sarray (statisches Array) [1] korrespondiert zu Index 1 (bzw. dem Listenelement dazu), sarray[2] korrespondiert zu Index 2 usw.

Jetzt können wir in die verkettete Liste dynamisch noch weitere Elemente einfügen (so, dass Index immer aufsteigend bleibt) und sarray[x] wird immer auf den Eintrag korrespondierend zum Index x zeigen.

Praktisch sieht das so aus: In der Liste sind wir über den Wert w gestollpert. Also suchen wir uns den nächstgelegenen Eintrag im statischen Array aus, nämlich sarray[ (w-min)/(max-min)*(listenlänge/10) ]. Dadurch landen wir in der verketteten Liste schonmal ganz in der Nähe vom Index w. Die Liste gehen wir jetzt solange durch, bis Eintrag(x)->Index <w und Eintrag(x+1)->Index >w - dazwischen fügen wir ein neues Element ein mit Index=w und setzen die Anzahl auf 1.

Das wars - und auf zum nächsten Listeneintrag.
Der Aufwand vom sarray Eintrag zum letztendlich richtigen Eintrag in der verketteten Liste steigt zwar langsam an, aber da die Größe von sarray mit listenlänge/10 definiert wurde müssen wir bei einer absolut homogenen Verteilung nie mehr als 10 neue Einträge zwischen den beiden Einträgen 2er benachbarter sarray Einträge anlegen - ergo bleibt der Aufwand zum Raussuchen der Einträge in der verketteten Liste immer <=10, unabhängig von der Anzahl der zu sortierenden Elemente -> der Alg ist linear.

Haben wir Pech liegen alle Einträge zwischen dem selben korrespondierenden Einträgen 2er benachbarter sarray Einträge und die Suchzeit dazwischen schwankt zwischen 0 und n -> der Alg ist quadratisch.
Aber dafür hab ich auch ne Lösung, die ich aber noch nicht verrate ;D

[PuckPoltergeist]

Original geschrieben von intel_hasser
Ausgang ist der BucketSort - also wir haben ein array[max-min] und zählen da wie häufig irgendwas vorkam.
Von der Sache her ist der Alg ja schon ideal, da O=n. Bei großen Bereichen (max-min ist ziemlich groß) frisst der allerdings zuviel Speicher, und bei zb. Floats kann man ihn garnicht (bzw. nicht wirklich) einsetzen.

Ich habe Bucketsort jetzt nicht im Kopf, aber ich werde dir dieses Wochenende noch zeigen, dass dieser Algorithmus nur unter ganz bestimmten Bedingungen lineare Komplexität hat (sofern das nicht jemand anderes tut). Entweder nutzt du nicht Bucketsort, oder du vereinfachst bei deiner Implementierung etwas sehr stark.

[i_hasser]

Ja, also ich meine damit den Alg den ich oben angesprochen hab. array[max-min] und dann für eine liste von Zahlen array[liste[i]]++; für i von 0 bis listenende.

Der ist definitiv linear aber praktisch fast immer untauglich *buck*

[DarkAvenger]

Ok, hier ein Zeiten vergleich. Ich habe mal eine template mergesort Klasse gebastelt und Zeiten genommen. Es handelt sich um ein unoptimiertes DEBUG build. Ich denke auch so sind die Ergebnisse schon vielsagen. Man beachte das k hinter den Zahlen. Dh. 1k =1024, etc...

n ist die Listenlänge, habe hier mit ints getestet und für jedes n jeweils 10 Durchgänge gemacht, bei denen die Listenwerte zufällig (mit sqrt(rand())*sqrt(RAND_MAX); damit ich bei floats auch Nachkommastellen habe... ) generiert wurden.


n = 1k average time: 0.0001462
n = 2k average time: 0.0003165
n = 4k average time: 0.0007789
n = 8k average time: 0.0015685
n = 16k average time: 0.0033645
n = 32k average time: 0.0069919
n = 64k average time: 0.0154623
n = 128k average time: 0.0329185
n = 256k average time: 0.0685915
n = 512k average time: 0.144551
n = 1024k average time: 0.300577
n = 2048k average time: 0.627323
n = 4096k average time: 1.30669
n = 8192k average time: 2.7166
n = 16384k average time: 5.65002


Wie lange braucht dein ALg bei 16*sizeof(type) MB an Daten? :)

Hier mein Hauptprogramm (EDIT s.u.)

Die check Routine ist nur dafür da, damit ich weiß, ob ich Mist gemacht habe beim SOrtieren...

[PuckPoltergeist]

DarkAvenger:

Rückst du auch noch den Code von MergeSort raus? :]

[DarkAvenger]

Naja, eigentlich ist es primitv, aber bitte, hier der ganze source minus häßlichen debug stuff ;):


/***************************************************************************
* Copyright (C) 2004 by Dark Avenger *
* darkav *at* gmx *dot* net *
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License for more details. *
* *
* You should have received a copy of the GNU General Public License *
* along with this program; if not, write to the *
* Free Software Foundation, Inc., *
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
***************************************************************************/


#include <iostream>
#include <cstdlib>
#include <cmath>

#include <mpi.h>

using namespace std;

template <class T> class MergeSort {
public :
MergeSort(long n);
~MergeSort();

void sort();

void generate();
void check();

private:
void merge(long na,T *a, long nb, T *b, T *c);

T *list[2];
long n;
unsigned char swap;

};

template <class T> MergeSort<T>::MergeSort(long n)
{
this->n=n;
list[0]=new T[n];
list[1]=new T[n];
swap=0;

srand ( time(NULL) );
}

template <class T> MergeSort<T>::~MergeSort()
{
delete[] list[0];
delete[] list[1];
}

template <class T> void MergeSort<T>::generate()
{
for (long i=0;i<n;++i) list[swap][i]=(T)(sqrt((double)rand())*sqrt(RAND_MAX));
}

template <class T> void MergeSort<T>::check()
{
for (long i=1;i<n;++i) if (list[swap][i]<list[swap][i-1]) cout<<"check failed!\n";
}


template <class T> void MergeSort<T>::merge(long na,T *a, long nb, T *b, T *c)
{
long i,ia,ib,nt;

nt=na+nb;
ia=0;
ib=0;

for (i=0;i<nt;i++) {
if (ia<na) {
if (ib<nb) {
if(a[ia]<b[ib]) c[i]=a[ia++];
else c[i]=b[ib++];
} else //b ended
for (;i<nt;i++) c[i]=a[ia++];
} else //a ended
for (;i<nt;i++) c[i]=b[ib++];
}
}

template <class T> void MergeSort<T>::sort()
{
long na,ns;
for (na=1;na<n;na*=2) {
for (ns=0;ns+2*na<n;ns+=2*na) merge (na,list[swap]+ns,na,list[swap]+na+ns,list[1-swap]+ns);
merge (na,list[swap]+ns,n-ns-na,list[swap]+na+ns,list[1-swap]+ns);

swap=1-swap;
}

}


int main(int argc, char *argv[])
{
MPI_Init(&argc,&argv);

double time, totime;


MergeSort<int> *ms;
long j;
for (long i=1024;i<(1<<25);i<<=1) {

ms=new MergeSort<int>(i);
totime=0;

for (j=0;j<10;++j) {
ms->generate();
time=MPI_Wtime();
ms->sort();
totime+=(MPI_Wtime()-time);

ms->check();
}

cout<<"n = "<<(i>>10)<<"k average time: "<<totime/j<<endl;
delete ms;
}
MPI_Finalize();
return EXIT_SUCCESS;
}

[DarkAvenger]

Naja, irgendwie schienen ein paar EInrückungen hier drauf gegangen zu sein, aber naja...[later] Ok nun ist's besser.

[PuckPoltergeist]

Vielleicht stehe ich jetzt wirklich total auf dem Schlauch, aber wie kannst du damit Fließkommazahlen sortieren? Long ist doch ein integer-Wert.

[DarkAvenger]

Guck mal in die merge Prozedur. Da werden a und b verglichen, die aber vom template Typ T sind. Die longs werden nur zur Indizierung benutzt.

Anmerkung: So wie ich ihn implementiert habe, geht der auch für n!=2^k, mit k natürlich...also sollte der allgemein verwendbar sein.

[Dizzy_Ti]

Hi,
da ich mal den Speeduntschied vom Bubblesort auf unterschiedlichen Compiler testen wollte, habe ich den Dev-C++ installiert.Mein Problem ist, das ich mit Borland c++ Builder bequem mit AnsiStrings, die Methode ToInt() und ToDouble() habe und damit int und double Werte in AnsiStrings speichern konnte um z.B die gebrauchte Zeit auszugeben in einer MessageBox und mit Dev-C++ habe ich diese Methoden nicht.Mit

double zeit1=GetTickCount();
// mach irgendwas
double zeit2=GetTickCount();
zeit2=zeit2-zeit1;
string ausgabe=string(zeit2);

hat es nicht funktioniert.
Wie mach man das richtig?

[i_hasser]

Dev-C++ ist GNU Kompatibel, und unter UNIX (bei GNU funktioniert die Zeitmessung wie in UNIX) funktioniert die Zeitmessung etwas anders.


#include <time.h>

clock_t t1,t2;

t1=clock();
// Tu was
t2=clock();

cout << (float)(t2-t1)/CLOCKS_PER_SEC;


Damit bekommst du bei Linux eine Auflösung von 1MHz, bei Windows afair 1KHz. Es gibt aber noch einen uclock Counter, der sehr viel genauer ist.

[Dizzy_Ti]

Ich mess die Zeit jetzt wie du es gesagt hast, aber ich kann das Ergebniss
der Messung immer noch nicht in einem String speichern.

float time=((float)(t2-t1)/CLOCKS_PER_SEC);
string s="";
s=string(time);

Fehlermeldung:
no matching function for call to `std::basic_string<char,

[i_hasser]

Weis ich jetzt auch net. Vielleicht mit einem cast.

Irgendwas läuft in meinem Alg nicht linear, anders lassen sich die überproportional anteigenden Zeiten nicht erklären.

[i_hasser]

Ich glaub ich hab den Grund gefunden. Dürfte eine Weile dauern das wegzuoptimieren...

[PuckPoltergeist]

Original geschrieben von Dizzy_Ti
Ich mess die Zeit jetzt wie du es gesagt hast, aber ich kann das Ergebniss
der Messung immer noch nicht in einem String speichern.

float time=((float)(t2-t1)/CLOCKS_PER_SEC);
string s="";
s=string(time);

Fehlermeldung:
no matching function for call to `std::basic_string<char,

Weil String keine Konvertierung von int oder float kennt. Da musst du über c-strings (also char-arrays) gehen.

[i_hasser]

Da gibts sicher irgend eine fertige Funktion (notfalls sprintf), sonst wären zb. die C-locales sinnlos.

Nur hab ich sowas bisher noch nie gebraucht.

[DarkAvenger]

So, habe mal einen optimierten compile (-march=athlon-xp -mtune=athlon-xp -O3 -ftracer -pipe -fno-web -fno-inline-functions -fomit-frame-pointer) gemacht und gemessen (Athlon XP @2.2GHZ, nforce2 1GB DDR-400 DC)


n = 1k average time: 0.0001036
n = 2k average time: 0.0002172
n = 4k average time: 0.0004756
n = 8k average time: 0.0012509
n = 16k average time: 0.0024537
n = 32k average time: 0.0049901
n = 64k average time: 0.0108535
n = 128k average time: 0.0227171
n = 256k average time: 0.0481879
n = 512k average time: 0.100816
n = 1024k average time: 0.207976
n = 2048k average time: 0.460807
n = 4096k average time: 0.990255
n = 8192k average time: 1.87691
n = 16384k average time: 3.89166

[PuckPoltergeist]

Original geschrieben von Dizzy_Ti
Hi,
da ich mal den Speeduntschied vom Bubblesort auf unterschiedlichen Compiler testen wollte, habe ich den Dev-C++ installiert.Mein Problem ist, das ich mit Borland c++ Builder bequem mit AnsiStrings, die Methode ToInt() und ToDouble() habe und damit int und double Werte in AnsiStrings speichern konnte um z.B die gebrauchte Zeit auszugeben in einer MessageBox und mit Dev-C++ habe ich diese Methoden nicht.Mit

double zeit1=GetTickCount();
// mach irgendwas
double zeit2=GetTickCount();
zeit2=zeit2-zeit1;
string ausgabe=string(zeit2);

hat es nicht funktioniert.
Wie mach man das richtig?

std::string toString(double wert)
{
char buffer[50];
sprintf(buffer, "%f", wert);
return std::string(buffer);
}

[i_hasser]

So ungefähr weis ich jetzt wo ich suchen muss. Hab den Alg mal bei 2000k und 4000k durch den Profiler gejagt:

Each sample counts as 0.000999001 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
39.05 0.58 0.58 2000000 0.00 0.00 std::DIndex_DL::search_be(int)
25.52 0.96 0.38 2000000 0.00 0.00 std::DIndex_IDL::account_value(int)
16.91 1.22 0.25 2000000 0.00 0.00 std::DIndex_IL::account_value(int)
8.44 1.34 0.13 1 0.13 1.47 sort_new2(int*, int)
2.21 1.37 0.03 2000000 0.00 0.00 std::DIndex_IL::index2step(int)
2.01 1.40 0.03 1998561 0.00 0.00 std::DIndex_DL::insert_member(int, int)
1.81 1.43 0.03 10 0.00 0.01 std::DIndex_IL::DIndex_IL(int, int, int)
1.41 1.45 0.02 499997 0.00 0.00 std::DIndex_IDL::DIndex_IDL(int, int)
1.14 1.47 0.02 main
0.84 1.48 0.01 999994 0.00 0.00 std::DIndex_IL::step2index(int)
0.67 1.49 0.01 2998555 0.00 0.00 std::DIndex_DL::DIndex_DL(int, int)
0.00 1.49 0.00 1 0.00 0.00 global constructors keyed to sort_new2(int*, int)
0.00 1.49 0.00 1 0.00 0.00 global constructors keyed to std::DIndex_IDL::DIndex_IDL(int, int)
0.00 1.49 0.00 1 0.00 0.00 global constructors keyed to std::DIndex_IL::DIndex_IL(int, int, int)
0.00 1.49 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 1.49 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 1.49 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)


Each sample counts as 0.000999001 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
39.59 1.30 1.30 4000000 0.00 0.00 std::DIndex_DL::search_be(int)
26.15 2.16 0.86 4000000 0.00 0.00 std::DIndex_IDL::account_value(int)
17.89 2.75 0.59 4000000 0.00 0.00 std::DIndex_IL::account_value(int)
7.91 3.01 0.26 1 0.26 3.24 sort_new2(int*, int)
2.22 3.08 0.07 3994465 0.00 0.00 std::DIndex_DL::insert_member(int, int)
1.92 3.14 0.06 4000000 0.00 0.00 std::DIndex_IL::index2step(int)
1.28 3.19 0.04 main
1.12 3.22 0.04 10 0.00 0.01 std::DIndex_IL::DIndex_IL(int, int, int)
0.82 3.25 0.03 999996 0.00 0.00 std::DIndex_IDL::DIndex_IDL(int, int)
0.65 3.27 0.02 1999992 0.00 0.00 std::DIndex_IL::step2index(int)
0.46 3.29 0.01 5994457 0.00 0.00 std::DIndex_DL::DIndex_DL(int, int)
0.00 3.29 0.00 1 0.00 0.00 global constructors keyed to sort_new2(int*, int)
0.00 3.29 0.00 1 0.00 0.00 global constructors keyed to std::DIndex_IDL::DIndex_IDL(int, int)
0.00 3.29 0.00 1 0.00 0.00 global constructors keyed to std::DIndex_IL::DIndex_IL(int, int, int)
0.00 3.29 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 3.29 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 3.29 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)


Also hier verläuft alles schön linear.


€: Und gleich die 1. Zeile sagt wo die Zeit nicht linear läuft... wirklich komisch, da hätte es auch linear laufen müssen.

[Dizzy_Ti]

Original geschrieben von PuckPoltergeist
std::string toString(double wert)
{
char buffer[50];
sprintf(buffer, "%f", wert);
return std::string(buffer);
}
thx die Methode funktioniert perfekt :)

[PuckPoltergeist]

Original geschrieben von Dizzy_Ti
thx die Methode funktioniert perfekt :)

Das geht natürlich auch für int bzw. long.

[i_hasser]

hmmm ich verstehs nicht so wirklich. Es kommt nur in search_be eine Schleife vor. Wirklich NUR da.
Jetzt hab ich mal spaßeshalber innerhalb von search_be eine dummy-funktion (perf_count) aufgerufen, damit gprof die Anzahl der Schleifendurchläufe auch erfasst.

Ergebnis:



Each sample counts as 0.000999001 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
35.78 0.52 0.52 2000000 0.00 0.00 std::DIndex_DL::search_be(int)
24.56 0.88 0.36 2000000 0.00 0.00 std::DIndex_IDL::account_value(int)
19.37 1.17 0.28 2000000 0.00 0.00 std::DIndex_IL::account_value(int)
2.05 1.37 0.03 2000000 0.00 0.00 std::DIndex_IL::index2step(int)
2.93 1.34 0.04 1998561 0.00 0.00 std::DIndex_DL::insert_member(int, int)
1.67 1.39 0.02 4000938 0.00 0.00 std::DIndex_DL::perf_count()
1.50 1.41 0.02 main
1.16 1.43 0.02 10 0.00 0.00 std::DIndex_IL::DIndex_IL(int, int, int)
1.09 1.44 0.02 499997 0.00 0.00 std::DIndex_IDL::DIndex_IDL(int, int)
0.82 1.46 0.01 999994 0.00 0.00 std::DIndex_IL::step2index(int)
0.55 1.46 0.01 2998555 0.00 0.00 std::DIndex_DL::DIndex_DL(int, int)


Und


Each sample counts as 0.000999001 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
36.02 1.16 1.16 4000000 0.00 0.00 std::DIndex_DL::search_be(int)
26.72 2.02 0.86 4000000 0.00 0.00 std::DIndex_IDL::account_value(int)
18.72 2.63 0.60 4000000 0.00 0.00 std::DIndex_IL::account_value(int)
2.28 2.95 0.07 4000000 0.00 0.00 std::DIndex_IL::index2step(int)
2.07 3.02 0.07 3994465 0.00 0.00 std::DIndex_DL::insert_member(int, int)
1.56 3.07 0.05 7996072 0.00 0.00 std::DIndex_DL::perf_count()
1.49 3.12 0.05 main
1.02 3.15 0.03 10 0.00 0.01 std::DIndex_IL::DIndex_IL(int, int, int)
0.82 3.18 0.03 999996 0.00 0.00 std::DIndex_IDL::DIndex_IDL(int, int)
0.71 3.23 0.02 1999992 0.00 0.00 std::DIndex_IL::step2index(int)
0.74 3.20 0.02 5994457 0.00 0.00 std::DIndex_DL::DIndex_DL(int, int)



Alles linear! Ansonsten kommen da einfach keine Schleifen mehr vor. Da kann sonst nix nicht-linear laufen.

[Dizzy_Ti]

Nach meinem Test ist Dev-C++ im Fall das jede Zahl getauscht werden muss
doppelt so schnell wie der Compiler von Borland.
Wenn keine Zahl getauscht werden muss ist der Dev-C++ geringfügig schneller.

Ich hätte nicht gedacht, dass bei so einem simplen Quelltext es schon
solche Unterschiede gibt :o .

[PuckPoltergeist]

Original geschrieben von intel_hasser
hmmm ich verstehs nicht so wirklich. Es kommt nur in search_be eine Schleife vor. Wirklich NUR da.
Jetzt hab ich mal spaßeshalber innerhalb von search_be eine dummy-funktion (perf_count) aufgerufen, damit gprof die Anzahl der Schleifendurchläufe auch erfasst.

Alles linear! Ansonsten kommen da einfach keine Schleifen mehr vor. Da kann sonst nix nicht-linear laufen.

Du hast deinen Code noch nicht gepostet, oder? Berücksichtigst du bei deiner Laufzeit auch Funktionen, die aus libs kommen, also nicht unter deine Kontrolle fallen?

[DarkAvenger]

Oder ob der Speicherverbrauch nicht ansteigt oder ähnl?

[i_hasser]

Original geschrieben von PuckPoltergeist
Du hast deinen Code noch nicht gepostet, oder? Berücksichtigst du bei deiner Laufzeit auch Funktionen, die aus libs kommen, also nicht unter deine Kontrolle fallen?

Bis auf "new" nehm ich da keine. An den C++ Speichermanager hab ich auch schon gedacht (new ... macht ja nix anderes), bei der C-Variante hab ich das mal getestet - ich weis wie oft ich new maximal brauche und da hab ich ein großes Array mit den Elementen allokiert. Dann hab ich statt new... die Arrayelemente nach und nach zurückgegeben.

Resultat: Nix, garnix hat sich an der Auführungszeit geändert.

Und ansonsten nehm ich wie gesagt keine lib-Funktionen. Den Source poste ich dann mal (ist ziemlich viel).

... hab jetzt mal ein bisschen dran rumgespielt - ohne Änderung. Der Aufwand beträgt ziemlich genau O=n^(1.13 bis 1.16).

[DarkAvenger]

Mich würden ja ein paar Geschw.messungen interessieren, etwa wie bei meiner Liste. (Deine alte Messung ist ja nix....insebsondere wenn man den Speicherverbrauch berücksichtigt...)

[i_hasser]

Die letzten Ergebnisse mit optimiertem Code:

1M 0.65s
2M 1.37s
4M 2.92s
8M 6.25s

Wie gesagt, es kommt nicht auf absolute Zeiten sondern auf die Relation zwischen Länge/Zeit an bzw. darauf, wie sich diese verändert.
Und desswegen ist der Alg auch noch ziemlich unoptimiert.

[DarkAvenger]

Naja, was bringt dir ein pseudo-linearer Alg, der nie schneller sein wird als mergesort, weil ihm der Speicher ausgeht. Kannst du theor beweisen, daß er linear ist? Im Moment leigt über ein Faktor 10 (EDIT, OK Faktor 10 ist es nicht mehr, aber immer noch mehr als 3) zwischen deiner Ausführungszeit und dem von mergesort.

Ein Faktor 10 gilt im allg als relevant für die Tonne...

Wie gesagt, dein Speicherverbrauch (O(max-min)) ist exponentiell, darum kann das nichts werden.

Erinnerst du dich noch ein das sat Problem? Ich habe da auch ein pseudo-lineares Vf hingekriegt, aber der SPeicherverbrauch ist da auch exponentiell, also auch für die TOnne. Aber mir war das vorher klar, daß der mathematisch instabil war. Hatte nur die Hoffnung, daß die Wahrscheinlichkeit auf meiner Seite wäre...

[i_hasser]

Mein Speicherverbrauch ist nicht exponentiell, sondern n*2...

Und der Faktor ist so ziemlich egal, solange der Aufwand wirklich geringer ist.

[DarkAvenger]

??? Du hattest doch geschrieben O(max-min * irgendwas). Das ist keinesfalls 2*n. Mergesort hat 2*n. (n=Listenlänge!)

[i_hasser]

Ja, oben hab ich Müll geschrieben. Der Speicherbedarf ist je nach Einstellung (1+a)*(n+8). a ist dabei <1 und fest verdrahtet.

[DarkAvenger]

Was heißt "je nach Einstellung". Wie viel Speicher nimmt der bei deinem 8M Bsp ein?

[i_hasser]

Das a ist ein Parameter der beeinflusst ob mehr Speicher gefressen wird oder ob es schneller gehen soll. Linear bleibt es in jedem Fall.

Momentan hab ich a=1/4 - also die 8M Variante frisst danach 114MB Speicher.

[DarkAvenger]

Uhem, ein Faktor 10 beim Speicherverbrauch gilt auch als relevant. Mir fällt jedenfalls keine Anwendungsmöglichkeit ein, wann dein ALg sinnvoll nutzbar ist?

[i_hasser]

1. gehts um die Theorie und nicht so sehr um die Praxis - in 3 Jahren werden wir über 4GB RAM nur müde lächeln.

2. hab ich jemals gesagt, dass man den Speicherbedarf nicht noch senken könnte?

3. Eine 8M Liste aus Integern ist sowieso schon 32MB groß. Mein Alg braucht also nur <4mal so viel Speicher wie die Liste selbst.

[DarkAvenger]

zu 1) Ich habe noch keinen Beweis gesehen, daß es linear ist. Einer Implementierung sieht man das normalerweise nicht sofort an...(bzgl zukünftiger Rechner:) Die Probleme werden auch größer werden...also wieder nix ;)

Nur überlge mal so: Um mehr Speicher schneller zu verarbeiten, mußt du entsprechned en Datenbus entsprechend schenller machen. Die "normalen" Sortiervf werden davon ebenfalls profitieren.

zu 2) Ich bin mal gespannt. Speicherverbrauch enken allein reicht ja nciht. Wie schon mal erwähnt. Es gibt auch einen polynomiellen (oder gar linearen) Alg zur Primzahlbestimmung, nur wird der so gut wie nie schneller als die exp. Alg sein... Nur hatte dieser ALg eine große theor. Aussagekraft, wogegen man beim Sortieren weiß, daß Linearzeit möglich ist unter Nutzung der Schlüsselinformationen. Also sorry, du zeigst nichts neues. Du machst allerhöchstens sowas wie bucketsort effizeinter, also verschiebst die Grenze etwas.

zu 4) Hmm, OK, die Datenstruktur hatte ich nicht berücksichtigt. Naja, es gibt genügend LEute, die sich bei mergesort an dem FAktor 2 stören...

Naja, evtl gibt es irgendwelche hochspeziellen anwendung,w o man deinen Alg sinnvoll einsetzen könnte, denn theor, wird der nicht viel hergeben, höchstens was die "Kunst des Programmierens" angeht, denke ich mal.

[i_hasser]

So richtig kennst du meinen Alg doch noch garnicht. Mit Bucketsort hat der nicht mehr viel gemein, aber das ist der ähnlichste - und das nur aus dem Grunde, weil der auch neu indiziert.

[DarkAvenger]

Klar kenn ich ich nicht, aber ich kann ja ausschließen, was er ist. ;)

[DarkAvenger]

Mein Vorschlag für lineares Sortieren für beliebig große Zahlen funktioniert (auch floats, siehe unten) und auch nur 2*n (es ginge auch in 1*n, wenn man verkettete Lsiten benutzt! Obwohl, bin mir nicht sicher, man müßte irgendwo bei der Rekursion die Listenenden speichern, also wäre spätestens auf dem stack wieder n) Speicherverbrauch:

Wahrscheinlich handelt es sich hierbei um Radixsort, denn ich hatte nur bucketsort in Info I gelernt, und weiß nur von der Existenz von Radixsort.

Man hat seine n Zahlen mit vorgegebener bitlänge (also etwa longs=32bit).

Man zähle (naja man muß nciht wirklich zählen...) die # der Zahlen, bei denen das 32. bit gesetzt ist. Diese vershciebt man (wie bei mergesort etwa mit dem temp array) and Ende der Liste und setzt alle anderen davor.

Man fährst rekirsiv mit dem nächsten bit fort für die beiden Teillisten, bis man bei dem 0. angekommen ist.

Laufzeit= #bits*n, also linear und wesentlich weniger Speicherverbrauch.


Wie macht man das bei float? Nun hier muß man die Mashchine kennen und erst mal nach dem Exponenten und dann nach der Mantisse sortieren.

Tada!

[PuckPoltergeist]

So, damit ihr mal wieder runter kommt, schlage ich vor, dass ihr (wir?) demnächst die Algorithmen auf eine (R)RAM übertragt, und daran die Speicher- und Laufzeitüberlegungen anstellt. Das ist allgemeingültig und hat auch entsprechende Aussagekraft. Des weiteren sind Algorithmen so auch noch relativ leicht überschaubar. Damit gibt es eine einheitliche Basis, um sich erst mal über die eigentlichen Algorithmen zu verständigen. ;)

[DarkAvenger]

Alles was ich erzählt habe, findet man bestimmt in jedem Buch. Warum PRAM, willst du was parallel machen? Meine Vf laufen auf EREW(1,n) resp EREW(1,n*logn) (=sequentiell ;))

Oops, habe mich verlesen. Was ist eine RRAM?

[PuckPoltergeist]

RRAM - Real Random-Access-Machine, also eine RAM, welche auf reellen Zahlen arbeitet. Die "normale" RAM arbeitet ja nur mit natürlichen Zahlen.

[i_hasser]

@DarkAvenger

Also immer hübsch langsam, eine verkettete Liste frisst schonmal so einiges an Speicher (ohne den Speicher würde mein Alg auch (1+a)4n weniger verbrauchen).

Der Aufwand von deinem Alg hängt aber davon abgesehen auch von der Zahlenlänge ab, meiner nicht - theoretisch funktioniert meiner auch mit Reellen Zahlen, deiner nicht ;).

Und bei Floats hast du sowieso ein großes Problem - es gibt normale Floats und nicht normale Floats. Einfach gesagt: 1.234e3 = 0.1234e4. Und wenn du sowas mit einbeziehst wird dein Alg extrem langsam.

EDIT: Nein, der Alg funktioniert garnicht (zumindest nicht in linearer Zeit).

Wenn du alles nach dem 1. Bit unterschieden hast wars das ja noch nicht - und die beiden Mengen die da entstehen musst du wieder nach den Teilbits sortieren. Damit beträgt der Aufwand n^32*a (wobei a sehr klein ist).

[PuckPoltergeist]

Original geschrieben von intel_hasser
EDIT: Nein, der Alg funktioniert garnicht (zumindest nicht in linearer Zeit).

Ich habe mir das Dingens immer noch nicht vollständig angeschaut, bilde mir aber ein, dass die Klasse schon mit Fließkommazahlen (double) arbeitet.

[i_hasser]

Ja, wie gesagt, man müsste floats/doubles vorher noch normalisieren.

Aber mal ein Beispiel:

a soll unsere komplette Menge sein.

b1 -> alle (a& (1<<31))==1
b2 -> alle (a& (1<<31))==0

Dann gilt |b1|+|b2|=|a|, also im Schnitt |b1|=|b2|=|a|/2

Also O_b=|a|

Dann müssen wir die Mengen nach dem 2. Bit unterscheien ->

c1 -> alle (b1& (1<<30))==1
c2 -> alle (b1& (1<<30))==0

c3 -> alle (b2& (1<<30))==1
c4 -> alle (b2& (1<<30))==0


hmm... nagut. O_c ist auch |a| und der gesamte Aufwand ist dann O=O_b+O_c+..., also O=32n bzw. 32*|a|.

Langsam ist das aber zu 100%. Vor allem mit einer verketteten Liste.

[PuckPoltergeist]

Könntest du bitte die O-Notation richtig verwenden? Das irritiert doch sehr stark, was du da machst. O(32*n) = O(n), soll heißen Konstanten werden da raus gelassen.

[i_hasser]

Die O-Notation ist in der Praxis sowieso mehr oder weniger sinnlos. Was bringt es mir, wenn zb. O=n^1.1 mehr Aufwand bedeutet als O=n*log(n) - das wirkt sich erst ab 1e10 aus. Praktisch kann da der Rechner nicht mehr.

Die Frage ist wie natürlich auch wie lange die n brauchen, und da machen sich konstanten gut. O=an^1.1 und O=bn*log(bn) - ist a>>b macht der 2. Alg durchaus Sinn, ist dagegen a<<b macht der 2. Alg durchaus Sinn (um genau zu sein bräuchte man eine Verteilungskurve der praktischen Verwendungshäufigkeit von der man O bildet und worüber man dann einfach integriert).

Da n bei meinem Alg und n bei DarkAvengers Alg ziemlich ähnlich ist (von der Zeit her) hab ich 32n geschrieben.

[PuckPoltergeist]

Original geschrieben von intel_hasser
O=an^1.1

Wer macht denn bitteschön sowas? Das läßt sich doch eh nicht abschätzen. Für mich ist das O(n), es sein denn, du kannst mir die 1.1 wirklich sauber und schnell zeigen (was ich wirklich bezweifle).

[DarkAvenger]

@intel hasser

Nein, du hast es nicht verstanden. Lies es nochmal durch. Deine Argumentation ist falsch. (Warum? DU hast die Rekursion nicht verstanden.) Auch mit floats sollte es unabhängig der Notation funkt. Bitte *genau* lesen. Ich habe eine eindeutige Ordnungsrelation zugrundegelegt.

Ok, das mit der Liste stimmt schon, aber mit 2 array habe ich 2*n.

Auch ok, mit reellen Zahlen geht es nicht, aber gibt es denn reale Machienen, die reell arbeiten? (Kleines Wortspiel am Rande.;))



Für die Leute, die meinen Alg verstanden haben:

Warum ist der dennoch fast immer langsamer als mergesort? Nun 2^32 = 4G, also wird etwa beim Zahlentyp long, mergesort erst dann langsamer als der lineare Alg, wenn man es mit 4G Zahlen zu tun hat! (Man sollte immer im Hinterkopf haben, daß log n seeehr langsam steigt.)

Es gibt aber eine Trick: Man beachte daß die Unterscheidung nach bits darauf berucht, daß wir uns im Zahlensystem zur Basis 2 befinden und damit eine 32 bit Zahl 32 Durchläufe braucht. Nun, also erhöhen wir einfach die Basis. Wenn wir etwa zur Basis 10 arbeiten (unsere gewohnten Zahlen) haben 32 bit Zaheln nur noch 13 Stellen, und wir wären (evtl) schneller ls mergesort. Wie? Nun muß man eine Liste führen von 0 - b (hier b=9) und wirklich zählen wie oft die Ziffer an der i. Pos (i von most significant to least, analog bei b=2). Dememtsprechend können wir berechnen, wo wir die Zahlen im temp array hin verfrachten müssen.

Iteration für nächste Ziffer in den b Teillisten.

Man könnte die Basis b beliebig wählen, so daß wir nur 2*n Durschgänge bräuchten (einmal zählen, einmal verfrachten), und damit wären wir wieder beim bucketsort Alg, der als Spezialfall auftaucht. Mit dem bekannten NAchteil, daß die Liste, die die # führt vom größten (und evtl kleinsten) Zahlenwert abhängt.

Dementsprechned wäre das schlauste das b so zu wählen, daß es etwa n entspricht, würde ich meinen.

[i_hasser]

Mein Alg läuft momentan zb. komischerweise n^(1.0875). Für 2n beträgt die Zeit komischerweise immer >=2.1t, und ist aber bisher auch nie größer als 2.15t gewesen. log(2.1)/log(2) ist 1.07, log(2.15)/log(2) ist 1.105 - das Mittel ist 1.0875.

Klar muss man es nicht so genau handhaben - aber früher oder später macht das schonmal einen Unterschied. In den kleinen Bereichen läuft die Mergesort Implementierung in etwa n^1.1 .

[i_hasser]

Original geschrieben von DarkAvenger
@intel hasser

Nein, du hast es nicht verstanden. Lies es nochmal durch. Deine Argumentation ist falsch. (Warum? DU hast die Rekursion nicht verstanden.)

Das mag daran liegen, dass deine Erklärung weder sprachlich, noch logisch ganz einwandfrei war :]

[i_hasser]

So, also die Abweichung bei meinem Alg von O=n liegt anscheinend nicht an den gegebenen Vorraussetzungen.

Hab ihm mal eine absolut homogene Liste zum Fressen gegeben (da O auch von (max-min) abhängt ist die Ausführungszeit für 2M übrigens auf 0.5 Sekunden gefallen - mit debug Code) und die Zeit steigt immernoch n^(a>1).

[i_hasser]

Und schon wieder ich :P


while(1)
{
#ifdef PERF_MON
pm_lc[3]++;
#endif

if(ttab_ptr[0]->next->index>data[i]) break;
if(ttab_ptr[0]->index==data[i]) break;
ttab_ptr[0]=ttab_ptr[0]->next;
}

Das ist der Übeltäter. Die Laufzeit für einen einzelnen Durchlauf ändert sich mit steigender Listenlänge (das hier ist jetzt die C-Variante, wegen der Kapselung lässt sich ein Performance Monitoring in C++ nicht so gut implementieren wie in C).
Die Anzahl der Durchläufe insgesammt steigt wie erwartet linear mit der Listenlänge (bzw. besser gesagt etwas unter-linear) - aber die Laufzeit eines einzelnen Durchlaufes dieser Schleife ist komischerweise nicht konstant.

Hab mal genau nachgemessem:


Listenlänge CPUTakte/Durchlauf
250k 354
500k 422
1M 456
2M 477
4M 500
8M 554


Das müsste ja eigentlich genau konstant sein. Ich werd jetzt mal noch die CPU Takte für jede einzelne Anweisung messen. Vielleicht bringt das noch etwas aufschluss.

[Sargnagel]

Original geschrieben von intel_hasser
aber die Laufzeit eines einzelnen Durchlaufes dieser Schleife ist komischerweise nicht konstant.
Juchhu - ich kann auch mal was sagen ... ;D

und sage lediglich: branch prediction *chatt*

[DarkAvenger]

Ich gebe zu, daß meine ich sprachlich nicht allzu viel auf meine Erklärung gegeben habe - dennoch sollte diese verständlich sein - , da ich nebenher ein EM Spiel angucke und auch nur 5h geschlafen hatte. Aber wenn du mir so kommen willst, dann könnte ich auch auf deine generell schwächelnde Orthographie hinweisen...

Logisch ist die Erklärung richtig...


Der Punkt an dem du wohl scheiterst: Die Rekursion bezieht sich nicht auf die ursprüngliche Listenlänge, sondern nur auf die Teilliste.

Übrigens, ist mir ein ziemlich guter Einfall bzgl der zu wählenden Basis gekommen bei (unsigned?) integer: b= 256

Wer es verstanden hat, sollte die Idee sehen...

Ein Tip:

union {
unsigned long Schlüssel;
unsigned char byte[sizeof (unsigned long)];
}


Bei CPUs mit viel L1 bzw L2 cache könnte man auch b=2^16 wählen. Würde die Durschläufe halbieren zu dem Preis, daß die Zählmenge wesentlich größer geworden ist (was aber bei n im GB Bereich dennoch sinnvoll sein könnte.

[i_hasser]

So, ich hab jetzt mal ganz genau nachgemessen. Hab alle 4 Anweisungen an den TSC gehangen.

250k 500k 1M 2M 4M 8M 16M 32M
Anweisung 1 105 148 151 149 162 179 203 230
Anweisung 2 11 13 13 13 13 14 14 14
Anweisung 3 103 112 119 127 138 163 197 225
While-Ende 44 57 66 73 78 82 87 97

while(1)
{
if(ttab_ptr[0]->next->index>data[i]) break;
if(ttab_ptr[0]->index==data[i]) break;
ttab_ptr[0]=ttab_ptr[0]->next;
}


Das kann ich mir jetzt nicht mehr so wirklich erklären. Eigentlich dürften die Daten da nämlich garnicht im Cache liegen, und die Zeiten sagen auch, dass die Daten aus dem Ram kommen.
Branch Prediction glaub ich auch nicht so richtig, höchstens die Steigerung beim While-Ende. Aber eigentlich sollte sich da auch nix verändern - im Schnitt läuft diese Schleife immer - ob nun 250k oder 32M - 5mal hintereinander durch. Aber das werd ich auch gleich mal nachmessen.


EDIT: Nein, wodurch auch immer läuft die Schleife bei jeder Listenlänge im Schnitt 3mal durch :P

[i_hasser]

LOL

Das ist der Einfluss der nicht ganz homogen verteilten Liste. Bei einer absolut homogenen Liste (die dazu schon aufsteigend sortiert ist) beträgt die Zeit pro Schleifendurchlauf ziemlich konstant 148 Takte.

Das Komische ist ja nur, dass ich das bei dem anderen Alg (der C++ Implementierung) schon umgangen hab :-/
Und die Frage ist natürlich auch wieso der da nicht linear läuft. Liegt es daran, dass die Zugriffe viel verteilter sind (weil die Liste nicht schon sortiert ist -> dann wäre es zb. der Cache) oder liegt es an was anderem (-> nicht der Cache).

Da muss ich jetzt wohl eine Funktion schreiben die eine absolut homogene, aber unsortierte Liste erzeugt.

[DarkAvenger]

Mist, die Käs'köppe sind weiter. :/

Also, zu meinem Alg mit b=256 ist mir eingefallen, daß der universell anwendbar ist, nur muß für jeden Sch### Fallunterscheidung gemacht werden:

- big/small endian?
- signed/unsigned? (bei signed dann die weniger signifikanten bytes umgekehrt ordnen)
- bei floats/doubles muß mit Binäroperatoren der Exponent bzw die Mantisse extrahiert werden.

Ich werde mal morgen den Alg für unsigned long implementieren. Habe auch schon eine effiziente Regelung der Datenstrukturen im Kopf. Laufzeit sollte 8*n sein. Speicherverbrauch 2*n + 4*b.

[i_hasser]

Ich hab mir vorhin schon auf deinem Alg basierend eine bessere und effizientere Version ausgedacht (da ich dich vorhin aber anscheinend falsch verstanden hab basiert es wohl doch nicht auf deinem Alg). Ok, in den Grundzügen will ich das bzw. hab ich das teilweise auch schon in meinen aktuellen Alg implementiert (die dynamische Bereichsaufteilung für Intervalle homogener Verteilung).

Wenn ich es mir recht überlege ist das wirklich eine Überlegung wert.

Meinen bisherigen Alg hab ich jetzt mal mit nicht sortierten Listen homogener Verteilung durchgemessen. Dummerweise schwanken die Werte aber viel zu stark, der Trend ist aber ziemlich deutlich - die Ausführungszeit bleibt wie erwartet konstant.
Da könnte ich die dynamische Bereichsaufteilung auch mal spaßeshalber in die C++ Variante implementieren.

[DarkAvenger]

Mir klingt das fast danach, daß du irgendwelche Heuristiken anwendest... Wird schwer sein, dafür eine Laufzeitanalyse hinzubekommen. Aber ich laß' mich überraschen. ;)

Ok, muß mal was Schlaf nachholen gehen. Frohes Schaffen noch!

[i_hasser]

Und zwar dynamische Heuristiken auf Heuristiken basierend ;D

Da kann man nur noch eine Best-Case und eine Worst-Case Analyse machen ;).


EDIT: Ja, ich glaub ich hab einen guten Alg. O=log(max-min)*n oder irgendsowas wie O=f(max-min)*n wobei f irgendeine logarithmusähnliche Funktion ist.

Reelle Zahlen sollten auch möglich sein.

Allerdings ist der Speicherbedarf wieder nicht gerade ermutigend. Irgendwo bei sizeof(n)+8.

EDIT: Nein, der Speicherbedarf ist nur sizeof(n)+4 ;D - bei 32bit Integern also 8 Byte*n.

EDIT: hmm... aber mit reellen Zahlen wirds anscheinend nix. Obwohl... doch. Aber nicht in der 1. Version, und später auch nur über nette, völlig undurchschaubare Konstrukte... und vor allem nicht mit O=n, bestenfalls O=n^2 :(

Aber bei Integern ist alles drinnen. Also 64bit Ints sind auch kein Problem. Beim Aufwand können wir sogar ein Speed/Mem Tradeoff bekommen, und das macht den Aufwand bei 32bit Integern auch absolut (undabhängig von (max-min) - wir nehmen einfach konstant 2^32).
Bei einem geringen Speicherbedarf (8n+(2^16)(12)))*1Byte sollte das sogar richtig schnell gehen.

EDIT: Natürlich geht das auch für nicht-Integer (müssen aber endliche Zahlen wie double oder float sein, reelle Zahlen gehen nur mit unendlichem Aufwand *buck*).

[i_hasser]

*lol*

Also der Alg ist sicher linear, dummerweise beträgt die Ausführungszeit mindestens 25 Sekunden *chatt* *chatt*

AARRRGH!

EDIT: So, wenigstens das hab ich jetzt beheben können. Allerdings nur für sehr kleine Listen - der Algorithmus ist Feind jeder homogen verteilten Liste (aber glücklicherweise nur bei sehr kleinen Listen).

Bei Listen in kleineren Zahlenbereichen ist der Alg aber verdammt schnell :o. Hab jetzt mal 0 bis 2^20 (~1 Mio) genommen.

Hier die Zeiten:


1M: 0.15s
2M: 0.29s
4M: 0.61s
8M: 1.18s


Juchu! Linear ;D 8) *buck*

Das mit dem log(max-min) war übrigens gelogen, es ist (max-min) :P


E:

So, also am besten skaliert der Alg wenn die Listenlänge in etwa (max-min) entspricht.
Hab ein paar Parameter getuned und jetzt ist die Zeit für 8M bei (max-min)=16M 1.26s.
Bei (max-min)=1M wie vorhin ist der BucketSort noch deutlich schneller, abei bei (max-min)=16M fängt meiner langsam an weniger Speicher zu verbrauchen (64MB BucketSort vs. 128.01MB für meinen *buck* - also bei einem Bereich von 32M lohnt es sich, da braucht meiner nämlich nur 128.02MB während der BucketSort da auch 128MB braucht).

So, jetzt sind es 0 bis 16M und er braucht 1.88 Sekunden. Der Alg deckt speichermäßig jetzt 0 bis 2^31 ab und braucht 1.5MB+8Byte*n, also 129.5MB bei 8M.

Mir ist noch eine Optimierung eingefallen die - rein theoretisch - vor allem bei ungünstigen Bedingungen (wenig Zahlen in einem größen Bereich) ordentlich Geschwindigkeit bringen könnte. Aber da kommt dann wieder die Heuristik ins Spiel ;)

Also momentan sieht der Aufwand so aus: O=(max-min-a)*w1+n*w2.
Dabei gilt w1 > w2 (w2 ist sogar sehr klein) und a geht für homogene Listen mit n/(max-min)>16384 (fest im Alg verdrahtet) gegen 0. Bei absolut nicht homogenen Listen geht a gegen (max-min), unabhängig von n.

[DarkAvenger]

Nicht schlecht, deine neuen Werte, wirklich nicht schlecht, auch wenn es wohl nur bei Spezialfällen so gut läuft.

Ich habe mal eine erste Version meines Alg implementiert. Allerdings hat di noch einen kleinen bug, weil ab und an ein paar Zahlen verkehrt stehen. Ich nehme mal an, daß ich irgendwo bei den Intervallgrenzen geschlampt habe. Naja, aber die Zeiten sollte auch so schon aussagefähig sein:


n = 1k average time: 0.0032887
n = 2k average time: 0.0055794
n = 4k average time: 0.0106285
n = 8k average time: 0.0212953
n = 16k average time: 0.0394551
n = 32k average time: 0.074813
n = 64k average time: 0.136178
n = 128k average time: 0.235071
n = 256k average time: 0.393645
n = 512k average time: 0.674017
n = 1024k average time: 1.21821
n = 2048k average time: 2.27839
n = 4096k average time: 4.26741
n = 8192k average time: 7.81394
n = 16384k average time: 13.3847


2 Dinge erkennt man:
1) Er ist deutlich langsamer als meine mergesort Implementation.
2) Er läuft offenbar in Linearzeit wie designed.
3) Er sollte bei beliebigen (hier 32 bit unsigned integer) gleich schnell laufen.

Meine Vermutung, warum der langsamer läuft: Mergesort ist chache effizienter. Es wird bei mergesort mehr "lokal" gearbeitet, während hier stets die ganze Folge bearbeitet wird. Daneben sieht man, daß mergesort sehr einfach gestrikt ist, wogegen ich hier doch etwas mehr overhead habe, der sich in der Laufzeit niederschlägt. Naja, muß mal den profiler bemühen.

Ich denke, wenn ich b=2^16 wähle, sollte sich die Zeit fast halbieren, aber ich bin dennoch zu weit weg von mergesort...

[i_hasser]

An den Spezialfällen arbeite ich noch ;). Die Liste kommt direkt aus dem Zufallsgenerator und dürfte homogen sein, ich muss mir eben nur noch was wegen min/max einfallen lassen. Mir ist aber schon was für den Speicherbedarf eingefallen, was wahrscheinlich auch mehr Geschwindigkeit bringt.

[DarkAvenger]

Hmm, habe mich geirrt. Mit b=2^16 wird es noch lahmer. Also liegt es am overhead. Muß doch mal den profiler benutzen um zu gucken, wo es am meisten verliert...

[DarkAvenger]

So, habe meinen Algorithmus gefixt und auch per profiler die Spaßbremse entdeckt: Die Präfixsummenbildung verschlingt mehr als die Hälfte(!!!) der Zeit...

EIne kleinen Trick habe ich bereits angewendet (der auch als fix fungiert) und schon sind die Zeiten schneller und kommen fast an mergesort ran:


n = 1k average time: 0.0003464
n = 2k average time: 0.0005051
n = 4k average time: 0.0006561
n = 8k average time: 0.0016538
n = 16k average time: 0.0038561
n = 32k average time: 0.0099401
n = 64k average time: 0.0275142
n = 128k average time: 0.061151
n = 256k average time: 0.0965709
n = 512k average time: 0.126606
n = 1024k average time: 0.187212
n = 2048k average time: 0.379544
n = 4096k average time: 0.883582
n = 8192k average time: 2.28398
n = 16384k average time: 5.72693



Es sieht nciht mehr linear aus, aber der Schein trügt! Ich denke, das wird auch der gleiche Grund sein, wie bei intel_hassers älteren Alg:

Der Alg an sich ist linear, aber das Einsparen durch Heuristik (ich benutze keine, aber hat ähnl Effekt) ist *nicht-linear*, dh. umso größer die Eingabelänge wird, umso wenigert kann hier mein Trick einsparen.

Aber ich denke, ich weiß, wie ich schneller werde: Ich muß einen Hybrid-Alg mit mergesort machen. Auch wenn das nach nicht-lin anhört, sollte es immer noch linear sein(!), weil mergesort nur dann eingreifen wird, wenn die Wahl von b (in der Rekursion natürlich nur) den Alg dominiert. Im Moment kann bei ungünstigen Situationen, die bei großen n offensichtlich häufiger vorkommen, das b bis zu 128 mal mehr Aufwand bedeuten als etwa mergesort brauchen würde....

[i_hasser]

Nach anfänglichen Schwierigkeiten siehts mit der Optimierung ziemlich gut aus. Ohne die Optimierung mag der Alg ganz andere voreingestellte Werte als mit, hatte mich schon geärgert, dass die Kiste jetzt viel langsamer ist ;).

Der Speicherbedarf beträgt im Idealfall nur noch 2MB+64kB+17/4*n Byte (bei 32bit Integern). Oder allgemein 2MB+64kB+( sizeof(n)*n+(n/64)*16 ). Also bei 8M macht das 34.5MB, die Liste als statisches Array braucht schon 32MB ;D.

[DarkAvenger]

Nicht schlecht. Damit steht dein Alg im Speicherverbrauch nicht mehr hinten an. ;)

Übrigens, gbt es eine Möglichkeit "schnellen" Speicher zu reservieren inc bzw c++? Ich möchte, daß 4kb nach Möglichkeit immer im L1 cache verbleiben...

[Dizzy_Ti]

Original geschrieben von DarkAvenger


n = 1k average time: 0.0003464
n = 2k average time: 0.0005051
n = 4k average time: 0.0006561
n = 8k average time: 0.0016538
n = 16k average time: 0.0038561
n = 32k average time: 0.0099401
n = 64k average time: 0.0275142
n = 128k average time: 0.061151
n = 256k average time: 0.0965709
n = 512k average time: 0.126606
n = 1024k average time: 0.187212
n = 2048k average time: 0.379544
n = 4096k average time: 0.883582
n = 8192k average time: 2.28398
n = 16384k average time: 5.72693


Kannst du bitte mal das ganze im Best-Case benchen?
EDIT:
Durch einen blöden Fehler waren die gepostenen Zeiten beide falsch.

[PuckPoltergeist]

Original geschrieben von DarkAvenger
Übrigens, gbt es eine Möglichkeit "schnellen" Speicher zu reservieren inc bzw c++? Ich möchte, daß 4kb nach Möglichkeit immer im L1 cache verbleiben...

Nein, das ist Sache des OS und letzten Endes der CPU. Außerdem fliegt dir das Zeugs bei einem Taskwechsel eh wieder aus dem Cache. Macht also wenig Sinn sowas anzubieten. Du kannst sowas nur forcieren, in dem du wenige lade- und speicher-Operationen ausführst.

[i_hasser]

falsch, aktuelle CPUs bieten eine Prefetch Möglichkeit mit der man explizit einen Speicherbereich vor Nutzung in den Cachel laden lassen kann.

Das ist übrigens CPU Sache, das OS kann auf die Cacheverwaltung genausowenig Einfluss nehmen wie ein Programm selbst (also auch nur per Prefetch).

[DarkAvenger]

@Dizzy_Ti


Was würde das denn bringen? Außerem müßte ich was nachdenken, wann der best case eintritt (nicht ganz trivial).

@rest

Naja, ich frage mich halt, warum in anderen libs etwa statt malloc calloc oder ähnl verwendent wird. Macht das nen Unterschied oder ne Ahnung wass die anderen ?allocs so bewirken?

[i_hasser]

Schade. Mein neuer Alg braucht wieder etwas länger, dafür hat er aber den geringeren Speicherverbrauch und früher oder später wird der auch wieder schneller als mergesort (vor allem weil es bei längeren Listen immer unwahrscheinlicher wird einen Worst Case zu erwischen in dem zum normalen Aufwand noch eine recht große "Strafzeit" kommt).

Aber ich werd auch mal ein bisschen mit den Parametern spielen.

...

So, naja. 2.2 Sekunden für 8M. Aber dafür einen Speicherverbrauch von ~40MB.
Und mir fällt gerade auf, dass ich mit Debug Code gebencht hab *buck*

Kann sich eigentlich sehen lasse - 1.65 Sekunden. 2.74 Sekunden für 16M und 4.92 Sekunden für 32M.

Ich sag doch, je mehr Werte es werden desto unwahrscheinlicher wird der Worst Case ;D.

Fairerweise muss ich aber noch sagen, dass die Werte alle zwischen 0 und 64 Millionen lagen. Mit großen Bereichen tut sich der Alg nach wie vor schwer.

hmm... *kopfkratz* da könnte man doch eigentlich auch was optimieren...

;D

8)

[DarkAvenger]

Ok, mir ist doch der best case ingefallen: Alle Zahlen gleich, hier gleich 0:


n = 1k average time: 6.36e-05
n = 2k average time: 0.0001167
n = 4k average time: 0.0002279
n = 8k average time: 0.0004548
n = 16k average time: 0.0013213
n = 32k average time: 0.0020023
n = 64k average time: 0.0042235
n = 128k average time: 0.0088796
n = 256k average time: 0.0176154
n = 512k average time: 0.0356135
n = 1024k average time: 0.0710616
n = 2048k average time: 0.140984
n = 4096k average time: 0.282647
n = 8192k average time: 0.564722
n = 16384k average time: 1.12756


Wieder herrlich linear und damit habe ich eine untere Schranke, die ioch auch mit mergesort-hybrid nicht (wesentlich?) unterbieten kann...

[Dizzy_Ti]

Original geschrieben von DarkAvenger
@Dizzy_Ti


Was würde das denn bringen? Außerem müßte ich was nachdenken, wann der best case eintritt (nicht ganz trivial).

Ich wollte einmal die maximale Differenz zwischen der schlecht möglichsten Zeit und beste möglichen Zeit sehen.

[DarkAvenger]

Ne andere Frage:

Weiß jemand, ob man mit mmx oder ähnl 32 bit integers addieren kann, bzw mehrere gleichzeitig? Wahrscheinlich wird das Problem sein, die Zahlen entsprechend zu füttern...

Naja, wie gesagt ich die Präfixsummenberechnung bei mir der Zeitkiller. Da ich ja weiß, wie der zu parallelisieren ist, sollte der per SIMD berechnbar sein.

Alg war EREW(n/log n, log n) (oder CREW, müßte nochmal nachgucken).

Im meinem Fall bei 256 wären also 8 simultane Operationen optimal.

[i_hasser]

Da braucht meiner bei 8M 0.5 Sekunden. Aber wer will sowas schon sortieren ;).

Mal ein paar mehr Zeiten:


250k 0.02s
500k 0.03s
1M 0.06s
2M 0.12s
4M 0.25s


Alles mit konstanter Zahl.

Mit nun wirklich zufälligen Zahlen sieht es so aus:


62.5k 0.61s
125k 0.62s
250k 0.64s
500k 0.66s
1M 0.75s
2M 0.86s
4M 1.12s
8M 1.67s
16M 2.74s
32M 4.82s


Das sieht doch mal schick aus ;D

Ein paar der Parameter die ich fest eingestellt hab will ich noch von der Bereichsgröße und von der Listenlänge abhängig machen - aber da muss ich mir erstmal in Ruhe überlegen wie ich das am dümmsten anstelle.

[Sargnagel]

Original geschrieben von DarkAvenger
Weiß jemand, ob man mit mmx oder ähnl 32 bit integers addieren kann, bzw mehrere gleichzeitig?
[...]
Im meinem Fall bei 256 wären also 8 simultane Operationen optimal.
128bit Vektoren stehen Dir zur Verfügung. Du kannst also 4 32bit Integer in einen Vektor packen und die Vektoren miteinander addieren.
Bei GCC kannst Du folgende Funktionen verwenden, ohne auf (Inline)Assembly zurückgreifen zu müssen:
http://gcc.gnu.org/onlinedocs/gcc/X86-Built-in-Functions.html#X86%20Built-in%20Functions
http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html#Vector%20Extensions

Bei Intel gibt's jede Menge PDFs, die die einzelnen SIMD-Instruktionen erklären ... Links habe ich leider nicht parat.

[PuckPoltergeist]

Original geschrieben von intel_hasser
falsch, aktuelle CPUs bieten eine Prefetch Möglichkeit mit der man explizit einen Speicherbereich vor Nutzung in den Cachel laden lassen kann.

@intel_hasser1:

Also Sache des OS. ;)


Das ist übrigens CPU Sache, das OS kann auf die Cacheverwaltung genausowenig Einfluss nehmen wie ein Programm selbst (also auch nur per Prefetch).

@intel_hasser2:

Sag ich doch, letzten Endes Sache der CPU. ;)


PS: Also eines von deinen beiden Ichs sollte dauerhaft die Kontrolle übernehmen. Das ist extrem irritierend, wenn von ein und der selben Person im gleichen Atemzug zwei konträre Meinungen kommen. ;D

[DarkAvenger]

@Sargnagel

Thx, werde ich mir mal zu Gemüte führen.

@Intel_Hasser

Ich habe aber die Vermutung, daß sich nach der Hybridisierung mein ALg näher am best case als am jetzigen average case orientieren wird. :) Die konstante Zahl sorgt nur für optimale "Auslastung" der Prefixsummenliste.

Und ich kann "bel" große Zahlen sortieren. Selbst 64bit sollte ohne allzu viel Zeitverlust möglich sein (max Faktor 2, glaube ich aber nicht).

[i_hasser]

@Puck

Die Cacheverwaltung hat nix mit der Speicherverwaltung vom OS zu tun, daher hat das auch nicht mit dem OS selbst zu tun sondern ist Programm<->CPU gebunden.

[DarkAvenger]

So, hier mal eine schnelle Anpassung auf *echte* 64bit Zufallszahlen (die auch alle 64bit ausnutzen könnten...):


n = 1k average time: 0.0003535
n = 2k average time: 0.0005015
n = 4k average time: 0.0007811
n = 8k average time: 0.0017725
n = 16k average time: 0.0037203
n = 32k average time: 0.0109599
n = 64k average time: 0.0294059
n = 128k average time: 0.065548
n = 256k average time: 0.108716
n = 512k average time: 0.151257
n = 1024k average time: 0.274353
n = 2048k average time: 0.505
n = 4096k average time: 1.30892
n = 8192k average time: 4.15553
n = 16384k average time: 9.05092


Man beachte, daß die letzte Instanz alleine 128MB Speicher für die Werte benutzt...

Ich fühle miene Vermutung bestätigt. :) Doch nun frage ich mich, ob es statt der Hybridisierung nicht doch sinnvoller wäre mit b=16 statt b=256 zu arbeiten. Naja, kann ja beides mal probieren.

[PuckPoltergeist]

Original geschrieben von intel_hasser
@Puck

Die Cacheverwaltung hat nix mit der Speicherverwaltung vom OS zu tun, daher hat das auch nicht mit dem OS selbst zu tun sondern ist Programm<->CPU gebunden.

Wieso nicht? Das OS kann doch bei der Speicherverwaltung die Cachestruktur berücksichtigen. Wieso hat die Cacheverwaltung nichts mit der Speicherverwaltung zu tun? Der Cache gehört doch zum Speicher.

[i_hasser]

Der Cache gehört desswegen nicht zur Speicherverwaltung, weil der funktional rein garnix beeinflusst.

Es macht nicht den geringsten Unterschied ob eine CPU Cache hat oder nicht - aus Programmierer Sicht ändert das rein garnix. Dazu ist die Cacheverwaltung nicht das was du dir vorstellst - du kannst nicht mal eben 20 Byte Informationen pro Cacheline speichern, das wäre schon viel zu ineffizient. Und der Cache funktioniert nicht fix - der wird dynamisch von der CPU anhand ganz banaler Sachen zugeteilt. Die Prefetch Möglichkeit ist schon das Maximum an komplexen Funktionen.

Und zu guter letzt hat das OS bzw. der Speichermanager nicht mal den hauch einer Chance eine glückliche Zuteilung für den Cache zu erreichen, darüber entscheided einzig und allein die CPU. So ein Prefetch ist im Endeffekt nicht wirklich anders als ein einfacher Lesezugriff auf den entsprechenden Speicherbereich, dank Read Allocate wird dann eine Cacheline mit den Daten allokiert und was altes fliegt raus.

[DarkAvenger]

So, wieder zurück zu 32 bit und weiterhin ohne Hybridisierung, aber nur einen weiteren Fall abgefangen:

n = 1k average time: 0.0002907
n = 2k average time: 0.0005408
n = 4k average time: 0.0004775
n = 8k average time: 0.0008162
n = 16k average time: 0.0016637
n = 32k average time: 0.0035046
n = 64k average time: 0.0123332
n = 128k average time: 0.0394411
n = 256k average time: 0.0834639
n = 512k average time: 0.136626
n = 1024k average time: 0.162397
n = 2048k average time: 0.278979
n = 4096k average time: 0.451315
n = 8192k average time: 1.09529
n = 16384k average time: 2.91961


Wieder deutlich besser! Oh, ich bin sogar besser als mergesort. ;D

[PuckPoltergeist]

Original geschrieben von intel_hasser
Der Cache gehört desswegen nicht zur Speicherverwaltung, weil der funktional rein garnix beeinflusst.

Es macht nicht den geringsten Unterschied ob eine CPU Cache hat oder nicht - aus Programmierer Sicht ändert das rein garnix. Dazu ist die Cacheverwaltung nicht das was du dir vorstellst - du kannst nicht mal eben 20 Byte Informationen pro Cacheline speichern, das wäre schon viel zu ineffizient. Und der Cache funktioniert nicht fix - der wird dynamisch von der CPU anhand ganz banaler Sachen zugeteilt. Die Prefetch Möglichkeit ist schon das Maximum an komplexen Funktionen.

Und zu guter letzt hat das OS bzw. der Speichermanager nicht mal den hauch einer Chance eine glückliche Zuteilung für den Cache zu erreichen, darüber entscheided einzig und allein die CPU. So ein Prefetch ist im Endeffekt nicht wirklich anders als ein einfacher Lesezugriff auf den entsprechenden Speicherbereich, dank Read Allocate wird dann eine Cacheline mit den Daten allokiert und was altes fliegt raus.

Das OS kann den Cache nicht direkt steuern, so wie den Speicher. Trotzdem werden verschiedene Techniken im Speichermanagement implementiert, um Cache- und TLB-Misses möglichst gering zu halten. Es ist also schon ein gewisses "Cachemanagement" im OS implementiert.

[i_hasser]

Aber die Zeiten sind alles andere als linear ;)

8M: ~1s -> 16M: ~3s

Du nimmst aber schon Zufallslisten, oder? Hast du eigentlich auch mal die Ergebnisse geprüft? Bei mir hatte sich zwischendurch ein dummer Fehler eingeschlichen, da hat er nur 8000 statt 8Mio Zahlen sortiert... das war natürlich schön schnell *chatt*

Wie siehts inzwischen eigentlich mit dem Speicherbedarf aus?
Ich werd jetzt mal bei meinem die Parameter abhängig der gegebenen Daten variieren. Das sollte einiges an Tempo bringen, vor allem bei nicht-8M Listen (darauf hab ich die Parameter handoptimiert, die Relationen werd ich jetzt einfach auf andere Listen übertragen - (max-min) spielt ja auch noch eine Rolle).

[DarkAvenger]

@intel_hasser

Bzgl Linearität siehe weiter oben, dazu habe ich bereits etwas geschrieben. Der Alg ist per se linear (->worst case angucken, das war meine erste Messung). Der average case läuft zwischen best und worst case (bei diesen beiden sieht man die Linearität), darum sieht er nicht linear aus.

Etwas mathematischer:

best case: ~c*n
worst case: ~d*n mit d>c

average case: k(n)*n, mit c<k(n)<d mit (so wie es scheint im Moment) lim k(n)=d

Durch verwendung von mergesort bei den krit Stellen werde ich dem best case näher kommen.

Im Moment fange ich nur (bei der Rekursion) n=1 und n=2 ab. n=3 bis n=128 (geschätzt) sind weiterhin zeitvergeudend...aber man sieht, wie viel alleine n=1 und n=2 ausmachen

Ja, alles Zufall unter AUsnutzng *voller* 32 bit und mache nach jeden Sortieren einen check.

Speicherbedarf ist nur 2*n +4*b. (wobei 4*b=1024*sizeof(long))

[i_hasser]

Ich hab im Moment noch so leichte Probleme mit dem (max-min). Bei kleinen Bereichen ist der Alg unschlagbar.

Für 2^22 (0..4M) mal die Zeiten:

(max-min)=2^22
8M: 0.8s
16M: 1.55s
32M: 3.07s

Bei 2^30 braucht die 4M Variante schon 6.28 Sekunden, bei unangepassten Einstellungen gar 11.16.

Das Interessante dabei: Die großen Zeiten kommen nicht durch das suchen selbst zustande. Der Unterschied bei 2^30 zwischen 4M und 16M ist in etwa dem bei 2^26 (den Werten oben) zwischen 250k und 500k - also praktisch vernachlässigbar.

Ich hab immer eine konstante Zeit drinnen und die richtet sich nach (max-min). Die muss ich wegoptimieren, und mir kommt gerade eine kleine Idee wie das gehen könnte ;D.

[DarkAvenger]

Also unschlagbar würde ich nciht sagen. hier mein Alg mit echten 24 bit:


n = 1k average time: 5.72e-05
n = 2k average time: 9.99e-05
n = 4k average time: 0.0002422
n = 8k average time: 0.0003827
n = 16k average time: 0.0008186
n = 32k average time: 0.0017455
n = 64k average time: 0.0035733
n = 128k average time: 0.0075101
n = 256k average time: 0.0147048
n = 512k average time: 0.0299175
n = 1024k average time: 0.0590768
n = 2048k average time: 0.118041
n = 4096k average time: 0.236241
n = 8192k average time: 0.472362
n = 16384k average time: 0.945041


;D

[i_hasser]

Soll ich mal fieß sein?

2.22 Sekunden für 32M bei 2^16 ;D

Und an der Heuristik arbeite ich noch, die sollte vor allem bei großen Bereichen ordentlich Speed bringen.

Ach ich vergaß ja, 32M Listen sprengen ja deinen Ram... ;D

EDIT: Wenn ich mir das gerade richtig überlege könnte ich mit dem Heuristik-Tree unabhängig von (max-min) werden ;D

[DarkAvenger]

Soll ich mal noch fieser sein?

Mit Kinderkram wie 16bit gebe ich mcih eigentlich nicht ab, also nur wiel du es bist:


n = 1k average time: 0.0001866
n = 2k average time: 0.0002534
n = 4k average time: 0.0003444
n = 8k average time: 0.0004642
n = 16k average time: 0.000656
n = 32k average time: 0.0012681
n = 64k average time: 0.0022833
n = 128k average time: 0.0047332
n = 256k average time: 0.0090926
n = 512k average time: 0.0189122
n = 1024k average time: 0.0399926
n = 2048k average time: 0.0833764
n = 4096k average time: 0.173787
n = 8192k average time: 0.373042
n = 16384k average time: 0.842694
n = 32768k average time: 1.83676
n = 65536k average time: 3.69676
n = 131072k average time: 8.29968


Ich könnte auch noch mit 200M dienen, allerdings müßte ich dann einen schlankeren WM benutzen. ;) Ich bin nur zu ungeduldig um auf 32M+ zu warten, aber prinzipiell ist es kein Problem. Dann gib mir mal 128M. ;D

[i_hasser]

Überprüfst du auch die Ergebnisse?

Zeig mal deine Zufallsgeneratorroutine.

[DarkAvenger]

Nebenbei, was bedeutet bei dir M? 1000^2 oder 1024^2? Bei mir 1024^2....


Ich wiederhole mich evtl, aber JAAAAA ich prüfe. Das lernt man auf der Uni...


lby[0][i].el[0]=(ulong) ((double)rand()/RAND_MAX*4294967295.0);


Zufrieden, der Herr?

[edit] Forensoftware ist Mist und macht Smileys in den COde... :]

[i_hasser]

Ich will aber einen Fehler in deiner Routine finden ;D

Andererseits ist meine Heuristik auch vielversprechend.

[DarkAvenger]

void R8Sort::check()
{
for (long i=1;i<n;++i)
if (lby[0][i].el[0]<lby[0][i-1].el[0]) {
cout<<"check failed!\n";
break;
}
}


Naja, evtl findest du ja einen Fehler in der check Routine. Denn sonst sind Fehler unmöglich. ;)

[DarkAvenger]

So, das wars nun für heute. Gleich ein außerdem ein Spiel...

Tata. :)

[Sargnagel]

Also, ich behaupte mal, daß diese Check Routine nicht viel Aussagekraft hat. Du vergleichst lediglich, ob das aktuelle Element kleiner ist, als sein Vorgänger. Dein Algorithmus kann den letzten Müll in die Liste schreiben; solange die von Deiner Funktion überprüfte Eigenschaft stimmt, wirst Du den Müll nicht bemerken.
Du mußt also die Ausgangsliste mit einem anderen Algorithmus (am besten aus der Standardlibrary) ebenfalls sortieren lassen und dann mit der von Deinem neuen Algorithmus sortierten Liste vergleichen. Nur dann kannst Du 100%ig sicher gehen, daß alles funktioniert wie es soll.


Im Nebenfach Informatik (ja, ich weiß, da lernt man nix :] ) hatte man uns mal eine solche Routine zur Verfügung gestellt, damit wir die Ausgabe des von uns programmierten Bubble Sorts überprüfen konnten. ;D
Ich hatte in meinem Optimierungswahn (das Ergebnis ist mein Sourcecode auf der 1. Seite des Threads) einen winzigen Fehler in den Algorithmus eingebaut. Die Testroutine teilte mir das aber nicht mit, da die Zahlen (war nur Müll drin) aufsteigend sortiert waren. Erst bei einer Exception bemerkte ich, das was faul war. Also, vorsicht mit solchen Tests.

[i_hasser]

Original geschrieben von DarkAvenger

void R8Sort::check()
{
for (long i=1;i<n;++i)
if (lby[0][i].el[0]<lby[0][i-1].el[0]) {
cout<<"check failed!\n";
break;
}
}


Naja, evtl findest du ja einen Fehler in der check Routine. Denn sonst sind Fehler unmöglich. ;)

Entweder versteh ich die Routine nicht so ganz (kenn ja deine Variablen net) oder du hast da einen ganz gewaltigen Fehler drinnen.

lby[0][i].el[0]<lby[0][i-1].el[0]

das müsste

lby[0][i].el[0]!=lby[0][i-1].el[0]

lauten ;)

EDIT:

Ach so hast du das gemacht. Ok. Trotzdem falsch. Möglicherweise lässt dein Alg einfach die Werte unter den Tisch fallen und füllt alles mit 0 auf (so wie meiner vorhin) - dann findet deine Check-Routine nix.
Nimm am besten einen 64bit integer und bilde die Quersumme der Liste.

[i_hasser]

Original geschrieben von Sargnagel
Also, ich behaupte mal, daß diese Check Routine nicht viel Aussagekraft hat. Du vergleichst lediglich, ob das aktuelle Element kleiner ist, als sein Vorgänger. Dein Algorithmus kann den letzten Müll in die Liste schreiben; solange die von Deiner Funktion überprüfte Eigenschaft stimmt, wirst Du den Müll nicht bemerken.
Du mußt also die Ausgangsliste mit einem anderen Algorithmus (am besten aus der Standardlibrary) ebenfalls sortieren lassen und dann mit der von Deinem neuen Algorithmus sortierten Liste vergleichen. Nur dann kannst Du 100%ig sicher gehen, daß alles funktioniert wie es soll.


Da besteht ja doch noch Chance wenn das uns beiden auffällt ;D


Wenn meiner der schnellste ist poste ich den Source.

[DarkAvenger]

OK, ich gebe ja zu, den Fall der böswilligen Veränderung habe ich nciht bedacht, aber ich habe mir hin und wieder bei kleineren Probs die Liste ausgegeben und da war es OK. Außerdem passiert nicht viel voodoo in meinem Alg. ;)

(Wenn er viel Müll schriebn würde, wäre immerhin die Wahrscheinlichkeit vorhanden, daß die Werte flasch sortiert stehen. ;))

Aber gut, werd die check Routine morgen verbessern. Aber bitte nicht die Hoffnung haben, daß mein Alg Mist liefert. ;)

[i_hasser]

Doch *chatt*

(kleiner Scherz)


Nein, mal im Ernst. Dein Alg ist einfach zu schnell. Der dürfte schneller als Bucketsort sein, und das wäre echt 'ne Kunst.


Ich will dir ja keine Angst machen, aber bei mir haben da auch die 1. 8000 Zahlen gestimmt. Hatte mich schon gefreut und dann hats auf einmal nur noch 0en gehagelt.

[DarkAvenger]

So Halbzeit. :) Ne dumme Frage: Wie mach ich mir eine 64 Bit Var unter gcc (oder gibt es was standarisierted)? (im obigen Bsp hatte ich einfach ein 2er array aus 32 bit genommen, muß ja nichts mit gerechnet werden...)

[i_hasser]

Schade. Die Heuristik macht das zwar in großen Bereichen schneller, in kleinen aber langsamer :(.

... Ich werd nie lernen. Ich werd es echt nie lernen. Wiedermal DEBUG Code *chatt*

Hat ein bisschen was gebracht. Aber nicht wirklich viel - bei Listen in kleinen Bereichen mit vielen Elementen (ab vielleicht (max-min)/n~16--) dürfte die Heuristik sogar deutlich bremsen.
Andererseits hats der Alg sowieso mit homogen verteilten Listen, und bei nicht homogen verteilten Listen wirkt die Heuristik wahre Wunder.


... schön, die Heuristik hat das alles nur langsamer gemacht (auch bei großen max-min). Hab also die letzte 3/4 Stunde umsonst mein Hirnschmalz verschwendet, den Code hab ich eben wieder rausgelöscht :[


EDIT: 64bit int in gcc: "long long int xyz;"

[DarkAvenger]

Hmm, das mit long long int klappt nicht wirklich. sizeof liefert mir zwar 8 byte, aber 1<<32 geht etwa nicht oder (1<<31)*4 liefert 0 bzw is true bei ==0. Was isn' das???

[i_hasser]

Integerwerte sind 32bit.

Also dann musst du schon sowas schreiben (ist ein bissel aufwändig ich weis):

(long long int)1<<(long long int)32

Vielleicht (imho müsste) das klappen: 1L<<32L (großes L -> long long int)

[DarkAvenger]

Ah OK, klappt jetzt. Das mit dem L ging nicht, aber das explizite casting.

Oh, man muß *2* L dranhängen, also 1LL<< blah geht. Das muß man auch erst einmal wissen...

[i_hasser]

Tja - kann sein. 64bit ints braucht man ja auch nur extrem selten.

Und? Wie siehts aus?

[PuckPoltergeist]

Mal eine Frage an die beiden Optimierungs-Helden ;)

Welche Anforderungen stellt ihr denn an die zu sortierenden Datensätze?

[DarkAvenger]

Ok, hattest recht, war ein kleiner Fehler drin, aber nicht laufzeitrelevant. Gefixt und alles beim alten (bzgl speed) und Quersumme stimmt auch. ;D

Wie gesagt, es ist noch einiges an Potential drin...

@Puck

Was genau meinst du mit "Anforderungen"?

[i_hasser]

Original geschrieben von PuckPoltergeist
Mal eine Frage an die beiden Optimierungs-Helden ;)

Welche Anforderungen stellt ihr denn an die zu sortierenden Datensätze?

Meiner ist noch relativ bereichssensibel und es müssen Integer sein (wäre ansich auch mit floats in engen Bereichen machbar).

Die Listenlänge kann dafür nahezu belieben sein, die Laufzeit verhält sich leicht unterlinear (für n->unendlich geht die Laufzeit gegen O=n oder andersherum die Laufzeit beträgt ungefähr O=a+n).

Die Verteilung spielt an sich keine Rolle, allerdings läuft der Alg schneller wenn es nicht-homogen ist - die Laufzeit beträgt aber immer O=n oder besser gesagt O=an wobei a bei nicht-homogenen Listen kleiner ist.

[i_hasser]

@DarkAvenger

Ist bei dir O eigentlich auch im Worst Case linear?


Ich hab jetzt nicht mehr wirklich Lust (und Zeit sowieso nicht :P), desswegen gibts jetzt meinen Source.




Fangen wir harmlos an - die main():

int main(int argc, char *argv[])
{
int i;

srand(1234);

// create a random list
int list_size=4*1<<20;
int* list=new int[list_size];
for(i=0;i<list_size;i++) list[i]=rand()>>5;

newsort3(list, list_size, 1<<26);

cout << endl << "succ" << endl;
return EXIT_SUCCESS;

newsort3 ist die Sortierfunktion. Der 3. Parameter hat übrigens nichts mit min/max zu tun, sondern gibt nur die obere Bereichsgrenze an.


int newsort3(int* list, int list_length, int rmax)
{
int i,j,k,l,m;
clock_t t1,t2;
t1=clock();

// Create Area Chains
int vl0_min=0;
int vl0_max=rmax;
int vl0_size=65536; // not easy to determine, L2 dependand
int vl0_count=(vl0_max-vl0_min)/vl0_size;
int vl0_llistlen=256;
VListChain** vl0=new VListChain*[vl0_count];
for(i=0;i<vl0_count;i++) vl0[i]=new VListChain(vl0_llistlen);


So fängt die Sortierfunktion an. An sich ist der Alg ziemlich einfach gestrickt.

Die Idee dahinter ist ein stinknormaler Bucketsort (oder wie auch immer der Alg nun heist) - also wir nehmen ein Array[0..max] und rechnen für alle Listenelemente array[liste[i]]++;, zum Schluss tragen wir array in einer neuen Liste ab.

Bei großen Bereichen hat das ja den Nachteil, dass array ziemlich groß wird und sich praktisch nicht mehr realisieren lässt.

Also teilen wir den Bereich in kleinere Teilbereiche ein - und zwar mit der Größe vl0_size (die 0 kommt nur aus historischen Gründe, ursprünglich hab ich das mal als multilayer Geschichte geplant).
Hier sind die Bereiche also 64K groß.

Für jeden dieser Bereiche legen wir eine verkettete Liste an (im Alg hab ich das ziemlich verändert und es ist ein mix aus staticher und verketteter Liste, das ist viel und spart haufenweise Speicher aber die Funktionalität ist die Selbe).

// Transscript to vl0 and sort into right area arrays
for(i=0;i<list_length;i++)
{
j=list[i]/vl0_size; // index of vl0 to use
vl0[j]->attach(list[i]);
}

Jetzt gehen wir die zu sortierende Liste (ich nenn das Ding jetzt einfach mal list) 1mal durch und hängen an die für den Bereich in den der Wert der liste (also list[i]) fällt zuständige verkettete Liste diesen Wert an (das Anhängen dauert eine konstante Zeit).

// walk through vl0s and count values
//int* list2=new int[list_length]; // list of sorted Data
int list2_pos=0;

// Value-Mapped counting array
int* acount=new int[vl0_size]; // counting array

int offset;
VListIter* vl_iter=new VListIter();

// Iterate through lists
for(i=0;i<vl0_count;i++)
{


Jetzt kommt nur ein bisschen Variablenkrempel und die beginnende wichtigste Schleife.
Die Bereiche sind jetzt klein genug als das wir die mit einem ordinären BucketSort sortieren können, und der braucht ja nur lineare Zeit.
acount ist das Array für den BucketSort.

vl_iter ist übrigens nur eine Hilfsklasse für den Zugriff auf die verkettete Liste (VList ist die verkettete Liste, VListChain enthält eine verkettete Liste und stellt Funktionen wie einfügen neuer Elemente zur Verfügung und VListIter stellt Funktionen bereit um möglichst schnell die Daten der Liste von vorne bis hinten auszulesen).

offset=i*vl0_size;


// don't do anything if this vl0 doesn't contain anything
if(vl0[i]->chain_length==0) continue;

// set iterator
vl_iter->set_on_list(vl0[i]->get_first());

// reset counting array and Heuristik Tree
for(j=0;j<vl0_size;j++) acount[j]=0;

// Transcript unordered Data to Value-Mapped Array
//
while(vl_iter->sure_count()!=0)
{
k=vl_iter->sure_count();
for(j=0;j<k;j++)
{
// account value
l=vl_iter->get_next()-offset;
acount[l]++;
}
}


So, ich fang oben mal an. offset sagt uns um wieviel wir den acount-Index nach oben verschieben müssen um die eigentliche Zahl zu erhalten. acount hat ja immer 64k Elemente und vl0[...] entscheided für welchen Bereich acount nun eigentlich zählt.

Danach überspringen wir diesen Bereich wenn er garkeine Werte enthält. Irritierenderweise ist chain_length aber nicht die Anzahl der enthaltenen Werte sondern 0 wenn keine Werte drinnen sind oder !=0 wenn Werte drinnen sind (liegt daran, dass ich das irgendwann mitten drinnen alles umgestellt hab von rein verketteten Listen auf einen Mix aus statischen und verketteten Listen).

Danach setzen wir den Iterator auf den 1. Wert und es kann losgehen, nachdem wir acount auf 0 gesetzt haben. Die Sache im Kommentar mit dem Heuristik Tree ist überflüssig, den hab ich ja wieder rausgelöscht.

Dann gehen wir alle Werte in der verketteten Liste durch und tragen die in acount ein. Ist etwas undurchsichtig - da die VList statisch/dynamisch sind können wir über einen kleinen Raum sicher sagen wieviele Werte enthalten sind. Danach muss der iterator den nächsten Eintrag raussuchen und dann können wir wieder über einen kleinen Raum (der übrigens durch int vl0_llistlen am Anfang festgelegt wird) sagen wieviele Werte drinnen sind.

sure_count() ist ziemlich vielseitig - sagt uns erstmal wieviele Elemente wir mindestens noch mit get_next() auslesen können. Also nach jedem get_next() ist sure_count um eins kleiner.
Theoretisch würde sure_count nachdem alle sicheren Elemente ausgelesen sind 0 zurückgeben - das fängt der iterator ab und guckt nach ob es noch mehr Elemente in der verketteten Liste gibt. Wenn ja setzt er sich selbstständig auf das nächste Element und sure_count gibt statt 0 wieder die Anzahl der sicheren Elemente in der nächsten Liste zurück.

Gibts kein nächstes Element in der verketteten Liste gibt sure_count 0 zurück und wir können aufhören.

// Walk through Value-Mapped Array and add values to sorted list
//
for(j=0;j<vl0_size;j++)
{

if(acount[j]!=0)
{
for(k=0;m<acount[l];k++) list[list2_pos+k]=offset+j;
list2_pos+=acount[j];
}
}
}


Und das hier überträgt acount in die neue, sortierte Liste... naja, das hat es früher mal getan. Jetzt überschreibt es einfach die übergebene Liste, braucht weniger Speicher (und wenn man die unsortierte Liste wirklich noch brauchte kann man vor dem Aufruf der Sortierfunktion eine Kopie erstellen).

Daher auch list2_pos und nicht list_pos.

Tja, und das wars schon.

Schwachpunkt ist, dass wir auf die eine oder andere Art (max-min)mal auf acount zugreifen müssen (hier eben (max-min)/65536mal von 0 bis 65536 statt gleich von 0 bis (max-min) beim einfachen BucketSort).
Und wächst der Bereich eben zb. auf 2^32 sind das 4 Milliarden Zugriffe, bei 2.2 Milliarden Takten die mein Athlon pro Sekunde ackert dauert das ziemlich lange.

Aber die Zeit ist wenigstens fix - egal wie lang die Liste ist.


Nochwas zum Speicherbedarf der einzelnen Klassen: VList gönnt sich vl0_llistlen*4+16 Bytes und speichert dabei vl0_llistlen Elemente.

VListChain begnügt sich mit 16 Bytes (enthält aber je nach Menge xyz VLists).


@DarkAvenger

Jetzt will ich aber auch deinen sehen ;D

[DarkAvenger]

@intel_hasser


Ja mein Vf ist im worst-case linear, nur wird der Vorfaktor recht groß.

Bzgl Source, weiß ich noch nicht. Mittlerweile gefällt mir mein Vf so gut, daß ich es evtl in meiner Diplomarbeit unterbringen kann. (Da benutzte ich mergesort mit floats.) Darum müßte ich mich erkundigen, ob ich sowas vorher veröffentlichen darf oder ob es sonst Probs gebe.

Nur, sobald ich diese eingereicht habe, werde ich den Source veröffentlichen, was aber bis zu 1 Monat dauern könnte (bin eigentlich fast durch).

Ansonsten könnte man mein Vf auch recht einfach nachbauen, habe ja die Theorie dazu erklärt. ;)

[DarkAvenger]

So, habe den Alg hybridisiert. Folg Messung ist für Übernahme von mergesort für n<=64:

(32bit Zahlen, zufällig verteilt)


Start
n = 1k average time: 6.53e-05
n = 2k average time: 0.0001395
n = 4k average time: 0.0002959
n = 8k average time: 0.0006325
n = 16k average time: 0.001559
n = 32k average time: 0.0024345
n = 64k average time: 0.0047698
n = 128k average time: 0.010381
n = 256k average time: 0.0240621
n = 512k average time: 0.0535796
n = 1024k average time: 0.115388
n = 2048k average time: 0.247241
n = 4096k average time: 0.522403
n = 8192k average time: 0.972613
n = 16384k average time: 1.95153



Hier nochmal eine Vergleichsmessung ohne mergesort:


n = 1k average time: 0.0003239
n = 2k average time: 0.0004897
n = 4k average time: 0.0005332
n = 8k average time: 0.0007529
n = 16k average time: 0.0014799
n = 32k average time: 0.003838
n = 64k average time: 0.013916
n = 128k average time: 0.0443731
n = 256k average time: 0.095386
n = 512k average time: 0.137215
n = 1024k average time: 0.180845
n = 2048k average time: 0.274442
n = 4096k average time: 0.495714
n = 8192k average time: 1.09581
n = 16384k average time: 2.93204


Man sieht, daß der Hybrid nicht immer schneller ist, aber bei 16M scheint der bis jetzt *immer* schneller zu sein, denn ich hatte ohne immer knapp 3sec, mit aber immer knapp 2sec.

Evtl müßte man auch mit dem Einsprungwert von mergesort experimentieren.

Der profiler zeigt nun eine ziemlich Gleichverteilung über die Routinen, dh. hier wäre nciht mehr viel rauszuholen. Was ich noch probieren könnte, wäre b=16 auszutesten.


Hier nochmal n<=32:


n = 1k average time: 6.63e-05
n = 2k average time: 0.0001401
n = 4k average time: 0.000305
n = 8k average time: 0.0007907
n = 16k average time: 0.0017771
n = 32k average time: 0.002318
n = 64k average time: 0.0047384
n = 128k average time: 0.0103069
n = 256k average time: 0.0243671
n = 512k average time: 0.053777
n = 1024k average time: 0.115433
n = 2048k average time: 0.288916
n = 4096k average time: 0.543281
n = 8192k average time: 0.971605
n = 16384k average time: 1.94871



Ach ja, mir ist bei der Gelegenheit ein bug im mergesort Alg aufgefallen, der sich aber nur bei n!=2er Potenz zeigt. Werde das in den Sourcen später fixen.

[DarkAvenger]

interessanter link:

http://www.sortieralgorithmen.de/radixsort/index.html

Hier werden fast alle Sortiervf erläutert. Offensichtlich (wie vermutet) habe ich Radixsort implementiert mit der Abwandlung des Hybriden. Ich habe mir die Varianten nicht angeguckt, evt kommt es sogar vor. Naja, evtl reicht es doch für einen Absatz in meiner Diplomarbeit. ;)

Der Autor spricht davon, daß AVL Sort optimal sein soll. Nun, ich kenne AVL Bäume und weiß, daß diese perfekt balancieren und immer log(n) Laufzeit für die Wörterbuchop. bieten. Nur sind diese Op bisweilen kompliziert zu implementieren (ich hatte mal einen einfach AVL implementiert). Evtl könnte ich meine damalige Impl. noch benutzen, denn delete braucht man nicht, denn wenn ich mich recht erinnere, hat man bei delete Haarausfall bekommen...

Ich kann mir aber nicht vorstellen, daß AVL Sort schneller als Mergesort ist, da die Op an sich mehr Zeit benötigen, AFAIK.

[PuckPoltergeist]

Original geschrieben von DarkAvenger
Ich kann mir aber nicht vorstellen, daß AVL Sort schneller als Mergesort ist, da die Op an sich mehr Zeit benötigen, AFAIK.

Du mußt immer unterscheiden zwischen dem Algorithmus und einer Implementierung.

Dazu sollte man vielleicht noch anmerken, dass Quicksort mitunter deutlich schneller ist als Mergesort. Es hat aber das Problem, dass es nicht stabil ist, weshalb man seinen Ansatz immer gut abwägen sollte. Mergesort hat dazu halt noch den Vorteil, dass es eines der am besten untersuchten Sortierverfahren ist.

[DarkAvenger]

Das "schneller" rührt max aus dem Unterschied der Speicherplatzverwendung.

AVL, Quicksort sollten in-situ arbeiten, was sich dann bemerkbar macht, wenn man bei sehr großen Listen swappen muß. Da würde dann mergesort kläglich eingehen.

Ich meine auch die Unterschiede bei den Alg an sich. Ich bin mir sicher, daß die Konst vor log(n) bei AVL größer ist als bei mergesort, was den Rechenaufwand angeht. Da kann auch die beste Impl, nicht viel rausholen. mergesort ist einfach, AVL ist es nicht. Wie gesagt kann nur der 2*n Speicherverbrauch mergesort zum Verhängnis werden.

Quicksort ist halt schwer zu analysieren, wegen der worst case O(n^2) Geschichte, aber wegen \Theta(n*log(n)) *könnte* es halt im average mergsort schlagen.

Nach etwas Nachdenken: Ich kann mir eigentlich nicht vorstellen, daß die in-situ Variante von Quicksort schneller als mergesort ist:

Man stelle sich das Vf auf einer HD vor: SO wie ich es kenne, wir das Pivot ans Ende der Liste geschrieben und dann die <= und > and den Anfang bzw ans Ende geschrieben (durch Austauschen der El). Dabei würde der HD-Kopf permanent hin und herklackern.

Mergesort dagegen shcriebt die Ausgabe recht sequentiell, so daß durch die cache Stufen dieses in einen Rutsch erledigt werden kann. (das Lesen ist dagegen nciht besser als bei quicksort).

Also um den Durchsattz zu ereichen, müßte man quicksort auch (zwei) seperate Ausgabepuffer spendieren, die dann sequentiell abgearbeitet werden. Nur dann wäre der Vortiel gegenüber mergesort dahin.

Ich *glaube* (bin kein Experte) daß im Rechner selbst, die mehrstufige Verwaltung cache eher mit sequentiellen Daten als mit zufälligen klar kommt.

Naja, im Zweifelsfall müßte man mal quicksort implementieren und testen, wobei hier die Pivotstartegie sher wichtig wäre... :]

[DarkAvenger]

Ich habe nochmal über AVL nachgedacht:

Also den Baum aufzubauen, könnte wirklich schneller sein, da folg gilt:

Mergesort geht ja log(n) mal durch die Liste => log(n) * n


Beim AVL gilt dagegen: Einfügen in den AVL Baum kostet log(n), wobei hier aber der Baum erst aufgebaut wird, dh. es gilt *nicht* n*log(n), sonder \Sum_{k=1}^{n-1} log(k), was mehr oder minder deutlich kleiner als n*log(n) ist. Kann das jemand etwas besser abschätzen? :)

Um aus dem Baum wieder ein sortiertes array zu bekommen, könnte man DFS bemühen, was in O(n) erledigt wäre.

[PuckPoltergeist]

Original geschrieben von DarkAvenger
Ich meine auch die Unterschiede bei den Alg an sich. Ich bin mir sicher, daß die Konst vor log(n) bei AVL größer ist als bei mergesort, was den Rechenaufwand angeht. Da kann auch die beste Impl, nicht viel rausholen. mergesort ist einfach, AVL ist es nicht. Wie gesagt kann nur der 2*n Speicherverbrauch mergesort zum Verhängnis werden.

Konstanten werden bei der Betrachtung des Algorithmus grundsätzlich nicht einbezogen, weil sie nichts am Laufzeitverhalten ändern. Hier ist wirklich nur die Skalierbarkeit von Interesse. Ob es nun 2*n oder 3*n ist juckt dabei nicht weiter, es ist alles n.

[DarkAvenger]

Jein, sobald du es auf dem Computer hast, wird die Konstante wieder wichtig. :)

Sonst wäre ja auch nach deiner Argumentation Quicksort nie schneller als Mergesort, was sich mit deiner vorherigen Behauptung widerspricht...

[PuckPoltergeist]

Original geschrieben von DarkAvenger
Jein, sobald du es auf dem Computer hast, wird die Konstante wieder wichtig. :)

Sonst wäre ja auch nach deiner Argumentation Quicksort nie schneller als Mergesort, was sich mit deiner vorherigen Behauptung widerspricht...

Hat aber nichts mit der Komplexität des Algorithmus zu tun, und somit auch nichts mit der O-Notation. Die sagt ja nur etwas darüber aus, wie sich der Algorithmus im Bezug auf die Anzahl der zu bearbeitenden Elemente verhält.

[DarkAvenger]

Das ist mir schon klar...

Die O \Theta \Omega Notation sind nur grundsätzlich für die Entwicklung von Algorithmen vom theor. Standpunkt interessant. Sobald man aber implementiert, muß man abwiegen...

[DarkAvenger]

Ich habe mal den Radixsort für b=2 implementiert und zwar in-situ (geht ja, da ähnlich wie quicksort), d.h. benutzt nur n Speicher. Die Routine ist zwar ncoh leicht fehlerhaft, aber habe mal Zeiten gemessen und die sind gar nciht gut... etwa 2-4x langsamer als meine Messung von dem Radix b=256 Hybrid.

Ich weiß nciht, ob das an dem Fehler liegt oder das generell keine gut Idee ist. Obiger link empfiehlt eigentlich für Zahlen b=2 zu benutzen. Naja, ich bin jedenfalls nciht begeistert... Mal sehen, ob ich den debugge. Wenn nicht, were ich diesen hier evtl posten, damit jemand anders auf Fehlersuche gehen kann, falls er will. ;)

[DarkAvenger]

So, habe doch (mit minimalen fix) meinen getunten Radixsort für b=2 hinbekommen. Hier die Sourcen. Das Vf ist nun knapp halb so schnell bei mein Vf für b=256 + Hybriden, aber hat den Vorteil, daß es keinen zusätzlichen Speicher benötigt.

Der Trick hier wird mit der Definition von BITCHECK aktiviert, der fast die Ausführungszeit halbiert. Ansonsten, wer Lust und Laune hat, kann ja mal probieren zu tunen. Am meisten läßt sich evtl. wieder durch Hybridisierung rausholen, denn ab Folgengröße von 3 wird rekursiv sortiert, wodurch schlimmstenfalls #bits weitere Durchgänge ausgelöst werden. Hier würde sich quicksort anbieten, wobei man den Einstiegspunkt vom (rekursiven) n und den verbleibenden erwarteten Rekursionen abhängig machen sollte.

Aktuelle Zeiten:


n = 1k average time: 0.0001023
n = 2k average time: 0.0002188
n = 4k average time: 0.0004783
n = 8k average time: 0.0011265
n = 16k average time: 0.0021479
n = 32k average time: 0.0047369
n = 64k average time: 0.010029
n = 128k average time: 0.020614
n = 256k average time: 0.0441157
n = 512k average time: 0.0916417
n = 1024k average time: 0.193906
n = 2048k average time: 0.408597
n = 4096k average time: 0.854637
n = 8192k average time: 1.78735
n = 16384k average time: 3.73418


Auch wenn es nicht ganz so aussieht, ist das Vf linear, nur das Tuning ist es halt nicht. ;)

Hier der code, der sich für bel Integer eignen sollte:

types.h

#ifndef TYPES
#define TYPES

typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned long ulong;

#endif


r1sort.h

/***************************************************************************
* Copyright (C) 2004 by Dark Avenger *
* darkav *at* gmx *dot* net *
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License for more details. *
* *
* You should have received a copy of the GNU General Public License *
* along with this program; if not, write to the *
* Free Software Foundation, Inc., *
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
***************************************************************************/
#ifndef R1SORT
#define R1SORT

#include "types.h"

#include <iostream>
#include <cmath>

using namespace std;

#define BITCHECK

template <class T> class R1Sort {
public :
R1Sort(ulong n);
~R1Sort();

void sort();

void generate();
void check();

private:
void recsort(ulong start, ulong end, long bit);

T *list;
ulong n;
ulong nbits;

T *bitlist;
long long int sum;
};

template <class T> R1Sort<T>::R1Sort<T>(ulong n)
{
this->n=n;
list=new T[n];
nbits=sizeof(T)<<3;
bitlist=new T[nbits];

for (ulong i=0;i<nbits;++i) bitlist[i]=((T)1<<i);

srand ( time(NULL) );
}

template <class T> R1Sort<T>::~R1Sort()
{
delete[] list;
delete[] bitlist;
}

template <class T> void R1Sort<T>::sort()
{
recsort(0,n,nbits-1);
}

template <class T> void R1Sort<T>::generate()
{
double maxval=pow(2,(double)nbits)-1;

sum = 0LL;
for (ulong i=0;i<n;++i) {
list[i]=(T) ((double)rand()/RAND_MAX*maxval);
sum+=(long long int)list[i];
}
}

template <class T> void R1Sort<T>::check()
{
long long int sumres=(long long int)list[0];
long i;

for (i=1;i<n;++i) if (list[i]<list[i-1]) {
cout<<"order failed!\n";

cout<<(T)list[i-1]<<" "<<(T)list[i]<<endl;
break;
}

for (i=1;i<n;++i) sumres+=(long long int)list[i];

if ((i==n)&&(sum!=sumres)) cout<<"sum failed!\n";
}


template <class T> void R1Sort<T>::recsort(ulong start, ulong end, long bit)
{
ulong ia=start,ib=end-1;
T temp;

T setbits=(T)0;
while (ia<ib) {
if ((list[ia]&bitlist[bit])&&!(list[ib]&bitlist[bit])) {//swap
#ifdef BITCHECK
setbits|=list[ia];
setbits|=list[ib];
#endif
temp=list[ia];
list[ia]=list[ib];
list[ib]=temp;
}

while (!(list[ia]&bitlist[bit])&&(ia<ib)) {
#ifdef BITCHECK
setbits|=list[ia];
#endif
++ia;
}
while ((list[ib]&bitlist[bit])&&(ia<ib)) {
#ifdef BITCHECK
setbits|=list[ib];
#endif
--ib;
}
}
#ifdef BITCHECK
setbits|=list[ia];
setbits|=list[ib];
#endif

if ((ia==end-1)&&!(list[ia]&bitlist[bit])) ++ia;
//now ia = #elemnts with msb=0

#ifdef BITCHECK
for (--bit;!(setbits&bitlist[bit])&&(bit>-1);--bit);
#else
--bit;
#endif
//found used bit
if (bit<0) return;

if (ia>start+2) recsort(start,ia,bit);
else if ((ia>start+1) && (list[start+1]<list[start])) {
T temp=list[start];
list[start]=list[start+1];
list[start+1]=temp;
}

if (ia+2<end) recsort(ia,end,bit);
else if ((ia+1<end) && (list[ia+1]<list[ia])) {
T temp=list[ia];
list[ia]=list[ia+1];
list[ia+1]=temp;
}
}

#endif

[DarkAvenger]

Hier ein Durchlauf mit 16bit Zahlen:


n = 1k average time: 0.0001122
n = 2k average time: 0.0002357
n = 4k average time: 0.0005037
n = 8k average time: 0.0013268
n = 16k average time: 0.0022919
n = 32k average time: 0.0048055
n = 64k average time: 0.0097773
n = 128k average time: 0.0193534
n = 256k average time: 0.0364086
n = 512k average time: 0.0718577
n = 1024k average time: 0.141925
n = 2048k average time: 0.285398
n = 4096k average time: 0.574954
n = 8192k average time: 1.15444
n = 16384k average time: 2.32785