std::list::sort vs. std::sort

[Ponto]

Maxi schrieb:

wenn die Liste Zeiger auf Objekte speichert... dann bringt es doch nichts die Zeiger zu sortieren...
Dann hast du deine Objekte im Speicher nach ihrer Anordnung sortiert und niht nach ihren Werten. wenn dann musst du schon das vergleichen worauf die zeiger zeigen.

Also ich denke es kommt auf die Listengröße an, list::sort ist eben nicht besonders schnell, weil da kein Direktzugriff ist. Weiß jetzt nich, wie das genau implementiert ist, aber ich schätz ma bubblesort oder so, also quadratisch laufzeit. std::sort hat ja logarithmische Laufzeit. Musst gucken... zu der Laufzeit musst du ja noch zwei Kopiervorgänge dazurechnen, samt aufbauen und löschen der Listen-zeiger. Ein Benchmark dazu is doch aber auch ncih sooo kompliziert dafür eigentlich.

1. Natürlich wird da eine Vergleichsfunktion mitgegeben, welche die Objekte hinter den Zeigern vergleicht.

2. std::list::sort ist auch O(nlogn) genauso wie std::sort

3. Das Ab- und Aufbauen der Liste entfällt, da beim Zurückschreiben einfach die Zeiger neu gesetzt werden. Es gibt ja nach dem Sortieren genauso viele Elemente, wie vorher.

[GPC]

Äh, also wenn ich ein std::list habe und die sortieren will, mach ich das immer über std::list::sort, der sort-Algo wurde IIRC an die Bedürfnisse von std::list angepasst.

[volkard]

Maxi schrieb:

Also ich denke es kommt auf die Listengröße an, list::sort ist eben nicht besonders schnell, weil da kein Direktzugriff ist. Weiß jetzt nich, wie das genau implementiert ist, aber ich schätz ma bubblesort oder so, also quadratisch laufzeit. std::sort hat ja logarithmische Laufzeit. Musst gucken... zu der Laufzeit musst du ja noch zwei Kopiervorgänge dazurechnen, samt aufbauen und löschen der Listen-zeiger. Ein Benchmark dazu is doch aber auch ncih sooo kompliziert dafür eigentlich.

naja, list::sort kann man auch ertne als quicksort implementieren. das wäre sehr naheliegend und oft rasend schnell. oder wie erwähnt mergesort, das immer ausreichend schnell ist.

zum umkopieren: ich würde auch im array nur die zeiger auf die daten speichern und dann nen entsprechenden verkleicher "bool ptrLess(T* a,T* b){return *a<*b;}" mitgeben.

was in vorliegenden fall besser ist, muss man wohl ausmessen.

[Konrad Rudolph]

Hallo,

ich denke, man kann mit ziemlicher Sicherheit davon ausgehen, dass 'std::list::sort' ein Mergesort ist. Dementsprechend denke ich, dass es auf *auf jeden Fall* schneller ist als das Kopieren in einen Vektor und Sortieren mit 'std::sort'.

[Konrad Rudolph]

volkard schrieb:

naja, list::sort kann man auch ertne als quicksort implementieren. das wäre sehr naheliegend und oft rasend schnell.

Huch? Wie implementiert man denn ein effizientes Quicksort auf Listen? Ich wäre sehr an einem (Pseudo-)Code interessiert.

[volkard]

Konrad Rudolph schrieb:

volkard schrieb:

naja, list::sort kann man auch ertne als quicksort implementieren. das wäre sehr naheliegend und oft rasend schnell.

Huch? Wie implementiert man denn ein effizientes Quicksort auf Listen? Ich wäre sehr an einem (Pseudo-)Code interessiert.

mal annehmen, daß ich zeiger auf anfang und ende der liste hab oder nen ring.

void quicksort(list li){
   pivot=li.popfront          //O(1)
   list left
   list right
   while(!li.isEmpty)         //O(1)
      x&=li.popfront          //O(1)
      if(x=pivot)             //O(1)
         left.pushback(x)     //O(1)
      else                    //O(1)
         right.pushback(x)    //O(1)
   quicksort(left)
   quicksort(right)
   moveallelems from left to end of li  //O(1)
   li.pushback(pivot)                   //O(1)
   moveallelems from left to end of li  //O(1)
}

offensichtlich ein gutes quicksort. man muss nur den kern von quicksort in die listen-teminologie mogeln, statt die liste als array zu sehen und dort ein array-quicksort drauf zu machen.

