4. STL sort schlagen

STL sort schlagen

  • 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
  • H

    Ich sehe nichst wirklich bahnbrechendes. Statt pow(..., 2) kann man auch (... * ...) schreiben, was schneller ist, hier wohl aber nichsts zur Sache tut.

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

 introsortloop(begin, end, 2*depth*depth );

 insertionsort(begin, end);
}

}

    solche kleinigkeiten lassen sich bestimmt auch noch wo anders finden.

    0
  • J

    ich hab mal noch so aus spass ein binary sort implementiert... aber achtung das teil ist nur auf 32 bittige signed integer anwendbar 😃
    es hält mit dem stl sort besser mit als ich dachte... im schlimmsten fall hat es doppelt so lange gebraucht (getestet habe ich bis 50'000'000 ints)

    void binsort(int A[], int l, int r, int bit=31)
{
   while(bit>=0 && r>l)
   {
      int muster = 1<<bit;
      int i=l, j=r;
      if(bit<31)
      {
         for(;;)
         {
            while(!(A[i] & muster) && i<=j)
               ++i;

            while((A[j] & muster) && i<=j)
               --j;

            if(i>j)
               break;

            int chg = A[i];
            A[i] = A[j];
            A[j] = chg;
         }
      }
      else
      {
         for(;;)
         {
            while((A[i] & muster) && i<=j)
               ++i;

            while(!(A[j] & muster) && i<=j)
               --j;

            if(i>j)
               break;

            int chg = A[i];
            A[i] = A[j];
            A[j] = chg;
         }
      }
      if(j-l>r-i)
      {
         binsort(A, i, r, --bit);
         r=j;
      }
      else
      {
         binsort(A, l, j, --bit);
         l=i;
      }

   }
}

    [ Dieser Beitrag wurde am 26.09.2002 um 19:29 Uhr von japro editiert. ]

    0
  • S

    ich duelliere mich auch hin und wieder mit der Dinkumware STL - aber verliere immer 😞

    Ab und zu bin ich fast gleich schnell *g*

    Naja, bis ich so gut bin wie die STL Implementoren brauch ich wohl noch n paar Jahrhunderte...

    0
Anmelden zum Antworten