4. STL sort schlagen

STL sort schlagen

  • G

    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!

    0
  • V

    (end-begin) ist ein int.

    0
  • J

    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.

    0
  • G

    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?

    0
  • V

    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

    0
  • V

    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!

    0
  • G

    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

    0
  • J

    man beachte den feinen unterschied 😃 LOL

    0
  • D

    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.

    0
  • G

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

    0
  • G

    ...danke für die Antworten! 🙂

    0
  • J

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

    0
  • G

    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!

    0
  • G

    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?

    0
  • J

    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

    0
  • H

    Wenns darum geht kleine Elemente zu sortieren ist aber immernoch der Radix-Sort ungeschlagen.

    0
  • V

    Original erstellt von Helium:
    Wenns darum geht kleine Elemente zu sortieren ist aber immernoch der Radix-Sort ungeschlagen.

    geht das mit strings?

    0
  • H

    Jein. Mit strings geht es, wenn Sie alle die gleiche länge haben. Außerdem sind sie meißt zu lang, so dass der *********** eher langsamer ist als intro.

    0
  • J

    ok ich bin jetzt gerade dabei mir ein introsort zu schreiben... und da ich wirklich alles selber machen will schreib ich mir auch das heapsort selber (interessanteres verfahren als ich dachte 😉 ).
    momentan hab ich folgendes:

    //swap
template<class T> inline void swap(T *a, T *b)
{
 T l_tmp = *a;
 *a = *b;
 *b = l_tmp;
}

/*downheap brint fehler im heap in ordnung der an position a_pos auftritt.
es beginnt beim start element a_pos und vergleicht es mit dem grösseren
der beiden child knoten und vertauscht gegebenenfalls*/
template<class T> inline void downheap(T array[], int a_pos, int a_max)
{
 int l_current = a_pos;
 int l_next = l_current*2;
 while(l_next < a_max)
 {
  if(l_next+1 < a_max)
      if(array[l_next] < array[l_next+1]) l_next++;

  if(array[l_next] < array[l_current]) break;

  swap(&array[l_next], &array[l_current]);

  l_current = l_next;
  l_next *= 2;
 }
}

//heapsort
template<class T> void heapsort(T *begin, T *end)
{
 T *l_array = begin-1; //da das erst element index 1 haben muss
 int l_lenght = end-begin;

 //heap inplace erzeugen neu (bottom-up)
 for(int n=l_lenght/2;n>=1;n--)
   downheap(l_array, n, l_lenght);

 //heap sortieren
 for(int n=l_lenght;n>=1;n--)
 {
  swap(&l_array[1], &l_array[n]);
  downheap(l_array, 1, n);
 }

}

    das ist im schnitt etwa 2.5 mal lanbgsamer als das stl sort (irgendwie klar) sieht noch jemand optimierungsmöglichkeiten?

    0
  • J

    so ich hab jetzt mal ein introsort gebaut und es ist jetzt etwa gleich schnell wie stl sort (nur das es nicht mit iteratoren umgehen kann)

    namespace sorting{

const int stopper = 32;

template<class T> inline int median3(const T a, const T b, const T c)
{
 if (a < b)
    if (b < c)
      return b;
    else if (a < c)
      return c;
    else
      return a;
  else if (a < c)
    return a;
  else if (b < c)
    return c;
  else
    return b;
}

//swap
template<class T> inline void swap(T *a, T *b)
{
 T tmp = *a;
 *a = *b;
 *b = tmp;
}

template<class T> inline T* partition(T *begin, T *end, T vgl)
{
 for(;;)
 {
  while(*begin < vgl)
    ++begin;

  --end;
  while(*end > vgl)
    --end;
  if(begin >= end)
    return begin;

  swap(begin, end);
  ++begin;
 }

 return begin;
}

template<class T> inline void downheap(T array[], int pos, int max)
{
 int current = pos;
 int next = current*2;
 while(next < max)
 {
  if(next+1 < max)
      if(array[next] < array[next+1])
          next++;

  if(array[next] < array[current])
      break;

  swap(&array[next], &array[current]);

  current = next;
  next *= 2;
 }
}

//heapsort
template<class T> void heapsort(T *begin, T *end)
{
 T *array = begin-1; //da das erst element index 1 haben muss
 int lenght = end-begin;

 //heap inplace erzeugen
 for(int n=lenght/2;n>=1;n--)
   downheap(array, n, lenght);

 //heap sortieren
 for(int n=lenght;n>=1;n--)
 {
  swap(&array[1], &array[n]);
  downheap(array, 1, n);
 }

}

template<class T> void insertionsort(T* begin, T* end)
{
 T* oldbegin = begin;
 for(; begin<end ; begin++)
 {
  T vgl = *begin;
  T *current = begin;
  while(current-1 >= oldbegin)
  {
   T *deccurrent = current-1;
   if(*deccurrent <= vgl) break;
   *current = *deccurrent;
   current = deccurrent;
  }
  *current = vgl;
 }
}

template<class T> void introsortloop(T *begin, T *end, int depht)
{
 while(end-begin > stopper)
 {
  if(depht <= 0)
  {
   heapsort(begin, end);
   return;
  }
  T *part = partition(begin, end, median3(*begin, *(begin+(end-begin)/2), *(end-1)));

  introsortloop(begin, part, --depht);
  begin = part+1;
 }
}

template<class T> inline void introsort(T *begin, T *end)
{
 int lenght = end-begin;

 introsortloop(begin, end, 2*pow(log(lenght),2) );

 insertionsort(begin, end);
}

}

    hat noch wer ideen?

    [ Dieser Beitrag wurde am 05.07.2002 um 10:25 Uhr von japro editiert. ]

    [ Dieser Beitrag wurde am 05.07.2002 um 15:55 Uhr von japro editiert. ]

    0
Anmelden zum Antworten