Unordered_set questions

Question

Quelqu'un pourrait-il expliquer comment fonctionne un ensemble non ordonné? Je ne suis pas sûr non plus comment fonctionne un ensemble. Ma question principale est quelle est l'efficacité de sa fonction de recherche.

Par exemple, quel est le temps d'exécution total du gros O?

vector<int> theFirst; 
    vector<int> theSecond; 
    vector<int> theMatch; 

    theFirst.push_back(-2147483648); 
    theFirst.push_back(2); 
    theFirst.push_back(44); 


    theSecond.push_back(2); 
    theSecond.push_back(-2147483648); 
    theSecond.push_back(33); 


    //1) Place the contents into a unordered set that is O(m). 
    //2) O(n) look up so thats O(m + n). 
    //3) Add them to third structure so that's O(t) 
    //4) All together it becomes O(m + n + t) 
    unordered_set<int> theUnorderedSet(theFirst.begin(), theFirst.end()); 

    for(int i = 0; i < theSecond.size(); i++) 
    { 
     if(theUnorderedSet.find(theSecond[i]) != theUnorderedSet.end()) 
     { 
     theMatch.push_back(theSecond[i]); 
     cout << theSecond[i]; 
     } 
    } 

Answer 1

Tous les types de données std :: unordered _ *() utilisent un hachage pour effectuer des recherches. Regardez la documentation de Boost sur le sujet et je pense que vous comprendrez très rapidement.

http://www.boost.org/doc/libs/1_46_1/doc/html/unordered.html

Answer 2

unordered_set et toutes les autres structures de données unordered_ utiliser le hachage, comme mentionné par @Sean. Le hachage implique un temps constant amorti pour l'insertion, et proche du temps constant pour la recherche. Une fonction de hachage prend essentiellement certaines informations et en produit un nombre. C'est une fonction dans le sens où la même entrée doit produire la même sortie. Cependant, différentes entrées peuvent entraîner la même sortie, ce qui se traduit par ce que l'on appelle une collision. Lookup serait garanti pour être un temps constant pour une "fonction de hachage parfaite", c'est-à-dire, sans collisions. En pratique, le numéro d'entrée provient de l'élément que vous stockez dans la structure (disons que c'est une valeur, c'est un type primitif) et le mappe à un emplacement dans une structure de données. Ainsi, pour une clé donnée, la fonction vous emmène à l'endroit où l'élément est stocké sans avoir besoin de traversées ou de recherches (en ignorant ici les collisions pour plus de simplicité), donc de temps constant. Il existe différentes implémentations de ces structures (adressage ouvert, chaînage, etc.). Voir hash table, hash function. Je recommande également la section 3.7 de The Algorithm Design Manual par Skiena. Maintenant, concernant la complexité big-O, vous avez raison d'avoir O (n) + O (n) + O (taille de chevauchement). Puisque le chevauchement ne peut pas être plus grand que le plus petit de m et n, la complexité globale peut être exprimée par O (kN), où N est le plus grand entre m et n. Bientôt). Encore une fois, c'est "le meilleur des cas", sans collisions, et avec un hachage parfait. D'autre part, utiliser des arbres binaires, donc les insertions et les recherches sont typiquement O (logN). La performance réelle d'une structure hachée par rapport à celle d'un arbre binaire dépendra de N, il est donc préférable d'essayer les deux approches et de les profiler dans un scénario de fonctionnement réaliste.