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