LINUX.ORG.RU

Какие быстрые непериодические хеш-функции вы знаете?

 


2

2

Для генерации карты алгоритмом «diamond-square» (кстати, устоявшееся русское название есть?) требуется простая быстрая функция, которая преобразовывала бы координаты в случайное число от 0 до 3. Если взять линейный конгруэнтный генератор ( seed = seed * 1664525 + 1013904223; random = seed & 3 ), на первом шаге получается слишком периодично "... 1 2 3 0 1 2 3 ...". Хуже того, с большой вероятностью входные значения имеют период кратный 4. Если прогнать 6-10 его циклов — слишком долго, и период — бОльшая степень 2.

Есть ли что-либо столь же быстрое, но менее предсказуемое?

★★★★★

random = seed & 3

Известно что младшие и старшие его биты предсказуемы. Можешь брать откуда-нибудь ближе к середине, но лучше возьми нормальный ГПСЧ. Я тоже на это наступил - у меня в одной игрушке должны были лампочки на пульте хаотично мигать, как на ЭВМ в древних фильмах, и с ЛКГ прямо в глаза бросалось что они мигают совсем неслучайно и неравномерно. Я не заморачивался и взял mersenne twister из стандартной плюсовой библиотеки, помогло.

слишком долго

Я думаю ты лукавишь - не может быть такого чтобы генерация карты упиралась в производительность ГПСЧ.

И да, ГПСЧ и хэш функции это немного совсем разные вещи.

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

Известно что младшие и старшие его биты предсказуемы. Можешь брать откуда-нибудь ближе к середине,

Логично, спасибо. Для битов 23-27 и 30-31 последовательности выглядят вполне случайно. Но неравномерно. Позже проверю точно.

ГПСЧ и хэш функции это немного совсем разные вещи.

Сгодится любая функция, непредсказуемо связанная со стартовым значением. Криптографические хеши — первое, что пришло в голову. Но насколько они быстрые?

Я думаю ты лукавишь - не может быть такого чтобы генерация карты упиралась в производительность ГПСЧ.
лучше возьми нормальный ГПСЧ.

Карта генерируется следующим образом:
Берётся битмап со сторонами в несколько десятков пикселей.
Создаётся вдвое больший массив.
Точки битмапа копируются на чётно-чётные позиции в новом массиве.
Затем генерируются нечётно-нечётные точки (центры квадратов) — выбираются с вероятностью 1/4 из 4 чётно-чётных соседей.
Затем так же генерируются чётно-нечётные и нечётно-чётные точки (центры ромбов).
Процесс повторяется пока не получится нужный размер карты.
Разумеется, нет необходимости многократно удваивать всю карту. Можно работать с куском. Тем более, в окончательном варианте я планирую 20-27 удвоений.
К ГСЧ (или ещё какой функции) 3 требования. Она должна быть довольно быстрой, для заданных координат всегда выдавать одинаковый результат и создавать интересный пейзаж — то есть быть достаточно непредсказуемой, без заметной периодичности.

В качестве стартового числа для ГСЧ на ЛКГ я использую координаты на самой крупномасштабной карте: y * ширина + x. (То есть на начальных этапах все координаты кратны 2 в 20-й или больше.)

Про скорость. Идеальный результат — чтобы на 4К мониторе можно было показать карту в масштабе 1 пиксель — 1 тайл, вычисленную в интервале между кадров :) Это будет немного больше 8 847 360 вызовов функции, выбирающей из 4 тайлов, скажем, за 1/25 с. Собственно ЛКГ — это около десятка команд ассемблера, то есть времени должно хватить.

У каких других функций такие же свойства? Скорость, однозначная зависимость от входного числа, непредсказуемость.

question4 ★★★★★ ()

посмотри на pcg https://en.wikipedia.org/wiki/Permuted_congruential_generator у них на сайте код есть. на сегодня, насколько мне известно, это самый быстрый * самый качественный гпсч. ещё есть xorshift (128+...), тот ещё быстрее, но в младших разрядах сильно лажает, хотя в целом довольно неплох.

anonymous ()
Ответ на: комментарий от question4

Я тут в соседнем треде про хеши болтал Все извесные djb2 коллизии там есть функция обнаружения коллизий если ей переделать и сильно сильно упростить выкинув хлам ненужный то можно определять генерируется ли последовательность сильно периодичная, хотя наверное при генерации можно просто хранить последние скажем 12 значений и смотреть что бы там не было периодичностей сильных если они есть то смешивать, но как то предсказуемо, что бы можно было сделать функцию корректировки типа, которая будет смешивать переодичности но всегда предсказуемо, получишь всегда шум вместо периодичности вне зависимости от выхлопа хеша, хотяяя… на 8 847 360 вызовов будет жирно всё так вычислять. Но тебе в любом случае приёдтся делать какой то хак, обеспечить стабильную работу и при этом скорость. И да кратные двум координаты просто инкрементируй на 1 и всё, ты от них просто избавляешься, но так как ты это делаешь всегда то пофиг хеш будет всегда выхлопываться один

UDP: не инкрементить не выход я бред сморозил

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от question4

Если добъёшься хорошей скорости и при этом красивых карт от генерации поделишься особенностями генерации, ну так чисто на словах? Тожа чёт захотелось карты генерировать, идеально будет подходить потом для проверки коллизий с мешем. А то руками рисовать карты высот надоело. Хотя если там у тебя всё коммерческое то я губу закатаю обратно :D

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от question4

Но неравномерно.

Это свойство человека — ожидать равномерности от случайного процесса. Но случайные процессы случайны. Так что в последовательности из четырёх разных цифр пять одинаковых цифр подряд — не такая уж и редкость, как нам обычно представляется.

i-rinat ★★★★★ ()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от i-rinat

Это свойство человека — ожидать равномерности от случайного процесса. Но случайные процессы случайны. Так что в последовательности из четырёх разных цифр пять одинаковых цифр подряд — не такая уж и редкость, как нам обычно представляется.

Когда я говорю про видимые без подсчётов недостатки, я имею в виду более тяжёлые случаи. Например, число встречается пару раз на несколько сотен. Или когда повторяется 10-20 раз подряд.

question4 ★★★★★ ()
Ответ на: комментарий от question4

Или когда повторяется 10-20 раз подряд.

Такая равномерность может выскочить внезапно, вот я и говорю надо хак. То есть повтор скажем числа 3 раза допустим в вот 4 и более допустим уже нет, заводим массивчик с последовательностью которую допустимо если что вставить например 3132 где угодно, встретили 4 подряд идущих числа на выхлопе 2222 меняем на 3132 встретили 8 подряд 22222222 меняем на 31323132 и так далее а можно завести несколько таких массивчиков и переключатся между ними, но если их менять случайно, из одного и тогоже массива входных данных будет разный выхлоп, ну тогда может по кругу их гнать. Если такое допустимо то избавимся от любых повторений уж совсем явных которые визуально не должно быть видно, но с другой стороны если эти кусочки будут часто повторятся будет тоже не гуд это будет тупо видно как видно кучу одинаковых картинок на большой плоскости

Deleted ()

Факториал от миллиона в HEX с отрезанными нулями. 4 млн. знаков. Любая цифра встречается 273-274 тысячи раз. Любая пара — 16-17 тысяч раз.

question4 ★★★★★ ()