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

random = seed & 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цифры pi генерируй. Вроде доказали, что они по свойствам близки к случайным

Цифры pi генерируй.

Долго. Даже по формуле Беллара.

http://www.cse.yorku.ca/~oz/hash.html вместо строки два значения координат и сжать выхлоп до значений от 1 до 3 как нить

https://en.wikipedia.org/wiki/Permuted_congruential_generator

Спасибо, пробую.

http://www.cse.yorku.ca/~oz/hash.html

Да, подобную подборку и искал. Спасибо.

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

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

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

Пока показывать нечего. Но всё будет открытое. https://github.com/tkzv/awl/tree/master/experiments Ничего серьёзного, так, для развлечения.

давно не мерялись хэш-функциями, есть повод :)

Изменился ли файл (самый быстрый алгоритм хеширования)? (комментарий)

давно не мерялись хэш-функциями, есть повод :)

Сейчас ситуация немного изменилась: https://news.ycombinator.com/item?id=19357895

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

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

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

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

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

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

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