STL sort schlagen

Gregor

@ Japro : Interessantes Sort! Das scheint so ähnlich zu funktionieren, wie ein Sort, das ich mal in Java geschrieben habe. Den entsprechenden Code findest du in diesem Thread : C# und Linux

Dein Sort wird natürlich sehr viel schneller sein, allein schon dadurch, dass du das in C++ geschrieben hast. Aber vielleicht findest du ja in meinem Code noch ein paar gute Ideen, die du auch bei dir einsetzen kannst.

Im Vergleich zu dem Sort aus java.util.arrays braucht mein Code ungefähr 85-90% der Zeit. Da sollten also schon ein paar gute Ideen drin sein. Wie sieht das denn bei dir im Vergleich zum STL-Sort aus?

[ Dieser Beitrag wurde am 29.06.2002 um 00:54 Uhr von Gregor editiert. ]

japro

erstmal muss ich meine aussagen etwas korrigieren :D. bei meinem sort bin ich nämlich nicht sicher ob man es wie das stl sort verwenden kann bezüglich kontainern und iteratoren, besonders wegen volgenden zeilen:

if ((end-obegin) > 32) subSort(obegin,end);
 if ((oend-begin) > 32) subSort(begin,oend);

das geht mit pointern ganz gut aber ich weiss net wie das bei iteratoren ist.
ausserdem dürfte es langsamer sein als das stl sort wenn es auf schon sortierte oder rückwärts sortierte daten losgelassen wird. weil ich bei der median aus drei methode bis jetzt keine möglichkeit sah das mittlere element ziwschen zwei pointer zu finden (pointerarithmetik erlaubt ja kein / und *).
hat da wer ne idee?

achja und was ist Intro-Sort??? noch nie gehört...

volkard

Original erstellt von japro:
**ausserdem dürfte es langsamer sein als das stl sort wenn es auf schon sortierte oder rückwärts sortierte daten losgelassen wird. weil ich bei der median aus drei methode bis jetzt keine möglichkeit sah das mittlere element ziwschen zwei pointer zu finden (pointerarithmetik erlaubt ja kein / und *).
hat da wer ne idee?
**

begin+(end-begin)/2;
Das / geschieht nur auf nem int.

Gregor

@ Volkard : Kann es da nicht passieren, dass die Adresse, die man sich da berechnet - speziell in diesem Fall - auf keinen Objekt-"Anfang" zeigt, sondern irgendwo z.B. in die Mitte des Speicherplatzes, der von einem Objekt belegt wird? Das sollte doch zu Problemen führen, oder?

...sorry, falls die Frage dumm war! Ich kenne mich ja mit C++ und Pointern nicht aus!

japro

nein da im zusammenhang mit pointerarithmetik immer in der einheit der grösse der jeweiligen types gerechnet wird...
d.h.

int zahlen[100];
zahlen+=50;    //hier wird sozusagen zahlen+50*sizeof(int) gerechnet

dadurch sind die sich ergebenden pointer immer an ensprechenden grenzen ausgerichtet (ausser man castet wie wild in der gegend rum etc.)
zu den vergleichen... ich habs bis jetzt nur mit ints gemacht. da hat meine version bei einem array das mit rand() gefüllt wurde etwa nen durschnittlichen vorsprung von 5%... als noch nicht so der haufen...

Gregor

Ja! OK! Danke! Das habe ich verstanden. Mir ist aber noch nicht klar, ob das mit dem "/" auch klappt, da Volkard meinte, dass das auf einem int arbeitet. Naja! Ich werde das schon rauskriegen, wenn ich demnächst anfange, C++ zu lernen.

Ich hatte bei meinem Sort übrigens auch mal die Median-Variante ausprobiert. Ich habe aber inzwischen vergessen, warum ich diese Variante wieder verworfen hatte. Wahrscheinlich war sie mir nicht schnell genug! Es kann aber auch sein, dass ich die Variante mit dem Element in der Mitte des zu sortierenden Bereiches einfach etwas schöner fand. Ich würde diese Variante an deiner Stelle zumindest mal ausprobieren.

Hast du schonmal mit der 32 rumgespielt und sie testweise durch andere Zahlen ersetzt? Das könnte unter Umständen ein paar Prozent Geschwindigkeitszuwachs bringen. ...bei mir war die 18 optimal!

volkard

(end-begin) ist ein int.

japro

Original erstellt von Gregor:
Hast du schonmal mit der 32 rumgespielt und sie testweise durch andere Zahlen ersetzt? Das könnte unter Umständen ein paar Prozent Geschwindigkeitszuwachs bringen. ...bei mir war die 18 optimal!

jup hab sie auf 64 erhöht
ausserdem hab ich die rekursion rausgenommen subSort sieht jetzt wie folgt aus:

template<class T> void subSort(T *argbegin,T *argend)
{
 T *stack[128]; // 128 sollten reichen da kaum wer mehr als 4 gb sortieren wird
 unsigned stackptr=0;
 stack[stackptr++] = argend;
 stack[stackptr++] = argbegin;

 while(stackptr>0)
 {
  T *begin = stack[--stackptr];
  T *end = stack[--stackptr];

  T med[3] = {*begin, *(begin+(end-begin)/2), *end};
  med[1]=(med[0]<med[1])?med[1]:med[0];
  med[1]=(med[1]<med[2])?med[1]:med[2];
  T vgl = med[1];

  T *obegin = begin, *oend = end;
  do
  {

   while(*begin < vgl) ++begin;
   while(*end > vgl) --end;
   if (begin <= end)
   {
    T tmp = *begin;
    *begin = *end;
    *end = tmp;

    ++begin;
    --end;
   }

  }while(begin <= end);

  if ((end-obegin) > 64)
  {
   stack[stackptr++] = end;
   stack[stackptr++] = obegin;
  }
  if ((oend-begin) > 64)
  {
   stack[stackptr++] = oend;
   stack[stackptr++] = begin;
  }
 }
}

