Hallo,
ich stehe im Moment vor dem Problem aus einem relativ kleinem Array mit ca 100-300 Elementen die 10-30 kleinsten Elemente möglichst effizient zu suchen.
Mein Vorgehen dabei war bisher immer ein Array von Pointer auf die kleinsten Elemente des Array mit einer Art Selectionsort auszurichten. Mir geht es dabei um maximal mögliche Performance, da ich dieses Verfahren sehr oft hintereinander ausführen muss und ich derzeit Laufzeiten von mehreren Tage habe, die bisher zu ~70% vom Sortieren resultieren.
Daher wäre ich sehr dankbar wenn Ihr einen Blick auf meine Sortierfunktion werfen könntet und evtl. Schwachstellen und schlechten Programmierstil finden könntet oder gar einen besseren Algorithmus empfehlen könnt der vlt sogar in einer Library implementiert ist.
Parallelisieren ist dabei nicht erforderlich, da der Sortieralgorithmus Teil einer Rechnung ist die mit openmp mehrfach parallel ausgeführt wird.
Hier ist mal ein minimal Beispiel. Der Sortier Algorithmus ist hierbei die erste Funktion. In der Main Funktion wird die Funktion dann ein paar Mal zur Laufzeit Messung aufgerufen und anschließend der Sortier Algorithmus mit qsort aus der STL überprüft:
Compiliert und getestet hab ich den Code mit gcc 4.8.1 unter ubuntu.
Vielen Dank fürs Lesen und ggf. Tipps!!
ich stehe im Moment vor dem Problem aus einem relativ kleinem Array mit ca 100-300 Elementen die 10-30 kleinsten Elemente möglichst effizient zu suchen.
Mein Vorgehen dabei war bisher immer ein Array von Pointer auf die kleinsten Elemente des Array mit einer Art Selectionsort auszurichten. Mir geht es dabei um maximal mögliche Performance, da ich dieses Verfahren sehr oft hintereinander ausführen muss und ich derzeit Laufzeiten von mehreren Tage habe, die bisher zu ~70% vom Sortieren resultieren.
Daher wäre ich sehr dankbar wenn Ihr einen Blick auf meine Sortierfunktion werfen könntet und evtl. Schwachstellen und schlechten Programmierstil finden könntet oder gar einen besseren Algorithmus empfehlen könnt der vlt sogar in einer Library implementiert ist.
Parallelisieren ist dabei nicht erforderlich, da der Sortieralgorithmus Teil einer Rechnung ist die mit openmp mehrfach parallel ausgeführt wird.
Hier ist mal ein minimal Beispiel. Der Sortier Algorithmus ist hierbei die erste Funktion. In der Main Funktion wird die Funktion dann ein paar Mal zur Laufzeit Messung aufgerufen und anschließend der Sortier Algorithmus mit qsort aus der STL überprüft:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 300
#define K 5
inline void __attribute__((always_inline)) psort(double* array, int n, double** pointer_array, int k)
{
register int i,j;
// Ersten zwei Elemente des Arrays vergleichen und Pointer initialisieren
if( array[0] < array[1] )
{
pointer_array[0] = &array[0];
pointer_array[1] = &array[1];
}
else
{
pointer_array[0] = &array[1];
pointer_array[1] = &array[0];
}
// Nächsten Elemente des Arrays bis k vergleichen und Pointer damit initialisieren
for(i=2; i != k; ++i)
{
if( *pointer_array[i-1] < array[i] )
{
pointer_array[i] = &array[i];
}
else
{
pointer_array[i] = pointer_array[i-1];
j = 0;
while( j != (i-1) && *pointer_array[i-2-j] > array[i] )
{
pointer_array[i-1-j] = pointer_array[i-2-j];
++j;
}
pointer_array[i-1-j] = &array[i];
}
}
//Jetzt restlichen Elemente des Arrays mit größtem Pointer vergleichen (ggf mit nächst kleineren Pointer vergleichen) und einsortieren
for(i=k; i != n; ++i)
{
if( *pointer_array[k-1] < array[i] )
{
continue;
}
else
{
j=0;
while(*pointer_array[k-2-j] > array[i] && j != (k-1) )
{
pointer_array[k-1-j]=pointer_array[k-2-j];
++j;
}
pointer_array[k-1-j]=&array[i];
}
}
}
//Vergleichs Funktion für qsort zum Überprüfen der Richtigkeit des Sortier Algorithmus
int cmpfunc(const void * a, const void * b)
{
if ( *(double*)a < *(double*)b ) return -1;
if ( *(double*)a == *(double*)b ) return 0;
if ( *(double*)a > *(double*)b ) return 1;
}
int main(void)
{
//Array definieren und mit Zufallszahlen füllen
double array[N];
int i;
for(i=0; i<N; ++i) array[i]= ( rand() / (double)RAND_MAX ) * 100.0 ;
//Pointer array
double *pointer_array[K];
clock_t start, ende;
start=clock();
for(i=0; i<900000;++i) psort(array, N, pointer_array, K);
ende=clock();
printf("\n\n\tDauer in Sekunden: %f\n", (double)(ende-start)/(double)CLOCKS_PER_SEC );
printf("\nKleinsten Elemente:\n");
for(i=0; i<K; ++i ) printf("%f \t", *pointer_array[i]);
printf("\n\nKleinsten Elemente mit QSORT:\n");
qsort(array, N, sizeof(double), cmpfunc);
for(i=0; i<K; ++i )printf("%f \t", array[i]);
return 0;
}Vielen Dank fürs Lesen und ggf. Tipps!!
Die STL ist ein Teil der Standard-Bibliothek von C++, während du hier offenbar mit C arbeitest. Wenn es dir aber wirklich um maximale Performance beim Sortieren geht, würde ich dir in diesem Fall tatsächlich den Umstieg auf C++ nahelegen, denn in C++ gibt eine std::sort()-Template-Funktion, die in der Regel wesentlich fixer ist, als das alte qsort() aus der C-Bilbiothek. Das liegt daran, daß std::sort() ein Template ist und die übergebene Vergleichsfunktion ge-inline'd werden kann, während qsort() seine Vergleichsfunktion als Pointer übergeben bekommt (da kann selten was ge'inline'd werden).