schlimmstensfalls hat man nur nen stack, also nur pushFront, popFront, isEmpty und peekFront implementiert (alle O(1) natürlich) und innendrin nur nen zeiger auf erste elem und pro elem einen zeiger auf den nachfolger.

auch dann kriegt man ein feines quicksort hin. nur ändert sich in jeder rekursionstiefe die sortierreihenfolge, da muß man ein wenig aufpassen.

[Konrad Rudolph]

volkard schrieb:

offensichtlich ein gutes quicksort.

Ja, aber doch wohl ein elend langsames. Du konstruierst hier 2 * n neue Listen und schiebst Elemente in sie rein. Das sind zwar alles elementare Operationen aber meines Wissens belasten die die Heap-Verwaltung ganz schön. Wo liegt mein Denkfehler?

Die SGI-Implementierung verstehe ich ehrlich gesagt überhaupt nicht. So, wie ich das sehe, wird da ganz zu Anfang das erste Element rausgeschmissen und nie wieder eingefügt. Wo isses hin?

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::sort()
{
    list<_Tp, _Alloc> carry;
    list<_Tp, _Alloc> counter[64];
    int fill = 0;

    while (not empty()) {
        carry.splice(carry.begin(), *this, begin());
        int i = 0;

        while(i < fill and not counter[i].empty()) {
            counter[i].merge(carry);
            carry.swap(counter[i++]);
        }

        carry.swap(counter[i]);         
        if (i == fill) ++fill;
    } 

    for (int i = 1; i < fill; ++i)
        counter[i].merge(counter[i - 1]);

    swap(counter[fill - 1]);
}

[volkard]

Konrad Rudolph schrieb:

volkard schrieb:

offensichtlich ein gutes quicksort.

Ja, aber doch wohl ein elend langsames. Du konstruierst hier 2 * n neue Listen und schiebst Elemente in sie rein. Das sind zwar alles elementare Operationen aber meines Wissens belasten die die Heap-Verwaltung ganz schön. Wo liegt mein Denkfehler?

darin, daß man gar keine neuen heap-elemente anlegen muß. ich habs der einfachheit halber im psodocode getan. es reicht natürlich, die elemnte leben zu lassen und nur die verzeigerung zu ändern.

[volkard]

gelöcht, war unfug

[volkard]

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::sort()
{
    list<_Tp, _Alloc> carry;
    list<_Tp, _Alloc> counter[64];
    int fill = 0;

    while (not empty()) {
        carry.splice(carry.begin(), *this, begin());//ein elem nach carry holen
        int i = 0;

//also in carry ist 1 elem. 
//und in counter[0] auch (ok, erst im zweiten durchlauf ist da was)

//nun mische ich carry und counter[0] zusammen und erhalte eine doppelt so 
//große liste in counter[0]
//die swappe ich nach carry und mache dabei counter[0] leer. und gehe zu counter[1]. 

//mein carry-sack ist jetzt auch doppelt so groß. wenn ich ein gleichgroßes 
//opfer in counter[1] finde, mische ich wieder zusammen. so lange, 
//wie ich opfer finde. 

        while(i < fill and not counter[i].empty()) {
            counter[i].merge(carry);
            carry.swap(counter[i++]);
        }

        carry.swap(counter[i]);         
        if (i == fill) ++fill;
    } 

    for (int i = 1; i < fill; ++i)
        counter[i].merge(counter[i - 1]);

    swap(counter[fill - 1]);
}

[Konrad Rudolph]

volkard schrieb:

carry.splice(carry.begin(), *this, begin());//ein elem nach carry holen

Ah. Aus der cppreference-Doku lese ich das Gegenteil heraus:

void splice( iterator pos, list& lst, iterator del );

The splice() function inserts lst at location pos. [...] the element... at del [is] removed.

=> Klingt für mich danach, dass 'this' nach 'pos' kopiert wird, mit Ausnahme von 'begin()'.

//nun mische ich carry und counter[0] zusammen und erhalte eine doppelt so
//große liste in counter[0]
//die swappe ich nach carry und mache dabei counter[0] leer. und gehe zu counter[1].

//mein carry-sack ist jetzt auch doppelt so groß. wenn ich ein gleichgroßes
//opfer in counter[1] finde, mische ich wieder zusammen. so lange,
//wie ich opfer finde.

Soweit klar. Trotzdem vermisse ich irgendwie einen Vergleich. Es wird hier doch an keinem Punkt ein Vergleich oder wenigstens eine Metrik aufgerufen.

[volkard]

Konrad Rudolph schrieb:

Soweit klar. Trotzdem vermisse ich irgendwie einen Vergleich. Es wird hier doch an keinem Punkt ein Vergleich oder wenigstens eine Metrik aufgerufen.

