qsort frage

Nexus

lord_fritte schrieb:

Das habe ich bei meiner Klasse eingebaut.

Mit linearer Zeitkomplexität? Keine gute Idee. Das ist auch der Grund, warum std::list das nicht bietet. Hier wären Iteratoren die bessere Wahl...

Nexus schrieb:

ich teste das so:

Arbeitest du im Release-Modus mit eingeschalteten Optimierungen und deaktivierter Debug-Laufzeitumgebung? Und falls du MSVC++ verwendest: hast du das Makro _SECURE_SCL mit 0 definiert?

Und hast du auch die Reihenfolge der beiden Listen vertauscht und viele Durchgänge gestartet? Nebendran keine Programme am Laufen? Einigermassen stabile Rechenleistung? Profiling kann von sehr vielen Faktoren abhängen, deshalb würde ich mit voreiligen Schlüssen etwas warten.

lord_fritte

hmm aber er misst doch nur immer wieder den Add vorgang, aber was bringt mir eine Liste in der ich Daten speichere wenn ich keinen direkten Zugriff auf die Elemente habe?

Don06

Direkten Zugriff hast du sowieso nie. Entweder du gehst über einen operator [] oder über Iteratoren.

Übrigens hat Nexus Recht. Es ist eher unwahrscheinlich, dass du in der Lage warst eine performantere Liste zu programmieren, als die über Jahre hinweg optimierte std::list. Die Container in der Standard-Library beim MSVC haben noch Laufzeitüberprüfungen, die man zur Not abschalten kann. Eigentlich sind sie aber recht sinnvoll und auch hilfreich. Deine Laufzeitmessung solltest du auch noch einmal überdenken. Miss die Laufzeit von 10.000 push_back()s und nicht von jeweils einem und addiere die Ergebnisse.

Gruß
Don06

man kann eine verkettete liste nicht mit quicksort sortieren. für die neu-zuordnung des 'next-zeigers' etc ist qsort nicht vorgesehen.

nachtrag:
für verkettete listen, nimmt man 'sortieren durch einfügen' bzw. insertion sort.
ist das gleiche in grün, nur auf englisch.
guckst du:
http://moritz.faui2k3.org/de/dmisc/einfach-verkettete-listen

Tachyon

Guck Dir vielleicht auch mal diesen Animationsfilm an. Der erklärt recht anschaulich Quicksort und Bubblesort im Vergleich (wurde vor kurzem mal im ANSI-C-Forum gepostet).

Nexus

lord_fritte schrieb:

hmm aber er misst doch nur immer wieder den Add vorgang, aber was bringt mir eine Liste in der ich Daten speichere wenn ich keinen direkten Zugriff auf die Elemente habe?

Wenn du direkten Zugriff (Random Access) willst - d.h. du möchtest auf das 153. Element zugreifen, ist eine verkettete Liste die falsche Datenstruktur. Falls du den operator[] nachbauen willst, hast du O(n) - du musst 152 Mal ein Element weitergehen, bevor du das gesuchte Element hast. Nun stell dir eine Liste mit 25 Millionen Einträgen vor und du willst auf das 24-millionste Element zugreifen. Nicht gerade optimal.

Deshalb gibt es Iteratoren. Die kannst du dir wie Zeiger vorstellen, die auf jeweils ein Element zeigen. Du kannst sie vorrücken, um an das nächste Element zu gelangen. Das ist vor allem sinnvoll, wenn du für alle Elemente der Liste etwas tun willst, und nicht ein einzelnes.

Ansonsten - im Fall, dass du Random Access brauchst - nimm eine array-ähnliche Datenstruktur. In der Standardbibliothek wären das std::vector und std::deque .

lord_fritte

x schrieb:

man kann eine verkettete liste nicht mit quicksort sortieren. für die neu-zuordnung des 'next-zeigers' etc ist qsort nicht vorgesehen.

Dessswegen ja ein eignes qsort

Nexus schrieb:

lord_fritte schrieb:

hmm aber er misst doch nur immer wieder den Add vorgang, aber was bringt mir eine Liste in der ich Daten speichere wenn ich keinen direkten Zugriff auf die Elemente habe?

Wenn du direkten Zugriff (Random Access) willst - d.h. du möchtest auf das 153. Element zugreifen, ist eine verkettete Liste die falsche Datenstruktur. Falls du den operator[] nachbauen willst, hast du O(n) - du musst 152 Mal ein Element weitergehen, bevor du das gesuchte Element hast. Nun stell dir eine Liste mit 25 Millionen Einträgen vor und du willst auf das 24-millionste Element zugreifen. Nicht gerade optimal.

Deshalb gibt es Iteratoren. Die kannst du dir wie Zeiger vorstellen, die auf jeweils ein Element zeigen. Du kannst sie vorrücken, um an das nächste Element zu gelangen. Das ist vor allem sinnvoll, wenn du für alle Elemente der Liste etwas tun willst, und nicht ein einzelnes.

