Динамическая функция equ_to unordered_map boost
У меня есть неупорядоченная строка карты для int, которая использует пользовательскую функцию equal_to, определенную как:
bool hashEqual::operator ()(const string &a, const string &b) const
{
if (a.size() != b.size())
return false;
return std::inner_product(
a.begin(), a.end(), b.begin(),
0, std::plus<unsigned int>(),
std::not2(std::equal_to<std::string::value_type>())
) <= 8;
}
По сути, если два ключа имеют расстояние Хэмминга, равное или меньшее 8, то это один и тот же ключ.
Дело в том, что я хочу, чтобы порог расстояния был динамическим, чтобы пользователь мог установить его через командную строку. Вместо 8 переменная порог или что-то вроде этого.
Я ищу не хак, как глобальную переменную (если это не единственный способ добиться этого), а «хороший способ».
Решение
Почему `unordered_map` не работает надежно
Хорошая универсальная хеш-функция отображает ключи в сегменты повторяемым, но, казалось бы, случайным образом, под которым я подразумеваю, что если ключ изменяется хотя бы на один бит, то блок должен быть статистически не связан — как если бы вы выбрали другой в случайным образом. Итак, скажем, у вас есть хеш-таблица с некоторыми существующими элементами:
[ bucket 0 - "abcde fghij" ]
[ bucket 1 - <empty> ]
[ bucket 2 - <empty> ]
[ bucket 3 - "01234 56789", "77777 QQQQQ" ] (2 colliding values for this bucket)
[ bucket 4 - "XXXXX YYYYY" ]
[ bucket 5 - <empty> ]
Если вы пришли, чтобы вставить, скажем, "Abcde fghij" тогда вы могли бы хэшировать любое из этих сегментов — у вас не должно быть больше шансов, что этот сегмент равен 0, чем любой другой, но если этот сегмент не ведро 0, тогда вы даже не пытайтесь сравнение равенства Хэмминга на расстоянии с «abcde fghij».
Почему `multimap` не работает надежно
Представь, что мы multimap с некоторыми существующими строками (от S1 до S6 в возрастающем лексикографическом порядке сортировки — каждая с расстоянием Хэмминга более 8 от других элементов) в нем, фактическое сбалансированное двоичное дерево может выглядеть примерно так:
S4
/ \
S2 S6
/ \ / \
S1 S3 S5
Теперь предположим, что S1 "Abcde fghij"S4 это "ZZZZZ ZZZZZ" и мы идем, чтобы вставить "abcde fghij":
-
даже при сравнении расстояний Хэмминга,
"ZZZZZ ZZZZZ" < "abcde fghij"(помните, что'Z' < 'a'в порядке ASCII), поэтомуmultimapнадеется"abcde fghij"храниться в правой части дерева … -
"abcde fghij"затем сравнивается с S6, и если меньше S5, и будет вставлен соответствующим образом, но принципиально есть никогда не сравнить с S1
Что возвращает меня к моему предыдущему комментарию:
Я не думаю, что есть какой-то простой и правильный способ сравнения, кроме грубой силы (попробуйте каждую комбинацию). И результаты варьируются для тех же данных в другом порядке.
Другие решения
Я понял.
Все сделано в классе hashEqual. Я изменил определение следующим образом:
class hashEqual {
private:
int th;
public:
hashEqual();
hashEqual(int th) { this->th = th; }; // This implemetation on the .cpp
bool operator ()(const string &a, const string &b) const;
};
реализация оператора ():
bool hashEqual::operator ()(const string &a, const string &b) const
{
if (a.size() != b.size())
return false;
return std::inner_product(
a.begin(), a.end(), b.begin(),
0, std::plus<unsigned int>(),
std::not2(std::equal_to<std::string::value_type>())
) <= this->th;
}
И в конструкторе unordered_map:
boost::unordered_map<string, unsigned int, boost::hash<string>, hashEqual> myMap(size, boost::hash<string>(), hashEqual(threshold));