Collisions dans unordered_multimap lors de l'itération dans bucket via local_it

Question

Dans le code ci-dessous, j'ai un certain nombre de chaînes (séquences d'ADN) que je stocke dans un vecteur. J'ai un struct, read_tag que j'utilise pour identifier chaque chaîne; read_tag.read_id est l'identificateur de chaîne. Je prends 30 sous-chaînes de caractères de chaque chaîne et l'utilise comme une clé dans un unordered_multimap avec le read_tag comme valeur; le but est de grouper des chaînes qui partagent une séquence de 30 caractères. Naturellement, une chaîne identique aura la même valeur et se retrouvera dans le même compartiment de la carte multiple. Offset est utilisé pour donner le "décalage" de l'index zéro de l'étiquette de 30 caractères. Cependant, lorsque j'exécute ce code, je traverse chaque compartiment en itération; Je trouve qu'il y a plusieurs séquences différentes dans le même seau. Je pensais que les collisions ont été résolues en unordered_mutlimap, et donc dans un seau, leur devrait être juste une clé (chaîne). Je comprends que la collision peut se produire, mais j'ai pensé que l'un ou l'autre chaînage, sondage, etc. a été implémenté dans unordered_mutlimap. Vous devriez être en mesure d'exécuter et de vérifier la sortie pour voir où je suis confus.

Je ai également std::hash chaque clé, un dans un seau, et je trouve que les clés dans les "collisions" ont une valeur de hachage différente. Donc, c'est comme si des collisions se produisaient, entraînant des valeurs avec diff. clés dans le même seau, mais en contradiction, les clés hachées à différents vals. Est-ce un moyen d'éviter cela et de différencier les valeurs en fonction des clés dans les compartiments? Ou ai-je besoin de mettre en œuvre ceci?

#include <iostream>                     
#include <string>                      
#include <unordered_map>                    
#include <vector>                      
#include <functional>                     

using namespace std;                     


int main() {                       


    vector<string> reads;                    

    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC"); 
    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC"); 
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG"); 
    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC"); 
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG"); 
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG"); 
    reads.push_back("GGCAGGGTCATACCCGATTAACTTGTTATAGAGTATGGGGCATCAACTTGGGCAGCAATGGGGAACGGTGTCTCTGGAAG"); 
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA"); 
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA"); 
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA"); 
    reads.push_back("CCGGGCGTGGTGGCGTGCACCTGTAATCCCAGCTACTTGGGATGTTCAGGCAGGAGACTCGCTTGATCCCCGGGGACGGA"); 
    reads.push_back("CCAGCTGCTCTCACCCTGGGCAGGGTCCCTGCACACACTGTATCTTTTGAGGTCCCTTCAGGACCCCGGTTTGCTGCCTC"); 

    struct read_tag{                      
    unsigned int read_id; // unique string identifier                   
    int offset;    // shift of 30 character substring represented by tag                                    
    };                         

    unordered_multimap<string, read_tag> mutation_grouper;            

    for(int read_id=0; read_id < reads.size(); read_id++) {            
    string read = reads[read_id];                        
    for(int i=0; i < read.size()-30; i++) {                                
     string sub_read = read.substr(i, 30);               
     read_tag next_tag;                    
     pair<string, read_tag> key_val;                 

     next_tag.read_id = read_id;                  
     next_tag.offset = i;                                    

     key_val.first = sub_read;                  
     key_val.second = next_tag;                  

     mutation_grouper.insert(key_val);                
    }                         
    }                         

    cout << "mutation_grouper buckets" << endl;               
    std::hash<std::string> hash_er;                  

    for(unsigned int bucket = 0; bucket < mutation_grouper.bucket_count(); bucket++) { 

    cout << "Bucket: " << bucket << endl;              
    for(auto local_it = mutation_grouper.begin(bucket);          
    local_it != mutation_grouper.end(bucket); ++local_it) {        

     cout << local_it->first << " : " << local_it->second.read_id       
     << ", " << local_it->second.offset << ", " << endl;            

     cout << "hash value: " << local_it->first <<"::: " << hash_er(local_it->first) << endl; 

    }                       
    cout << endl << endl;                  
    }                       
}  

Answer 1

Oui, vous avez raison. Il n'est pas garanti que deux articles différents atterrissent dans deux seaux différents. Vous savez seulement que deux mêmes objets atterrissent dans le même seau.

La solution à votre problème est simplement d'éviter les godets.La classe unordered_multimap (ainsi que multimap) a la méthode equal_range, qui vous donne la plage d'éléments avec une clé spécifique. Vous n'avez donc qu'à parcourir toutes les clés et utiliser equal_range pour parcourir toutes les valeurs. Malheureusement, il n'y a pas de méthode, qui vous permet d'itérer sur les touches, donc vous devez être un peu difficile. Le code suivant devrait vous donner la sortie désirée:

// iterate through all elements in the multimap 
// don't worry, we'll skip a bunch 
for (auto it = mutation_grouper.begin(); it != mutation_grouper.end();) 
{ 
    // Get the range of the current key 
    auto range = mutation_grouper.equal_range(it->first); 

    // Print all elements of the range 
    cout << it->first << endl; 
    for (auto local_it = range.first; local_it != range.second; ++local_it) 
     std::cout << " " << local_it->second.read_id << " " << local_it->second.offset << '\n'; 

    // Step to the end of the range 
    it = range.second; 
} 

Answer 2

Donc, pour tous ceux qui étaient intéressés. J'ai trouvé ceci dans la norme

[C++ 11: 23.2.5/5]: Deux valeurs k1 et k2 de type Key sont considérées comme équivalentes si l'objet de fonction key_equal du conteneur renvoie vrai lorsqu'il est passé à ces valeurs. Si k1 et k2 sont équivalents, la fonction de hachage doit renvoyer la même valeur pour les deux. [..]

[C++ 11: 23.2.5/8]: Les éléments d'un conteneur associatif non ordonné sont organisés en compartiments. Les clés avec le même code de hachage apparaissent dans le même compartiment. Par conséquent, deux valeurs avec la même clé finiront toujours dans le même compartiment, mais des clés ayant des valeurs différentes pourraient également aboutir dans ces segments. Donc, je suppose que la mise en œuvre peut être plus intelligente et promouvoir réellement ces situations; Une raison pour laquelle je pourrais y penser pour réduire le nombre de seaux. Vous pouvez voir à partir de la sortie que les compartiments remplis sont clairsemés; et plus nous approcherons des tables d'adresses directes (tableau de vecteurs, indexé par le hachage), nous nous retrouverons avec un univers géant de clés potentielles, avec un nombre gigantesque de slots vides, contre lesquels les tables de hachage se protègent. Donc, cela semble être une optimisation raisonnable de l'espace. Pour cette raison, j'ai choisi d'utiliser multimap à la place. Les raisons sont que, les valeurs dans multimap sont ordonnées en fonction de la clé, de sorte que je peux faire un seul passage à travers les valeurs de regroupement en fonction des clés. En unordered_multimap une fois que j'atteins un seau (en O (1) parce que c'est une table de hachage) il n'y a pas de commande par clé, donc je ne peux pas prendre un passage linéaire dans le seau pour grouper des séquences.