Столкновения в 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. ключи в одном и том же ведре, но в противоречие ключи хешируются на разные значения. Есть ли способ избежать этого и дифференцировать значения на основе ключей в корзинах? Или мне нужно сделать это реализовать?
#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;
}
}
2 ответа
Да, вы правы. Не гарантируется, что два разных предмета попадут в два разных ведра. Вы знаете только, что два одинаковых предмета приземляются в одном ведре.
Решение вашей проблемы - просто избегать ведер. Класс 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;
}
Итак, для всех, кому было интересно. Я нашел это в стандарте
[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), потому что это хеш-таблица), порядок на основе ключей не будет, поэтому я не смогу выполнить линейный проход через сегмент для группировки последовательностей.