vergleich? metrik? was genau vermißt du?

[volkard]

volkard schrieb:

Konrad Rudolph schrieb:

Soweit klar. Trotzdem vermisse ich irgendwie einen Vergleich. Es wird hier doch an keinem Punkt ein Vergleich oder wenigstens eine Metrik aufgerufen.

vergleich? metrik? was genau vermißt du?

vergleiche sehe ich zwei.
innerhalb von counter[i].merge(carry);, da wird immer elementweise nach größe verglichen.

und bei
and not counter[i].empty())
da wird per hand binär hochgezählt.

[Konrad Rudolph]

volkard schrieb:

vergleich? metrik? was genau vermißt du?

Na ja, mit einer Metrik könnte man drei Punkte anhand ihrer Entfernungen zueinander anordnen. Ist aber in diesem Zusammenhang natürlich Quatsch, da man aufsteigend oder absteigend nicht bestimmen könnte.

innerhalb von counter[i].merge(carry);, da wird immer elementweise nach größe verglichen.

Aaah. Okay, damit wird einiges klarer. Danke.

[volkard]

ganz zufällig habe ich so einen hochzähl-trick erst vor wenigen wochen auch programmiert.

als batch-datei in winxp.

das wichtigste dran ist

@echo off
set pos=-1
:nextLevel
set /A pos=%pos%+1
if exist %pos%.digit (
 del %pos%.digit"
 goto nextLevel
)
echo.>%pos%.digit"

das zählt bei jedem aufruf eine binärzahl um 1 hoch, die als bits veteilt (die jeweils duch die existenz der datei bitnummer.digit) auf der platte liegt. und gibt mir die variable pos, die dann meine backup-zeildatei ist. damit halte ich weniger der älteren backups vor, genau das, was ich mag.

[Ponto]

Konrad Rudolph schrieb:

volkard schrieb:

offensichtlich ein gutes quicksort.

Die SGI-Implementierung verstehe ich ehrlich gesagt überhaupt nicht. So, wie ich das sehe, wird da ganz zu Anfang das erste Element rausgeschmissen und nie wieder eingefügt. Wo isses hin?

Ich weiss nicht genau wie der Algorithmus heisst, aber er funktioniert so:

Du hast eine Liste carry, die als Arbeitspferd dient. Dann hast du 64 Listen im Array counter. Für jede dieser Listen gilt folgende Eigenschaft:

enthält nach jeder Iteration höchstens 2^x Elemente. Zusätzlich sind die Elemente sortiert.

Dies bedeutet, dass counter[0] maximal 1 Element enthält. counter[5] hat maximal 32 Elemente. Insgesamt dürfen in counter höchstens 2^64-1 Elemente drin sein. Das sollte auf heutigen Rechnern ausreichen. Wenn das aber mal ein Problem wird, kann man einfach das Limit erhöhen.

Nun wird einfach der Reihe nach ein Element aus der Ursprungsliste entfernt und in counter[0] sortiert reingetan. Wird die obige Bedingung verletzt wird counter[0] mit counter[1] sortiert vermengt (std::sort::merge) und das Ergebnis ist in counter[1]. Falls die Bedingung immer noch verletzt ist, wird das beliebig weitergetan.

Man kann nach der x-ten Iteration genau sagen, wieviele Elemente in den einzelnen counter Listen liegen. Es ist einfach die Binärdarstellung von x.

Am ende werden alle listen in counter sortiert vermengt und das Ergebnis wird in die Ursprungsliste geschrieben.

Anmerkungen:

Die benutzten Funktionen merge(), splice() und swap() legen keine neuen Listenelemente an, sondern biegen nur existierende um.

Die Vergleiche für das Sortieren finden in merge() statt.

[Ponto]

Ein kleiner Test sagt mir, dass die Benutzung von std::sort schneller ist, als die Benutzung von std::list::sort. Zumindest für int. Sollte aber auch für Zeiger gelten.

Das hätte ich nicht erwartet.

Wenn man sich also den Overhead leisten kann und man die Laufzeit benötigt, dann ist std::sort schneller.

#include <cstdlib>
#include <iostream>
#include <vector>
#include <list>

extern "C" {
#include <sys/time.h> 
}

void vectorsort(std::list<int> list) {

   std::vector<int> vec(list.begin(), list.end());
   std::sort(vec.begin(), vec.end());
   list.assign(vec.begin(), vec.end());
}

void listsort(std::list<int> list) {
   list.sort();
}

