Credo che se dovessi provare qualcosa di simile, probabilmente sarei iniziare con qualcosa di codice in questo ordine:
#include <list>
#include <vector>
#include <algorithm>
#include <deque>
#include <time.h>
#include <iostream>
#include <iterator>
static const int size = 30000;
template <class T>
double insert(T &container) {
srand(1234);
clock_t start = clock();
for (int i=0; i<size; ++i) {
int value = rand();
T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
container.insert(pos, value);
}
// uncomment the following to verify correct insertion (in a small container).
// std::copy(container.begin(), container.end(), std::ostream_iterator<int>(std::cout, "\t"));
return double(clock()-start)/CLOCKS_PER_SEC;
}
template <class T>
double del(T &container) {
srand(1234);
clock_t start = clock();
for (int i=0; i<size/2; ++i) {
int value = rand();
T::iterator pos = std::lower_bound(container.begin(), container.end(), value);
container.erase(pos);
}
return double(clock()-start)/CLOCKS_PER_SEC;
}
int main() {
std::list<int> l;
std::vector<int> v;
std::deque<int> d;
std::cout << "Insertion time for list: " << insert(l) << "\n";
std::cout << "Insertion time for vector: " << insert(v) << "\n";
std::cout << "Insertion time for deque: " << insert(d) << "\n\n";
std::cout << "Deletion time for list: " << del(l) << '\n';
std::cout << "Deletion time for vector: " << del(v) << '\n';
std::cout << "Deletion time for deque: " << del(d) << '\n';
return 0;
}
Dal momento che utilizza clock, questo dovrebbe dare il tempo processore non parete di tempo (anche se alcuni compilatori come MS VC++ si sbagliano). Non cerca di misurare il tempo per l'inserimento esclusivo del tempo per trovare il punto di inserimento, dal momento che 1) richiederebbe un po 'più di lavoro e 2) Non riesco ancora a capire cosa potrebbe ottenere. È certamente non rigoroso al 100%, ma vista la disparità che ne vedo, sarei un po 'sorpreso nel notare una differenza significativa rispetto ai test più accurati. Ad esempio, con MS VC++, ottengo:
Insertion time for list: 6.598
Insertion time for vector: 1.377
Insertion time for deque: 1.484
Deletion time for list: 6.348
Deletion time for vector: 0.114
Deletion time for deque: 0.82
con GCC ottengo:
Insertion time for list: 5.272
Insertion time for vector: 0.125
Insertion time for deque: 0.125
Deletion time for list: 4.259
Deletion time for vector: 0.109
Deletion time for deque: 0.109
Factoring il tempo di ricerca sarebbe un po 'non banale, perché si avrebbe in volta ogni iterazione separatamente . Avresti bisogno di qualcosa di più preciso di clock (di solito lo è) per ottenere risultati significativi da quello (più sull'ordine o leggendo un registro del ciclo di clock). Sentiti libero di modificarlo se lo ritieni opportuno - come ho detto sopra, mi manca la motivazione perché non riesco a vedere come sia una cosa sensata da fare.
fonte
2012-03-19 04:37:27
Non è affatto chiaro cosa intendi su "...inserendo ed eliminando elementi che possono essere fatti prima, in modo che non influenzino i tempi? "Se si sta inserendo e cancellando i tempi, si vuole chiaramente che l'inserimento e la cancellazione influenzino i tempi. –
Sì, ma non voglio la determinazione di dove il punto di inserimento/cancellazione sarà quello di far parte dei tempi – soandos
Oh, capisco ... E a parte cercare di rendere un elenco più competitivo, perché esattamente vorresti farlo? tutto ciò che riguarda l'uso del mondo reale. –