seltsamer weise wird das ganze langsamer wenn ich es inline mache oder in die mysort funktion direkt reinkopiere
leigt vielleicht daran wie der compiler optimiert...

<probier...>

wollts zuerst nicht glauben aber anstatt den median den mittelwert der beiden ersten werte zu nehmen hat noch nen temposchub gebracht... ist nur dann heikel wenn man mit pintern auf objecte arbeitet die überadene operatoren haben für vergeliche sich aber nicht dividieren lassen (mir fällt im moment kein beispiel ein). aber erstmal lass ich den mittelwert drinn. danke für den tip.

Gregor

OK! Ich habe es komplett verstanden, falls es so ist, dass bei end-begin der Abstand der beiden Adressen (in Byte) berechnet wird und dann implizit durch die Größe eines Elements geteilt wird.

Ist das so?

volkard

Original erstellt von japro:
ist nur dann heikel wenn man mit pintern auf objecte arbeitet die überadene operatoren haben für vergeliche sich aber nicht dividieren lassen (mir fällt im moment kein beispiel ein).

string

volkard

Original erstellt von Gregor:
OK! Ich habe es komplett verstanden, falls es so ist, dass bei end-begin der Abstand der beiden Adressen (in Byte) berechnet wird und dann implizit durch die Größe eines Elements geteilt wird.
Ist das so?

JO!

Gerard

Original erstellt von Gregor:
**OK! Ich habe es komplett verstanden, falls es so ist, dass bei end-begin der Abstand der beiden Adressen (in Byte) berechnet wird und dann implizit durch die Größe eines Elements geteilt wird.

Ist das so?**

jup

japro

man beachte den feinen unterschied LOL

Daniel E.

Original erstellt von japro:
**nein da im zusammenhang mit pointerarithmetik immer in der einheit der grösse der jeweiligen types gerechnet wird...
d.h.
int zahlen[100];
zahlen+=50;    //hier wird sozusagen zahlen+50*sizeof(int) gerechnet
**

Das hier ist nicht erlaubt. Ein Array ist kein veränderbarer L-Value und auch kein Zeiger.

Gregor

Moment! Wenn ich das richtig sehe, dann nimmst du jetzt den Median der drei Werte am Anfang, am Ende und in der Mitte des zu sortierenden Bereiches. Lass doch mal den Median ganz weg und nimm einfach den Wert in der Mitte des zu sortierenden Bereiches als Vergleichswert.

Wenn du einen Median nimmst, dann mußt du immer ein paar Vergleiche machen. Die kosten auf jedenfall Zeit. Außerdem kann es sein, dass der Vergleichswert dann der Wert am Anfang oder der Wert am Ende ist. Ich habe nicht genau gesehen, wie das bei dir abläuft, aber bei meinem Algorithmus würde er dann beim Sortieren den Vergleichswert andauernd hin und herschieben, was noch viel mehr Zeit kostet. Es kann aber sein, dass das bei dir anders funktioniert!

Edit : Wenn das mit dem Hin- und Herschieben bei dir nicht der Fall ist, dann sollte die Variante mit Median bei dir wahrscheinlich schneller sein, da das Quicksort dann etwas "gleichmäßiger" abläuft.

[ Dieser Beitrag wurde am 29.06.2002 um 21:41 Uhr von Gregor editiert. ]

Gregor

...danke für die Antworten!

japro

Original erstellt von Gregor:
Wenn du einen Median nimmst, dann mußt du immer ein paar Vergleiche machen. Die kosten auf jedenfall Zeit.

aber nur seeeehr wenig da sowieso mindestens 64 vergleiche in der funktion ausgeführt werden da spielen die 2 zusätlichen nimmer so ne roll. wenn ich hingegen einfach das mittlere element nehme kann es viel schneller vorkommen das es das grösste (oder jedenfalls eines das eher "am rand" ) ist. und das führt zu einer schlechten partitionierung und bremst viel mehr als diese 2 verlgeiche.
(wenn man sowieso nur einen wert nimmt kann man es sich sparen das mittlere auszurachenen da kann man auch einfach das erste nehmen...)

[edit]in diesem text sind ganz viele rechtschreib und orthographie fehler versteckt. finde sie! :p[/edit]

[ Dieser Beitrag wurde am 29.06.2002 um 21:58 Uhr von japro editiert. ]

Gregor

Ja! Ich habe auch gerade gesehen, dass bei deinem Sort nicht hin- und hergeschoben wird. Der Tipp wird dir also tatsächlich nichts bringen. Einer von uns beiden hat zumindest eigentlich nur etwas Quicksort-ähnliches programmiert. Wahrscheinlich war ich das. ...ich sollte mir nochmal irgendwo eine Beschreibung des Algorithmus durchlesen! ...vielleicht kriege ich mein Sort dann ja auch noch performanter!

Gregor

Bringt es in C++ eigentlich einen Geschwindigkeitszugewinn, wenn man Variablen nicht in Schleifen deklariert, sondern davor und in der Schleife nur eine Zuweisung macht? Kannst es ja mal testen auch, wenn es sehr wahrscheinlich nicht sehr viel bringt.

Sowas, wie "/2" in ">>1" umwandeln sollte ja eigentlich der Compiler selber machen, oder?

japro

so jetzt hab ich auch geschnallt was das mit dem introsort aufsich hat
hier n link auf ne postscript datei wos beschreiben is (english):
introsort