Mergesort sehr langsam

[unskilled]

hallo mal wieder ;o)

Also ich komme mit

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

#include "my/timer.h"

int main()
{
	int count = 100*1000;
	std::vector<int> vec;
	vec.reserve(count);
	for(int i=0; i != count; ++i)
		vec.push_back(i);
	std::random_shuffle(vec.begin(), vec.end());

	std::list<int> list(vec.begin(), vec.end());
	my::timer_t timer;
	list.sort();
	std::cout << my::timer_t::get_seconds_from_ticks(timer()) << std::endl;

	std::cout << '\t' << *list.begin() << std::endl;
}

auf 0.032 Sekunden(x32) bzw 0.027 Sekunden(x64). (Core2Duo 2x3,0GHz; MSVC9; Release ohne Debugger)
int count = 10*1000*1000; : 0.5Sekunden
int count = 100*1000*1000; : 9Sekunden
Klingt schneller als deine reichliche halbe Sekunde ;P

Falls du weiterhin ein eigenes sort brauchst: std::list::splice ist dein Freund.
Ich fürchte aber, du wirst nicht schneller kommen.
Maximal noch, wenn du etwas über die Verteilung der Zahlen in deiner Liste weist.

bb

[unskilled]

Es geht doch noch schneller:

template<typename T>
void list_sort(T& to_sort)
{
	if(to_sort.size() < 10000)
	{
		to_sort.sort();
		return;
	}

	try
	{
		std::vector<typename T::value_type> tmp(to_sort.begin(), to_sort.end());
		std::sort(tmp.begin(), tmp.end());
		to_sort.assign(tmp.begin(), tmp.end());
		return;
	}
	catch(std::bad_alloc&)
	{}

	std::deque<typename T::value_type> tmp(to_sort.begin(), to_sort.end());
	std::sort(tmp.begin(), tmp.end());
	to_sort.assign(tmp.begin(), tmp.end());
}

if(to_sort.size() < 10000)
Die Zahl ist einfach nur geraten. Evtl ausmessen und in ne Konstante packen.
Wenn man zum Programmstart Zeit hat, könnte man die auch für jeden PC "ausrechnen".
Also als static-Variable in die Fkt packen und beim ersten Aufruf nen paar Sortier-Vorgänge simulieren:

namespace detail
{
	template<typename T>
	void sort_list(T& to_sort)
	{
		to_sort.sort();
	}

	template<typename T>
	void sort_and_assign(T& to_sort)
	{
		try
		{
			std::vector<typename T::value_type> tmp(to_sort.begin(), to_sort.end());
			std::sort(tmp.begin(), tmp.end());
			to_sort.assign(tmp.begin(), tmp.end());
			return;
		}
		catch(std::bad_alloc&)
		{}

		try
		{
			std::deque<typename T::value_type> tmp(to_sort.begin(), to_sort.end());
			std::sort(tmp.begin(), tmp.end());
			to_sort.assign(tmp.begin(), tmp.end());
			return;
		}
		catch(std::bad_alloc&)
		{}

		sort_list(to_sort);
	}

	template<typename S, typename T>
	S get_performance_bound_for_list_search(const T&)
	{
		S ret_val = 32;

		my::timer_t::tick_type ticks_list_sort;
		my::timer_t::tick_type ticks_assign_and_sort;

		do
		{
			if(ret_val >= std::numeric_limits<S>::max()/2)
				return std::numeric_limits<S>::max();

			ret_val *= 2;
			std::list<S> list1, list2;
			{
				std::vector<S> vec;
				vec.reserve(ret_val);
				for(S i=0; i != ret_val; ++i)
					vec.push_back(i);
				std::random_shuffle(vec.begin(), vec.end());
				list1.assign(vec.begin(), vec.end());
				list2.assign(vec.begin(), vec.end());
			}

			my::timer_t timer;
			detail::sort_list(list1);
			ticks_list_sort = timer();

			timer.reset();
			detail::sort_and_assign(list2);
			ticks_assign_and_sort = timer();

		} while(ticks_list_sort < ticks_assign_and_sort);

		return ret_val;
	}
}

template<typename T>
void list_sort(T& to_sort, bool strict_use_list_sort = false)
{
	static typename T::size_type performance_bound_for_list_search = detail::get_performance_bound_for_list_search<typename T::size_type>(to_sort);

	if(strict_use_list_sort || to_sort.size() < performance_bound_for_list_search)
	{
		detail::sort_list(to_sort);
	}
	else
	{
		detail::sort_and_assign(to_sort);
	}
}

int main()
{
	int count = 10*1000*1000;
	std::vector<int> vec;
	vec.reserve(count);
	for(int i=0; i != count; ++i)
		vec.push_back(i);
	std::random_shuffle(vec.begin(), vec.end());

	std::list<int> list(vec.begin(), vec.end());

	my::timer_t timer;
	list_sort(list);
	std::cout << my::timer_t::get_seconds_from_ticks(timer()) << std::endl;

	std::cout << '\t' << *list.begin() << std::endl;
}

