Коллизии в unordered_multimap при переборе корзины через local_it

В приведенном ниже коде у меня есть ряд строк (последовательностей ДНК), которые я сохраняю в векторе. У меня есть struct, read_tag, которые я использую для идентификации каждой строки; read_tag.read_id — идентификатор строки. Я беру 30-символьные подстроки каждой строки и использую их как ключ в unordered_multimap с read_tag в качестве значения; цель состоит в том, чтобы сгруппировать строки, которые имеют общую последовательность из 30 символов. Естественно, идентичная строка будет хэшироваться до одного и того же значения и попадет в одно и то же ведро на мультикарте. Смещение используется для указания «сдвига» от нулевого индекса 30-символьного тега.

Однако, когда я запускаю этот код, перебирая каждое ведро; Я обнаружил, что в одном и том же ведре есть несколько разных последовательностей. Я думал, что коллизии были разрешены в unordered_mutlimap, и поэтому в ведре их должен быть только один ключ (строка). Я понимаю, что может произойти столкновение, но я думал, что в unordered_mutlimap реализовано либо цепочка, либо зондирование и т.д. Вы должны иметь возможность запустить и проверить вывод, чтобы увидеть, где я запутался.

Я также std::hash каждый ключ, один в ведре, и я обнаружил, что ключи в "столкновениях" имеют другое значение хеш-функции.

Итак, как будто происходят коллизии, в результате чего получаются значения с diff. keys в одном и том же сегменте, но, наоборот, ключи хэшируются в разные значения. Это способ избежать этого и различать значения на основе ключей внутри сегментов? Или мне нужно реализовать это?

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

c++ string hash unordered-map unordered-multimap
person izaak_pyzaak    schedule 22.07.2016    source источник
comment
Пожалуйста, убедитесь, что код компилируется, если вы попросите нас запустить его.   -  person Jakube    schedule 23.07.2016
comment
Я не делаю нет? Где ошибка?   -  person izaak_pyzaak    schedule 23.07.2016
comment
Во втором цикле for указано read.size(), но переменной read нет (вы имели в виду reads?). Вы также дважды используете .orientation в коде, который нигде не определен. И с этими двумя исправлениями программа все равно вылетает, из-за строки read.substr(i, 30).   -  person Jakube    schedule 23.07.2016
comment
Упс, ваше право. Рад за улов. Редактирование нового   -  person izaak_pyzaak    schedule 23.07.2016
comment
Бегает сейчас. Вам может понадобиться вкл. -стандарт=С++11   -  person izaak_pyzaak    schedule 23.07.2016

Ответы (2)


arrow_upward
2
arrow_downward

Да, вы правы. Не гарантируется, что два разных предмета окажутся в двух разных корзинах. Вы знаете только, что два одинаковых предмета попадают в одно и то же ведро.

Решение вашей проблемы — просто избегать ведер. Класс unordered_multimap (как и multimap) имеет метод equal_range, который дает вам диапазон элементов с определенным ключом. Таким образом, вам нужно только перебрать все ключи и использовать equal_range для перебора всех значений. К сожалению, нет метода, позволяющего вам перебирать ключи, поэтому вам нужно быть немного хитрым. Следующий код должен дать вам желаемый результат:

// 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;
}
person Jakube    schedule 23.07.2016

arrow_upward
0
arrow_downward

Итак, для всех, кому было интересно. Я нашел это в стандарте

[C++11: 23.2.5/5]: два значения k1 и k2 типа Key считаются эквивалентными, если объект функции key_equal контейнера возвращает true при передаче этих значений. Если k1 и k2 эквивалентны, хэш-функция должна возвращать одно и то же значение для обоих. [..]

[C++11: 23.2.5/8]: элементы неупорядоченного ассоциативного контейнера организованы в сегменты. Ключи с одинаковым хеш-кодом появляются в одном сегменте. [..]

Таким образом, два значения с одним и тем же ключом всегда окажутся в одной корзине, но ключи с разными значениями также могут оказаться в этих корзинах. Итак, я полагаю, что реализация может быть более разумной и фактически способствовать этим ситуациям; одна из причин, по которой я мог бы подумать об этом, чтобы уменьшить количество ведер. Вы можете видеть из вывода, что заполненные ведра разрежены; и чем ближе мы подходим к таблицам прямых адресов (массив векторов, проиндексированных хэшем), тем больше мы получаем гигантскую вселенную потенциальных ключей с огромным количеством пустых слотов, от которых защищают хеш-таблицы. Таким образом, это кажется разумной оптимизацией пространства.

Из-за этого я решил использовать multimap вместо этого. Причина в том, что значения в multimap упорядочены на основе ключа, поэтому я могу сделать один проход через группировку значений на основе ключей. В unordered_multimap, когда я достигаю ведра (в O (1), потому что это хеш-таблица), нет упорядочения на основе ключей, поэтому я не могу выполнить линейный проход через ведро для группировки последовательностей.

person izaak_pyzaak    schedule 23.07.2016