I która sytuacja będzie std :: map <A,B> będzie szybsza niż posortowana std :: vector <std :: pair <A,B>>?

Question

Używam map w jakimś kodzie do przechowywania zamówionych danych. Dowiedziałem się, że na ogromnych mapach zniszczenie może zająć trochę czasu. W tym kodzie miałem, zastępując map przez vector<pair> skrócenie czasu przetwarzania przez 10000 ...

Wreszcie, byłem tak zaskoczony, że postanowiłem porównać map występy z posortowanej vector lub pair.

I jestem zaskoczony, bo nie mógł znaleźć sytuację, w której map był szybszy niż klasyfikowane vector z pair (wypełniony losowo i później sortowane) ... musi istnieć pewne sytuacje, w których map jest szybsza .... indziej jaki sens ma zapewnienie tej klasy?

Oto co mam przetestowane:

testowy jeden, porównaj map napełnianie i niszcząc vs vector nadzieniem, sortowania (bo chcę posortowaną pojemnik) i niszcząc:

#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; 
} 

Zestawione ze g++ main.cpp -O3 -o main i dostał :

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

map „s 3 razy wolniej ...

Potem powiedział: "OK, vector jest szybsze wypełnienie i porządek, ale wyszukiwanie będzie szybsze z mapą" .... więc testowałem:

#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; 
} 

Zestawione ze g++ main.cpp -O3 -o main i otrzymała:

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 

Nawet wyszukiwania jest najwyraźniej szybciej z vector (10 wyszukiwaniach z map zajęło prawie 2 sek i zajęło zaledwie pół sekundy z vector) ....

A więc:

• Czy coś mi umknęło?
• Czy moje testy nie są poprawne/dokładne?
• Czy map jest po prostu klasą, której należy unikać, czy naprawdę istnieją sytuacje, w których map oferuje dobre wyniki?

Answer 1

Ogólnie rzecz biorąc wartość map będzie lepsza, jeśli wykonujesz wiele wstawień i usunięć przeplatanych z wynikami wyszukiwania. Jeśli zbudujesz strukturę danych tylko raz, a następnie przeprowadzisz tylko wyszukiwania, posortowana vector będzie prawie na pewno szybsza, choćby ze względu na efekty pamięci podręcznej procesora. Ponieważ insercje i delecje w dowolnych miejscach w wektorze są O (n) zamiast O (log n), nadejdzie moment, w którym staną się czynnikiem ograniczającym.

Answer 2

std::find ma liniowy czas złożoności, podczas gdy wyszukiwanie map ma złożoność logu N.

Gdy okaże się, że jeden algorytm jest 100000x szybszy od drugiego, należy podejrzewać! Twój benchmark jest nieprawidłowy.

Musisz porównać realistyczne warianty. Prawdopodobnie chodziło o porównanie mapy z wyszukiwarką binarną. Uruchom każdy z tych wariantów przez co najmniej 1 sekundę czasu procesora, aby móc realistycznie porównać wyniki.

Kiedy test porównawczy zwraca "0.00001 sekund" czasu spędzonego jesteś dobrze w hałas niedokładności zegara. Ta liczba nic nie znaczy.