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

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