Zeigt, dass das list-sort immer langsamer ist als das umkopieren und kopieren (zumindest bei mir).
Das hab ich erst nicht geglaubt und noch nen Sleep in die Umkopier-Variante gemacht, aber dann hab ichs auch geglaubt... ^^
Aber evtl gibts ja nen System, wo ein new (erheblich) teurer ist... ^^

Das einzige, was man jz noch machen könnte, wäre den entsprechnenden Allokator zu nutzen - aber das wird wohl kaum jmd brauchen (es sei denn, du hast irgend nen GC, den du nutzt)... ^^

bb

PS: Anwendung bleibt wie gehabt:

list_sort(list);

evtl sollte man die fkt auch in inplace_sort oder so umbenennen - kA...

edit: was ich vergessen habe zu erwähnen: Bei den Tests wird list<size_type> anstatt list<value_type> genutzt - das liegt daran, dass value_type nicht zwangsläufig einen CTor besitzen muss, der einen Integer-Wert entgegennimmt - und da ist mir nix besseres eingefallen, als den size_type zu nehmen. Einfach nur value_type() zu nehmen, war mir zu gefährlich beim Testen - evtl. gibt es ja list.sort()-Implementierungen, die zu erst gucken, ob schon geordnet ist - weiterhin gibt es ja auch nicht immer einen Standard-CTor. Kurz: wenn die Objekte kompliziert(zeitaufwendig) zu kopieren sind, dann solltest du den test entsprechend anpassen...

edit #2:
Zeile 46-48 im zweiten Quellcode eingefügt.

[otze]

ja, bei dem Test ist das auch erstmal kein Wunder. Immerhin ist das kopieren von ints nicht wirklich teuer - und dann ist die ganze Listenoptimierung im Eimer. Dast du aber Objekte, die nicht trivial kopierbar sind, oder die einen großen State haben, dann zieht dir die Liste sofort davon.

Was mich viel eher interessieren würd eist, welche Probleme der Threadstarter mit der std::list hatte...

[unskilled]

otze schrieb:

ja, bei dem Test ist das auch erstmal kein Wunder. Immerhin ist das kopieren von ints nicht wirklich teuer - und dann ist die ganze Listenoptimierung im Eimer. Dast du aber Objekte, die nicht trivial kopierbar sind, oder die einen großen State haben, dann zieht dir die Liste sofort davon.

Jopp - habe ich ja auch geschrieben.
Ist aber eben auch kein Problem, das zu ändern - auch das habe ich aber geschrieben...
Allerdings hat der TO ja explizit ints verwendet.

Was mich viel eher interessieren würd eist, welche Probleme der Threadstarter mit der std::list hatte...

ich nehme an, es lag daran, dass er list::sort nicht gefunden hatte und std::sort nicht ging und dann hat er splice nicht gefunden und konnte somit die Zeiger nicht umbiegen...

bb

[Godemit]

das Problem mit std::list hat nichts mit dem sortieren zu tun. Das funktioniert tadellos und schnell.

Mein Problem war, dass ich im späteren Verlauf des Programms Zeiger auf einzelne Listenelemente benötigt und das überhaupt nicht hinbekommen hab.

Daraufhin hab ich mich entschlossen, lieber eine komplett eigene Datenstruktur zu benutzen, die ich dafür vollständig verstehe.

Vielleicht noch was über die Daten, die zu sortieren sind: Es sind integer Werte zwischen 0 und 765 mit einem sehr hohen Anteil von kleinen Werten (12% sind 0, 74% unter 10, 95% unter 100)

Welches Verfahren sortiert mir eine Liste mit 10 solcher Werte am schnellsten?

Gruß
Godemit

[Michael E.]

Godemit schrieb:

Mein Problem war, dass ich im späteren Verlauf des Programms Zeiger auf einzelne Listenelemente benötigt und das überhaupt nicht hinbekommen hab.

An deiner Stelle würde ich mich dann mit std::list (und Iteratoren bei diesem speziellen Problem) vertraut machen, anstatt das Rad neuzuerfinden. Dadurch wirst du auch sehr viel Zeit sparen, denn den Umgang mit std::list hast du nach spätestens ein paar Stunden raus. In der Zeit hast du keine eigene gute, schnelle, exceptionsichere, fehlerfreie Klasse geschrieben.

[krümelkacker]

Godemit schrieb:

das Problem mit std::list [...] Mein Problem war, dass ich im späteren Verlauf des Programms Zeiger auf einzelne Listenelemente benötigt und das überhaupt nicht hinbekommen hab.