Ansonsten - im Fall, dass du Random Access brauchst - nimm eine array-ähnliche Datenstruktur. In der Standardbibliothek wären das std::vector und std::deque .

Aber das selbe habe ich bei einem Iterator doch auch... wenn ich an das Element 150 will, muss ich 150 nal durch alle Elementer gehen...

Nur ich habe eine doppelverkette Liste, ich teile diese Virtuell in der mitte.
Z.b. n Elemente, ich möchte an Element x, dann überprüfe ich:
x < n/2: laufe ich von vorne durch,
x > n/2: laufe ich von hinten durch.
Und jetzt erzählt mir nicht dass eine eine einfache if abfrage 100.000 ms braucht...

unskilled

lord_fritte schrieb:

Nur ich habe eine doppelverkette Liste, ich teile diese Virtuell in der mitte.
Z.b. n Elemente, ich möchte an Element x, dann überprüfe ich:
x < n/2: laufe ich von vorne durch,
x > n/2: laufe ich von hinten durch.
Und jetzt erzählt mir nicht dass eine eine einfache if abfrage 100.000 ms braucht...

und jz rate mal, welche Laufzeit den op[] jz hat? richtig - O(n)
mal davon abgesehen, dass man (mit an sicherheit grenzender wahrscheinlichkeit), wenn man den op[] bei einer list braucht, eh den falschen container verwendet hat...

und wieso meinst du, dass dein qsort dann schneller ist, als das std::list::sort ist? Oo
und wenn du ne list geordnet haben möchtest, dann gibt es auch wieder andere container...
du hast iwie scheinbar nicht verstanden, dass jeder container nur bestimmte anwendungsgebiete besitzt...

bb

Nexus

lord_fritte schrieb:

Aber das selbe habe ich bei einem Iterator doch auch... wenn ich an das Element 150 will, muss ich 150 nal durch alle Elementer gehen...

Ja. Iteratoren verbessern deinen Index-Zugriff aber trotzdem, weil du beim Durchiterieren aller Elemente quadratische zu linearer Zeitkomplexität reduzieren kannst. Das Problem des Random Access ist bei Listen unumgänglich - aber zum Glück gibt es auch noch andere Datenstrukturen.

Dein operator[] braucht etwa n Rechenschritte, wenn du auf das n-te Element zugreifen willst. Möchtest du nun durchiterieren, greifst du auf jedes Element vom ersten bis zum letzten in der Liste zu - bei m Elementen also m-mal. Jeder dieser Zugriffe benötigt aber wiederum n Schritte. Das führt dazu, dass die Anzahl totalen Rechenschritte quadratisch von der Listengrösse abhängt, was sehr ineffizient ist.

Der Iterator hingegen benötigt nur m-mal für das Durchiterieren, da er jedes Mal direkt weitergesetzt werden kann. Also hast du eine lineare Abhängigkeit.

lord_fritte schrieb:

Nur ich habe eine doppelverkette Liste, ich teile diese Virtuell in der mitte.

Wie willst du die Mitte treffen, wenn du keinen Random Access hast?

unskilled

Nexus schrieb:

lord_fritte schrieb:

Nur ich habe eine doppelverkette Liste, ich teile diese Virtuell in der mitte.

Wie willst du die Mitte treffen, wenn du keinen Random Access hast?

lies seinen post ma noch ma - er meinte es anders ^^
er hats net wirklich getrennt, aber er speichert die länge noch extra mit und pürft dann halt, von welcher seite er anfangen muss, zu suchen...

bb

Nexus

unskilled schrieb:

lies seinen post ma noch ma - er meinte es anders ^^

Stimmt, sorry. Das Problem der Ineffizienz bleibt trotzdem. Und ineffiziente Sortieralgorithmen sind nicht gut.

volkard

x schrieb:

man kann eine verkettete liste nicht mit quicksort sortieren. für die neu-zuordnung des 'next-zeigers' etc ist qsort nicht vorgesehen.

man kann nur nicht die liste als array anschauen und es mit dem array-quicksort machen. (ok, man kann, aber das wird asozial lahm).

quicksort auf listen ist enorm nett und wie dafür gemacht. der einfachheit halber nehme ich eine queue.

void quicksort(queue &q)
  pivot=q.pop();
  queue left,right;
  while not q.empty
    i=q.pop
    if i<pivot
      left.push i
    else
      right.push i
  qsort left
  qsort right
  q.appendAndDestroy left
  q.appendAndDestroy right

die abbruchbedingung für leere oder kleine listen sowie die logarithmische beschränkung der rekursion hab ich mal weggelassen. außerdem denke ich dran, nicht elemente anzufassen, sondern knoten umzuketten. appendAndDestroy ist auch nur eine umkettung. und es läßt sich leicht auf FIFO-listen umnauen, da muß man halöt nur drauf achten, daß in jeder rekursionsvertiefung sich die richtung ändert.
quicksort geht also mit verkettetren listen und ist darüberhinaus sogar asymptotisch genauso effizient, wie quicksort auf arrays.