int main() {

   std::list<int> list;

   for (int i = 0; i < 1000000; ++i) {
      list.push_back(random());  
   }

   struct timeval start, stop;
   gettimeofday(&start, NULL);
   vectorsort(list);
   gettimeofday(&stop, NULL);

   std::cout << "Sorting time using std::sort:       " << (stop.tv_sec - start.tv_sec) * 1000000 + (stop.tv_usec - start.tv_usec) << " ms\n";

   gettimeofday(&start, NULL);
   listsort(list);
   gettimeofday(&stop, NULL);

   std::cout << "Sorting time using std::list::sort: " << (stop.tv_sec - start.tv_sec) * 1000000 + (stop.tv_usec - start.tv_usec) << " ms\n";
}

[GPC]

Hm, ich bin mir jetzt nicht sicher, aber liefert dein Aufruf von gettimeofday nicht einfach die verstrichene Zeit, anstatt der benutzten CPU-Zeit?
Na ja, hier mein Test (mit Timer Klasse und direktem Aufruf der sort-Algos):

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

#include <ctime>
#include <cstdlib>

class Timer {
	clock_t start_, end_;

	Timer(const Timer&);
	Timer& operator=(const Timer&);

public:
	Timer() {}
	virtual ~Timer() {}

	void start() { start_ = clock(); }

	void stop() { end_ = clock(); }

	float diff() {
		return static_cast<float>(end_ - start_) /
			static_cast<float>(CLOCKS_PER_SEC);
	}

	float elapsed() {
		return static_cast<float>(end_ = clock() - start_) /
			static_cast<float>(CLOCKS_PER_SEC);
	}
}; 

int main() {
	srand(time(NULL));

	std::list<int> list;

	for (int i = 0; i < 1000000; ++i) {
		list.push_back(rand()%2000);  
	}
	Timer t1;
	t1.start();
	std::vector<int> vec(list.begin(), list.end());
	std::sort(vec.begin(), vec.end());
	list.assign(vec.begin(), vec.end());
	t1.stop();

	std::cout << "Sorting time using std::sort: " << t1.diff() << " ms\n";

	//Timer t2;
	t1.start();
	list.sort();
	t1.stop();

	std::cout << "Sorting time using std::list::sort: " << t1.diff() << " ms\n";
	return EXIT_SUCCESS;
}

Hier schneidet std::list::sort deutlich besser ab:

Sorting time using std::sort: 0.64 ms
Sorting time using std::list::sort: 0.297 ms

EDIT 1+2: Code und Ergebnisse geändert.

EDIT 3:
Wenn man die listen per Referenz an die Funktionen übergibt, sieht's so aus:

Sorting time using std::sort: 0.625 ms
Sorting time using std::list::sort: 0.312 ms

Macht man die Funktionen zusätzlich inline, tut sich nicht mehr viel am Ergebnis.

MfG

GPC

[Ponto]

GPC schrieb:

Hm, ich bin mir jetzt nicht sicher, aber liefert dein Aufruf von gettimeofday nicht einfach die verstrichene Zeit, anstatt der benutzten CPU-Zeit?
Na ja, hier mein Test (mit Timer Klasse und direktem Aufruf der sort-Algos):

Ja. Mit gettimeofday messe ich die Realzeit. Bei so klaren Unterschieden ist es nicht notwendig CPU-Zeit zu messen.

Ich habe außerdem die Listen nicht als Referenz übergeben, damit beide Algorithmen die selbe Startliste haben. Mit Referenzen und in deinem Code übergibst du dem std::list::sort eine bereits sortierte Liste mit. Das Ergebnis ist damit nicht aussagekräftig.

[GPC]

Ponto schrieb:

GPC schrieb:

Hm, ich bin mir jetzt nicht sicher, aber liefert dein Aufruf von gettimeofday nicht einfach die verstrichene Zeit, anstatt der benutzten CPU-Zeit?
Na ja, hier mein Test (mit Timer Klasse und direktem Aufruf der sort-Algos):

Ja. Mit gettimeofday messe ich die Realzeit. Bei so klaren Unterschieden ist es nicht notwendig CPU-Zeit zu messen.

okay

Ich habe außerdem die Listen nicht als Referenz übergeben, damit beide Algorithmen die selbe Startliste haben. Mit Referenzen und in deinem Code übergibst du dem std::list::sort eine bereits sortierte Liste mit. Das Ergebnis ist damit nicht aussagekräftig.

Fuck, das hab ich glatt verpennt
Na jo, damit hast du Recht, hier ist std::sort wirklich schneller als std::list::sort... was mich jetzt aber wundert.