std::list und sort funktion
-
BorisDieKlinge schrieb:
1. Welche sortieralgorithmus verwenden diese funktion std::list.sort ? kann man diesen beschleunigen?
Man kann der Funktion sort ein Funktionsobjekt mitgeben, indem man selbst das sortierkriterium bestimmen kann, ohne Parameter nutzt die Funktion einen vordefinierten Funktor, der nach < sortiert. Wüsste aber nicht wie man den algorithmus beschleunigen könnte...
BorisDieKlinge schrieb:
2. Wenn ich die liste lösche, kann es sein das das löschen im unsortierten zustand länger geht??? je nach anzahl der elemente? Das kann doch nich sein oder...
soweit ich weiß, nein. Die liste wird (glaube ich) mit einem Iterator durchgegangen( vom anfang bis zum Ende ) und jedes Element wird einzeln geprüft( und gelöscht ). Demzufolge wäre es dann ja irrelevant an welcher stelle welches Element steht.
Mr Evil schrieb:
ich wuerd dir empfehlen eine std::map zu verwenden und es direkt schon beim einsetzen sortieren zu lassen
-
Mal so in den Raum gefragt:
Was hat das Sortierkriterium eigentlich mit dem Sortieralgorithmus zu tun?!
-
- der algo ist das ganze sortieren an sich
- das kriteritum gibt an wonach es sich dabei richtet ( in diesem fall < )
{=
-
Das Kriterium ist eine Eingabe des Algorithmus', das ist alles.
-
BorisDieKlinge schrieb:
1. Welche sortieralgorithmus verwenden diese funktion std::list.sort ? kann man diesen beschleunigen?
der standard sagt da nichts zu. Ich würde aber mal sagen nein. Die Liste nutzt höchstwahrscheinlich quicksort oder mergesort(halt ich für wahrscheinlicher). Da der sort der liste so optimiert ist, dass nur zeiger umgehängt werden und die Objekte nicht kopiert werden, wird es schwer fallen das noch weiter zu optimieren. Bei sehr kleinen Objekten bei denen das einfache kopieren schneller ist, würde ich dir eventuell zu einem vector raten und dann std::sort drüberlaufen lassen, ich denke aber nicht, dass du da viel rauskriegen wirst.
2. Wenn ich die liste lösche, kann es sein das das löschen im unsortierten zustand länger geht??? je nach anzahl der elemente? Das kann doch nich sein oder...
Nein. das löschen hat komplexität O(n). sicher dass die Liste die richtige struktur für dich ist? man löscht eigentlich nur sehr ungern elemente aus der Mitte einer Liste heraus.
Ich bin übrigens für ein set. Die Listenelemente scheinen bereits vergleichbar zu sein, also hats keinen Sinn die schlüssel separat nochmal zu speichern
-
Der Sortieralgorithmus bei std::list sort() ist Introsort und ist eine Mischung aus Quicksort und Mergesort. Er hat gegenüber dem Quicksort eine verbesserte durchschnittliche Laufzeit von O(n*log(n))
Einen schnelleren Sortieralgorithmus gibts tätsächlich, nämlich den Bucketsort (http://de.wikipedia.org/wiki/Bucketsort). Dieser hat eine Laufzeit von O(n), man muss aber dafür die komplette Liste in den Speicher laden.
-
Bitte ein Bit schrieb:
Der Sortieralgorithmus bei std::list sort() ist Introsort und ist eine Mischung aus Quicksort und Mergesort. Er hat gegenüber dem Quicksort eine verbesserte durchschnittliche Laufzeit von O(n*log(n))
Nein, introsort ist nicht stabil, dies wird aber vorm standard verlangt. wird also auf merge sort rauslaufen
-
Mr Evil schrieb:
ich wuerd dir empfehlen eine std::map zu verwenden und es direkt schon beim einsetzen sortieren zu lassen
Der Laufzeit sollte in etwa gleich sein. Was ich verwende, würde ich eher von den Operationen, die anschließend auf dem sortierten Container durchgeführt werden, abhängig machen. btw. wäre das sortierte Gegenstück zur Liste eher das multiset, weil list auch nicht assoziativ ist.
-
Bekannt geworden ist Introsort vor allem dadurch, dass Silicon Graphics in seiner Standard Template Library für C++ seit einigen Jahren auf Introsort statt Quicksort zurückgreift.
Quelle: http://de.wikipedia.org/wiki/Introsort
PS: Ein Standard möge gut und schön sein, aber Ausnahmen bestätigen die Regeln bzw. Standards
-
Bitte ein Bit schrieb:
Bekannt geworden ist Introsort vor allem dadurch, dass Silicon Graphics in seiner Standard Template Library für C++ seit einigen Jahren auf Introsort statt Quicksort zurückgreift.
Schön. Und woher weißt du, dass der Threadersteller diese Library benutzt?
Bitte ein Bit schrieb:
PS: Ein Standard möge gut und schön sein, aber Ausnahmen bestätigen die Regeln bzw. Standards
Selten so einen Quatsch gelesen. Wenn der Standard für std::list::sort ein stabiles Verfahren vorschreibt (ich habe hier gerade nur den Final Draft, da ist es so), und diese Implementierung Introsort benutzt, dann kann es also sein, dass standardkonformer Code mit dieser Implementierung nicht funktioniert. Wo du da irgendwas "bestätigt" siehst, erschließt sich mir nicht.
Ich könnte mir vorstellen, dass man Introsort für std::sort benutzt, aber nicht für std::list::sort.
-
Für list::sort wird üblicherweise Mergesort benutzt. Dieser lässt sich für Listen sehr effizient implementieren und erfüllt weiterhin die im Standard festgelegten Anforderungen: Stabilität und Komplexität von O(N Log(N)).
-
danke schön für deine überaus freundliche Antwort.
Aber bitte verzeih mir, wenn ich std::list.sort nicht kannte und ihn deswegen als std::sort ansah.
-
um noch die erklärung nachzuliefern, warum man eine liste nicht mit std::sort sortieren kann: std::sort verlangt einen randomacces-iterator, den std::list nicht bietet. (ok, man könnte mit ein bisschen spaß einen solchen machen, aber dessen performance wäre so grotten schlecht, dass man darauf verzichten sollte.)
daher die spezialisierte variante der sortierfunktion in std::list.
das ganze hätte man auch über eine templatespezialisierung lösen können, was aber ein bisschen unübersichtlich geworden wäre, da dann hinter std::sort zwei oder mehr sehr unterschiedliche sortierfunktionen gestanden hätten.