Столкновения в 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;
}
}

1

Решение

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

Решение вашей проблемы — просто избегать ведер. Класс 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;
}
1

Другие решения

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

[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), потому что это хеш-таблица), порядок на основе ключей не будет, поэтому я не могу сделать линейный проход через сегмент для группировки последовательностей.

0

По вопросам рекламы [email protected]