Questa non è davvero tanto una risposta in sé, come una risposta alla risposta di AraK al mio commento che l'ordinamento con una funzione anziché un funtore può essere più lento. Ecco un codice di prova (certamente brutto - troppa CnP) che confronta vari tipi di ordinamento: qsort, std :: sorta di vettore contro matrice e std :: sort utilizzando una classe template, una funzione template o una funzione plain per il confronto:
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
int compare(void const *a, void const *b) {
if (*(int *)a > *(int *)b)
return -1;
if (*(int *)a == *(int *)b)
return 0;
return 1;
}
const int size = 200000;
typedef unsigned long ul;
void report(char const *title, clock_t ticks) {
printf("%s took %f seconds\n", title, ticks/(double)CLOCKS_PER_SEC);
}
void wait() {
while (clock() == clock())
;
}
template <class T>
struct cmp1 {
bool operator()(T const &a, T const &b) {
return a < b;
}
};
template <class T>
bool cmp2(T const &a, T const &b) {
return a<b;
}
bool cmp3(int a, int b) {
return a<b;
}
int main(void) {
static int array1[size];
static int array2[size];
srand(time(NULL));
for (int i=0; i<size; i++)
array1[i] = rand();
const int iterations = 100;
clock_t total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
qsort(array2, size, sizeof(array2[0]), compare);
total += clock()-start;
}
report("qsort", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size);
total += clock()- start;
}
report("std::sort (array)", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size, cmp1<int>());
total += clock()- start;
}
report("std::sort (template class comparator)", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size, cmp2<int>);
total += clock()- start;
}
report("std::sort (template func comparator)", total);
total = 0;
for (int i=0; i<iterations; i++) {
memcpy(array2, array1, sizeof(array1));
wait();
clock_t start = clock();
std::sort(array2, array2+size, cmp3);
total += clock()- start;
}
report("std::sort (func comparator)", total);
total = 0;
for (int i=0; i<iterations; i++) {
std::vector<int> array3(array1, array1+size);
wait();
clock_t start = clock();
std::sort(array3.begin(), array3.end());
total += clock()-start;
}
report("std::sort (vector)", total);
return 0;
}
compilazione questo con VC++ 9/VS 2008 utilizzando cl /O2b2 /GL sortbench3.cpp, ottengo:
qsort took 3.393000 seconds
std::sort (array) took 1.724000 seconds
std::sort (template class comparator) took 1.725000 seconds
std::sort (template func comparator) took 2.725000 seconds
std::sort (func comparator) took 2.505000 seconds
std::sort (vector) took 1.721000 seconds
credo che questi cadano abbastanza pulito in tre gruppi: usando sorta con il confronto di default, e utilizzando la classe template prodotto il codice più veloce. L'uso della funzione o della funzione template è chiaramente più lento. L'uso di qsort è (a sorpresa per alcuni) il più lento di tutti, con un margine di 2: 1.
La differenza tra cmp2 e cmp3 sembra derivare interamente dal passaggio per riferimento rispetto al valore - se si modifica cmp2 per ottenere i suoi argomenti in base al valore, la sua velocità corrisponde esattamente a cmp3 (almeno nei miei test). La differenza è che se sapete che il tipo sarà int, passerete quasi certamente per valore, mentre per il generico T, di solito passerete con riferimento const (nel caso in cui sia qualcosa che è più costoso da copiare).
C++ 0x ha funzioni lambda e TR1 aggiunge il '' colpo di testa che rendono questo molto meno inutilmente prolisso. –
Omnifarious
+1 molto ben chiesto e risposto. Questo dovrebbe essere il post a cui sono collegati i futuri duplicati. –
@Omnifarious: sei sicuro che ci sia qualcosa in TR1/funzionale che aiuti in questo esempio rispetto a cosa potresti già fare in C++ 03? – Manuel