Quel type de conteneur offre de meilleures performances (moyennes) que std :: map?

Question

Dans l'exemple suivant, une structure std :: map est remplie avec 26 valeurs de A - Z (pour la clé) et 0 - 26 pour la valeur. Le temps pris (sur mon système) pour rechercher la dernière entrée (10000000 fois) est d'environ 250 ms pour le vecteur et de 125 ms pour la carte. (J'ai compilé en utilisant le mode release, avec l'option O3 activée pour g ++ 4.4)

Mais si pour une raison étrange je voulais de meilleures performances que std :: map, quelles structures de données et fonctions devrais-je utiliser? Je m'excuse si la réponse vous semble évidente, mais je n'ai pas beaucoup d'expérience dans les aspects critiques de la programmation C++.

#include <ctime> 
#include <map> 
#include <vector> 
#include <iostream> 

struct mystruct 
{ 
    char key; 
    int value; 

    mystruct(char k = 0, int v = 0) : key(k), value(v) { } 
}; 

int find(const std::vector<mystruct>& ref, char key) 
{ 
    for (std::vector<mystruct>::const_iterator i = ref.begin(); i != ref.end(); ++i) 
     if (i->key == key) return i->value; 

    return -1; 
} 

int main() 
{ 
    std::map<char, int> mymap; 
    std::vector<mystruct> myvec; 

    for (int i = 'a'; i < 'a' + 26; ++i) 
    { 
     mymap[i] = i - 'a'; 
     myvec.push_back(mystruct(i, i - 'a')); 
    } 

    int pre = clock(); 

    for (int i = 0; i < 10000000; ++i) 
    { 
     find(myvec, 'z'); 
    } 

    std::cout << "linear scan: milli " << clock() - pre << "\n"; 

    pre = clock(); 

    for (int i = 0; i < 10000000; ++i) 
    { 
     mymap['z']; 
    } 

    std::cout << "map scan: milli " << clock() - pre << "\n"; 

    return 0; 
} 

Answer 1

Pour votre exemple, utilisez int value(char x) { return x - 'a'; }

plus générale, étant donné que les « clés » sont continues et denses, utilisez un tableau (ou vecteur) pour garantir Θ (1) temps d'accès.

Si vous n'avez pas besoin des clés à trier, use unordered_map, qui devrait fournir une amélioration logarithmique amortie (c'est-à-dire O (log n) -> O (1)) pour la plupart des opérations.

(parfois pour les petits ensembles de données, la recherche linéaire est plus rapide que la table de hachage (unordered_map)/les arbres binaires équilibrés (map) car le premier a un algorithme beaucoup plus simple. Profil, profil, profil.)

Answer 2

Pour commencer, vous devez probablement utiliser std::map::find si vous souhaitez comparer les heures de recherche; operator[] a des fonctionnalités supplémentaires en plus de la recherche régulière.

De plus, votre jeu de données est assez petit, ce qui signifie que le vecteur entier peut facilement s'adapter au cache du processeur; Beaucoup de processeurs modernes sont optimisés pour ce type de recherche en force brute, ce qui vous permet d'obtenir de bonnes performances. La carte, bien qu'ayant théoriquement de meilleures performances (O (log n) plutôt que O (n)) ne peut pas vraiment exploiter son avantage du plus petit nombre de comparaisons car il n'y a pas beaucoup de clés à comparer et le surcoût de ses la disposition des données fonctionne contre cela. TBH pour des structures de données aussi petites, le gain de performance supplémentaire de ne pas utiliser un vecteur est souvent négligeable. Les structures de données «plus intelligentes» telles que std::map entrent en jeu lorsque vous traitez de grandes quantités de données et un ensemble de données bien réparti que vous recherchez.

Answer 3

Si vous avez vraiment avoir des valeurs pour toutes les entrées de A à Z, pourquoi ne pas utiliser la lettre (correctement ajustée) que l'indice dans un vecteur ?:

std::vector<int> direct_map; 
direct_map.resize(26); 

for (int i = 'a'; i < 'a' + 26; ++i) 
{ 
    direct_map[i - 'a']= i - 'a'; 
} 

// ... 

int find(const std::vector<int> &direct_map, char key) 
{ 
    int index= key - 'a'; 
    if (index>=0 && index<direct_map.size()) 
     return direct_map[index]; 

    return -1; 
}