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

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

[volkardus]

GPC schrieb:

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

komisch. ich hätte dem introsort aber deutlich mehr performance zugetraut als einem lächerlichen mergesort.
miss dich auch mal für 10 mio elemente und 100 mio elemente (und wenn du genug ram hast 1000 mio).
und nicht mit rand()%2000, sondern mir rand().

[GPC]

Äh, die "Ergebnisse" sind wertlos, da std::list::sort eine bereits sortierte Liste sortiert hat, ich war wohl nicht ganz bei der Sache, als ich das machte
Interessieren würde mich allerdings, wie meine selbstgebaute uralt-Liste dagegen performt... mal schauen.

[Ponto]

Hab den Quellcode etwas modifiziert:

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

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

void vectorsort(std::list<int> list) {
   struct timeval start, stop;
   gettimeofday(&start, NULL);
   std::vector<int> vec(list.begin(), list.end());
   std::sort(vec.begin(), vec.end());
   list.assign(vec.begin(), vec.end());
   gettimeofday(&stop, NULL);
   std::cout << "Sorting time using std::sort:       " << (stop.tv_sec - start.tv_sec) * 1000000 + (stop.tv_usec - start.tv_usec) << " us\n";
}

void listsort(std::list<int> list) {
   struct timeval start, stop;
   gettimeofday(&start, NULL);
   list.sort();
   gettimeofday(&stop, NULL);
   std::cout << "Sorting time using std::list::sort: " << (stop.tv_sec - start.tv_sec) * 1000000 + (stop.tv_usec - start.tv_usec) << " us\n";
}

int main() {

   std::list<int> list;

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

   struct timeval start, stop;

   vectorsort(list);
   listsort(list);
   vectorsort(list);
   listsort(list);
   vectorsort(list);
   listsort(list);
   vectorsort(list);
   listsort(list);  
}

1.000.000 Elemente:

Sorting time using std::sort: 186023 us
Sorting time using std::list::sort: 938861 us
Sorting time using std::sort: 615975 us
Sorting time using std::list::sort: 2073201 us
Sorting time using std::sort: 704289 us
Sorting time using std::list::sort: 2033904 us
Sorting time using std::sort: 668453 us
Sorting time using std::list::sort: 2029653 us

10.000.000 Elemente:

Sorting time using std::sort: 2020496 us
Sorting time using std::list::sort: 26830949 us
Sorting time using std::sort: 11975191 us
Sorting time using std::list::sort: 52479697 us
Sorting time using std::sort: 12099630 us
Sorting time using std::list::sort: 53836998 us
Sorting time using std::sort: 13060649 us
Sorting time using std::list::sort: 53148505 us

100.000.000 Elemente:

Sorting time using std::sort: 21028156 us
Sorting time using std::list::sort: 256302313 us
Sorting time using std::sort: 120128629 us
Sorting time using std::list::sort: 511849305 us
Sorting time using std::sort: 102596007 us
Sorting time using std::list::sort: 510751965 us
Sorting time using std::sort: 102630509 us
Sorting time using std::list::sort: 496394299 us

1000 Mio scheitern nicht am RAM, sondern an der Zeit.

Was ich mich nun frage, ist warum die ersten zwei Iterationen schneller sind als der Rest.

[GPC]

Hehe, das ist schräg.

Aber immerhin bin ich mit meiner eigenen "dunkle Zeiten" - Liste knapp am std::sort dran:

Sorting time using std::sort: 0.484375 ms
Sorting time using std::list::sort: 2.46875 ms
Sorting time using my own list: 0.492188 ms

Allerdings habe ich auch einfach die Liste in ein Array gedumpt und das per quicksort sortiert, also nix großartiges.

Code:

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

#include <ctime> 
#include <cstdlib>

#include "linkedlist.hpp"

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

void std_sort(std::list<int> l) {
	std::vector<int> v(l.begin(), l.end());
	std::sort(v.begin(), v.end());
	l.assign(v.begin(), v.end());
}

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

void my_list_sort(LinkedList<int> l) {
	l.sort();	
}

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

    std::list<int> list;
	LinkedList<int> mylist; 

	int r = 0;
    for (int i = 0; i < 1000000; ++i) {
		r = rand();
        list.push_back(r);
		mylist.append(r);		   
	} 

    Timer t1; 

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

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

	t1.start(); 
	my_list_sort(mylist);
	t1.stop(); 
        std::cout << "Sorting time using my own list: " << t1.diff() << " ms\n";
    return EXIT_SUCCESS; 
}