qsort frage

lord_fritte

Weil ich keine vectoren, sondern eine verkettete liste sortieren möchte.
Außerdem soll meine Sortfunktion eine zusatzklasse zum einstellen von sortierparametern bekommen.

Firefighter

Kann std::sort alles.Schau dir den Link von Nexus an.Du übergibst einfach Iteratoren

Nexus

Firefighter schrieb:

Kann std::sort alles.Schau dir den Link von Nexus an.Du übergibst einfach Iteratoren

Stimmt nicht ganz, std::sort() und std::stable_sort() funktionieren nur mit Random-Access-Iteratoren. Für Listen kann man std::list::sort() nehmen.

lord_fritte schrieb:

Außerdem soll meine Sortfunktion eine zusatzklasse zum einstellen von sortierparametern bekommen.

Das sollte gut mit Funktoren möglich sein, die du der Sortierfunktion übergibst.

lord_fritte

Wofür Iteratoren... mein tut es auch super, ich brauche nur noch ein laufendes qsort und alles ist perfekt..

Firefighter

Sorry Nexus, ich bin zu der Uhrzeit wo du richtig Wach wirst, nicht mehr ganz auf der Höhe, natürlich nur RandomAccess, hab sogra die Referenz vor und hab Mist erzählt, nimms mir nicht übel

Nexus

lord_fritte schrieb:

Wofür Iteratoren... mein tut es auch super, ich brauche nur noch ein laufendes qsort und alles ist perfekt..

Selber schreiben ist nicht empfehlenswert, wenn es die Funktionalität bereits in der Standardbibliothek gibt. Die STL ist recht gut auf Performance optimiert und prüft auch alles Mögliche mit Assertions. Und wozu das Rad neu erfinden und es mit hoher Wahrscheinlichkeit schlechter machen, wenn es schon eine fertige Funktion dafür gibt?

Du musst nichts mit Iteratoren machen, ruf einfach std::list::sort() auf. Je nach Wunsch mit Vergleichsprädikat. Mehr dazu hier...

Firefighter schrieb:

Sorry Nexus, ich bin zu der Uhrzeit wo du richtig Wach wirst, nicht mehr ganz auf der Höhe, natürlich nur RandomAccess, hab sogra die Referenz vor und hab Mist erzählt, nimms mir nicht übel

Aber nein, ist doch kein Problem...

lord_fritte

Aber mit Iteratoren kann man doch keinen direkten zugriff([]) durchführen..
Und ich teste gleich mal mit dem QueryPerformanceCount wie die Geschwindigkeit aussieht.

Also beim einfügen von 10.000 Elementen ist meine Klasse schonmal 20 ms schneller, direkten zugriff kann ich ja nicht testen, das gibt es ja nicht bei std::list nicht....

Nexus

lord_fritte schrieb:

Aber mit Iteratoren kann man doch keinen direkten zugriff([]) durchführen..

Kann man bei verketteten Listen eh nicht...

lord_fritte schrieb:

Also beim einfügen von 10.000 Elementen ist meine Klasse schonmal 20 ms schneller, direkten zugriff kann ich ja nicht testen, das gibt es ja nicht bei std::list nicht....

Hm, wie hast du es genau versucht? Und du hast eine eigene Listenklasse, oder?

lord_fritte

Nexus schrieb:

Kann man bei verketteten Listen eh nicht...

Das habe ich bei meiner Klasse eingebaut.

Nexus schrieb:

Hm, wie hast du es genau versucht? Und du hast eine eigene Listenklasse, oder?

Ja und bisher läuft alles super.

ich teste das so:

void ListBench2()
{
	double time1 = 0.0;
	double time2 = 0.0;

	MyList<int> myList;
	list<int> yourList;

	srand(time(NULL));

	printf("Liste fuellen mit ");
	for(int x = 0; x < 10000; x++)
	{
		int zahl = rand();
		HiPerCounter counter1;
		HiPerCounter counter2;

		counter1.Start();
		myList.Add(zahl);
		counter1.Stop();
		time1 += counter1.GetTime();

		counter2.Start();
		yourList.push_back(zahl);
		counter2.Stop();
		time2 += counter2.GetTime();
	}
	printf("%d Elementen.\n", myList.Count());
	printf("%lf sec's MyList\n\n", time1);
	printf("%lf sec's list\n", time2);

	time1 = 0.0;
	time2 = 0.0;
	printf("Leeren der Liste:\n");
	HiPerCounter counter1;
	HiPerCounter counter2;
	counter1.Start();
	myList.Clear();
	counter1.Stop();
	time1 = counter1.GetTime();

	counter2.Start();
	yourList.clear();
	counter2.Stop();
	time2 = counter2.GetTime();

	printf("%lf sec's MyList\n\n", time1);
	printf("%lf sec's list\n", time2);
}

und der Counter arbeitet korrekt, das ahbe ich auch schon geteste, mit sleep.

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