K
Система непересекающихся множеств?
Size: a a a
2021 June 27
MB
Запустить обход в глубину/ширину или систему непересекающихся множество на полученном графе
2021 June 28
K
в итоге сделал через хеш, не ожидал даже что так быстро будет работать. Правда ещё ресурс для полиморфного аллокатора написал, но в целом ощущения классные ))
2021 June 29
A
День добрый! А как можно шустро подсчитать контрольную сумму (хэш, например) для матрицы (n, m), где n, m ~ 1000 и все значения в матрице типа float? Нашёл такое - https://codeforces.com/blog/entry/13737?locale=ru, но не уверен, что не будет коллизий при моей размерности
p
Коллизии не зависят от размерности же
EZ
Кажется что флоаты хешировать смысла мало
A
Битовый размер хеша просто должен быть больше чем битовый размер адресуемых сущностей. Если матриц всего 10, то достаточно 4-х битов для хеша. И не важно, сколько внутри элементов - это повлияет лишь на скорость вычисления хеша.
D
Ну если юзать обычный полиномиальный хеш, то еще как зависят (при условии неизменности поля), т.к. степень многочлена растет, а вместе с ней и возможное число корней.
p
Вероятность совпадения двух объектов остаётся одинаковой
p
Я не понял, почему не так
D
Почему?
p
Ну вот есть k бит хеша. Тогда вероятность того, что хеш одного объекта совпадет с x - примерно 1/2^k. В этом факте нигде не используется размерность объекта
D
А как вы так лихо посчитали вероятность совпадения?
p
Поправьте меня, где я не прав. Всего возможных хешей - 2^к. Хеш равновероятный. Значит, вероятность - 1/2^к.
D
Полиномиальный хеш, например, не равновероятный
p
Тут ничего не могу сказать, но по моему опыту везде, где полиномиальной хеш используется на практике, предполагается, что он почти равновероятен.
A
Это для идеального хеша, а таких не бывает. Но к этой вероятности стремится реальная вероятность.
D
Извините, а с чего вы это взяли? Если у вашего полинома растет степень, то растет и возможное кол-во корней и, соответственно, вероятность получить 0, подставив в него случайную точку поля.
A
Возьмите самый неидеальный хеш y(x) = 0. И посчитайте вероятность для двух элементов, а потом для 100, например.
A
У идеального хеша должно быть равномерное распределение. У неидеального будут резкие пики и ямы. Если использовать такой хеш, например в качестве генератора шума для изображения - на изображении будет красивая картинка, а не шум. Причем средняя яркость будет плавать в зависимости от хеша. Можно даже получать красивые узоры, темные или светлые.