Warum ist die Laufzeit bei Bubblesort nicht gleich steigend?

Dizzy_Ti · 23.06.2004

Hi,
hier erstmal der Quellcode zum sortieren:

Code:

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 · 23.06.2004

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:

Code:

       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:

Code:

       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 · 24.06.2004

Wie intel_hasser schon schrieb, ist Bubblesort ein Algorithmus mit quadratischer Komplexität. Hier 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:

PHP:

#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 · 24.06.2004

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 · 24.06.2004

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

Duff ist eben allgegenwärtig

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

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 · 24.06.2004

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]++;".
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

Sargnagel · 24.06.2004

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.

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.

i_hasser · 24.06.2004

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

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 · 24.06.2004

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

i_hasser · 24.06.2004

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 · 24.06.2004

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

).

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

i_hasser · 24.06.2004

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 · 24.06.2004

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

.

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 · 24.06.2004

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 · 24.06.2004

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 · 24.06.2004

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.

i_hasser · 24.06.2004

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

).

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

i_hasser · 24.06.2004

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

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:

Code:

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 · 24.06.2004

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

).

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 · 25.06.2004

Sortierverfahren, die auf paarweisen Schlüsselvergleichen beruhen *können* nicht schneller als n*log

sein. (Schreibweise \Omega(n*log

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

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 · 25.06.2004

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

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 · 25.06.2004

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

)

i_hasser · 25.06.2004

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 · 25.06.2004

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 · 25.06.2004

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

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

Warum ist die Laufzeit bei Bubblesort nicht gleich steigend?

Vice Admiral Special

Grand Admiral Special

Commodore Special

Grand Admiral Special

Commodore Special

Grand Admiral Special

Commodore Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Commodore Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Commodore Special

Grand Admiral Special

Ähnliche Themen