STL sort schlagen
-
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?
-
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
-
Wenns darum geht kleine Elemente zu sortieren ist aber immernoch der Radix-Sort ungeschlagen.
-
Original erstellt von Helium:
Wenns darum geht kleine Elemente zu sortieren ist aber immernoch der Radix-Sort ungeschlagen.geht das mit strings?
-
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.
-
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?
-
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. ]
-
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.
-
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. ]
-
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...