I in quale situazione sarà std :: map <A,B> essere più veloce di std :: vector <std :: pair <A,B>> ordinato?

Question

Stavo usando uno map in qualche codice per memorizzare i dati ordinati. Ho scoperto che per le mappe enormi, la distruzione potrebbe richiedere del tempo. In questo codice ho avuto, in sostituzione di map da vector<pair> ridotto il tempo di elaborazione da parte di 10000 ...

Infine, ero così sorpreso che ho deciso di confrontare map prestazioni con ordinato vector o pair.

E sono sorpreso perché non riuscivo a trovare una situazione in cui map era più veloce di un ordinato vector di pair (riempito in modo casuale e in seguito ordinato) ... ci devono essere alcune situazioni in cui map è più veloce .... altro qual è il punto nel fornire questa classe?

Ecco cosa ho provato:

prova uno, confrontare map riempimento e distruggendo vs vector di riempimento, l'ordinamento (perché voglio un contenitore ordinato) e distruggendo:

#include <iostream> 
#include <time.h> 
#include <cstdlib> 
#include <map> 
#include <vector> 
#include <algorithm> 

int main(void) 
{ 

    clock_t tStart = clock(); 

    { 
     std::map<float,int> myMap; 
     for (int i = 0; i != 10000000; ++i) 
     { 
      myMap[ ((float)std::rand())/RAND_MAX ] = i; 
     } 
    } 

    std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl; 

    tStart = clock(); 

    { 
     std::vector< std::pair<float,int> > myVect; 
     for (int i = 0; i != 10000000; ++i) 
     { 
      myVect.push_back(std::make_pair(((float)std::rand())/RAND_MAX, i)); 
     } 

     // sort the vector, as we want a sorted container: 
     std::sort(myVect.begin(), myVect.end()); 
    } 

    std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl; 

    return 0; 
} 

compilato con g++ main.cpp -O3 -o main e ottenuto :

Time taken by map: 21.7142 
Time taken by vect: 7.94725 

s' map 3 volte più lento ...

Poi, ho detto, "OK, il vettore è più veloce da riempire e tipo, ma di ricerca sarà più veloce con la mappa" .... così ho provato:

#include <iostream> 
#include <time.h> 
#include <cstdlib> 
#include <map> 
#include <vector> 
#include <algorithm> 

int main(void) 
{ 
    clock_t tStart = clock(); 

    { 
     std::map<float,int> myMap; 
     float middle = 0; 
     float last; 
     for (int i = 0; i != 10000000; ++i) 
     { 
      last = ((float)std::rand())/RAND_MAX; 
      myMap[ last ] = i; 
      if (i == 5000000) 
       middle = last; // element we will later search 
     } 

     std::cout << "Map created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl; 

     float sum = 0; 
     for (int i = 0; i != 10; ++i) 
      sum += myMap[ last ]; // search it 

     std::cout << "Sum is " << sum << std::endl; 
    } 

    std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl; 

    tStart = clock(); 

    { 
     std::vector< std::pair<float,int> > myVect; 
     std::pair<float,int> middle; 
     std::pair<float,int> last; 
     for (int i = 0; i != 10000000; ++i) 
     { 
      last = std::make_pair(((float)std::rand())/RAND_MAX, i); 
      myVect.push_back(last); 
      if (i == 5000000) 
       middle = last; // element we will later search 
     } 

     std::sort(myVect.begin(), myVect.end()); 

     std::cout << "Vector created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl; 

     float sum = 0; 
     for (int i = 0; i != 10; ++i) 
      sum += (std::find(myVect.begin(), myVect.end(), last))->second; // search it 

     std::cout << "Sum is " << sum << std::endl; 
    } 

    std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl; 

    return 0; 
} 

compilato con g++ main.cpp -O3 -o main ed ho ottenuto:

Map created after 19.5357 
Sum is 1e+08 
Time taken by map: 21.41 
Vector created after 7.96388 
Sum is 1e+08 
Time taken by vect: 8.31741 

Anche ricerca è apparentemente più veloce con le vector (10 ricerche con il map sono voluti quasi 2 sec e ci sono voluti solo mezzo secondo con la vector) ....

Quindi:

• Mi sono perso qualcosa?
• I miei test non sono corretti/precisi?
• È map semplicemente una classe da evitare o esistono davvero situazioni in cui lo map offre buone prestazioni?

Answer 1

Generalmente uno map sarà migliore quando si eseguono un sacco di inserimenti e cancellazioni inframezzate con le proprie ricerche. Se si costruisce la struttura dei dati una sola volta e poi si eseguono solo ricerche, un ordinamento vector sarà quasi sicuramente più veloce, se non altro a causa degli effetti della cache del processore. Poiché le inserzioni e le delezioni in posizioni arbitrarie in un vettore sono O (n) invece di O (log n), arriverà un punto in cui quelle diventeranno il fattore limitante.

Answer 2

std::find ha una complessità temporale lineare mentre una ricerca map presenta una complessità del registro N.

Quando si trova che un algoritmo è 100000x più veloce dell'altro, si dovrebbe diventare sospettosi! Il tuo benchmark non è valido.

È necessario confrontare varianti realistiche. Probabilmente, intendevi confrontare la mappa con una ricerca binaria. Esegui ciascuna di queste varianti per almeno 1 secondo del tempo della CPU in modo da poter confrontare realisticamente i risultati.

Quando un punto di riferimento restituisce "0,00001 secondi" di tempo trascorso, si ha un discreto errore nell'orologio. Questo numero non significa nulla.