list<int> intlist;
intlist.push_back(11);                             // [11]
intlist.push_back(22);                             // [11 22]
intlist.push_back(33);                             // [11 22 33]
list<int>::iterator it1 = intlist.begin();         //  ^^
++it1;                                             //     ^^
list<int>::iterator it2 = intlist.insert(it1,20);  // [11 20 22 33]
                                                   //     ^^ ^^
                                                   //    it2 it1

Ein Iterator funktioniert so ähnlich wie ein Zeiger. Die Iteratorn einer Liste sind bidirektional. D.h. Du kannst ++ und -- benutzen, um ein Element vor und zurück zu gehen, Du kannst sie vergleichen, Iteratoren bleiben relativ lange gültig bei std::list (im Gegensatz zu std::vector zB).

[unskilled]

krümelkacker schrieb:

Iteratoren bleiben relativ lange gültig bei std::list (im Gegensatz zu std::vector zB).

Nicht nur relativ lange, sondern so lange das Element gelöscht wird.

Mal was ganz anderes:
Wieso denkst du denn, dass list die optimale Datenstruktur ist?
Erzähl mal ein wenig, was du mit der Liste alles so anstellst... Und vll auch, wie oft circa.

bb

[Nexus]

unskilled schrieb:

Nicht nur relativ lange, sondern so lange das Element gelöscht wird.

Du meinst wohl "so lange bis das Element gelöscht wird".

[Godemit]

unskilled schrieb:

krümelkacker schrieb:

Iteratoren bleiben relativ lange gültig bei std::list (im Gegensatz zu std::vector zB).

Nicht nur relativ lange, sondern so lange das Element gelöscht wird.

Mal was ganz anderes:
Wieso denkst du denn, dass list die optimale Datenstruktur ist?
Erzähl mal ein wenig, was du mit der Liste alles so anstellst... Und vll auch, wie oft circa.

bb

Es geht um Bildverarbeitung. Das Rohbild wird eingelesen und die Pixel in einer verketteten Liste gespeichert. Zusätzlich werden die Kantengewichte der Pixelübergänge zu den benachbarten Pixeln gespeichert (RGB Bild: R1+G1+B1-R2-G2-B2, daher auch die maximalen 755). Zusätzlich zeigt jede Kante auf die beiden Pixel, die sie verbindet und ein Pixel zeigt auf die (max) 8 Kanten, die von ihm ausgehen. Das ist wichtig, damit ich später im MST (Minimal Spanning Tree) die Umgebung einer Kanten bzw. eines Pixels untersuchen kann.
Um den MST zu berechnen, müssen die Kanten nach Kosten aufsteigend sortiert werden (für den Algorithmus von Kruskal).

Hier die derzeitige Datenstruktur, falls das von Interesse ist:

class edge
{
public:
	pixel *p1;
	pixel *p2;
    int cost;
	int dir;
    edge *prev;
    edge *next;
};

class pixel
{
public:
	int x;
	int y;
	int n;
	RGB seg_color;

	edge* e[8];

	pixel *next;
	pixel *prev;
	pixel *parent;

public:
	pixel();
	pixel* find();
	void union2(pixel* p2);

};

Jedes Pixel hat noch ein Attribut parent, durch das man mehrere Pixel zu einem Segment gruppieren kann (das passiert per union2()).

Das ganze soll für Kamerabilder mit einer Auflösung von 640x480 (307.200 Pixel, 1.225.442 Kanten) funktionieren. Später evtl mehr.

[unskilled]

@nexus:
forumbug - ich hatte das bis bestimmt mitgeschrieben!

@TO:
kein plan, wie das normalerweise gelöst wird, aber das hört sich nicht nach nem anwendungsfall für eine liste an...
klingt eher nach vector.

aber warte mal lieber, bis dir jmd antwortet, der sich damit vll doch ein wenig auskennt... ^^

bb

[krümelkacker]

Godemit schrieb:

Es geht um Bildverarbeitung. [...]

Das ganze soll für Kamerabilder mit einer Auflösung von 640x480 (307.200 Pixel, 1.225.442 Kanten) funktionieren. Später evtl mehr.

Dafür legste Dir 'ne vernünftige "Raster"-Klasse an, wo die Pixelwerte alle linear hintereinander im Speicher stehen. Etwa so:

template<typename T>
class raster2d
{
public:
  typedef typename std::vector<T>::size_type size_type;

private:
  std::vector<T> elements;
  size_type width;
  size_type height;

  size_type indexof(size_type x, size_type y) const
  { return y*width+x; }

public:
  ...

  T const& operator()(size_type x, size_type y) const
  { return elements[indexof(x,y)]; }

  T      & operator()(size_type x, size_type y)
  { return elements[indexof(x,y)]; }

  ...
};

... oder einfach Boost.MultiArray nehmen.

[life]

Du benutzt tatsächlich den Algorithmus von Kruskal zum Berechnen eines MSTs? Warum nicht einfach den Algorithmus von Prim (http://de.wikipedia.org/wiki/Algorithmus_von_Prim)?