Реализовал оба варианта на С++, поэкспериментировал.
На мой взгляд, 80 прогонов у тебя избыточны, хватает 32 раз. Соответственно время генерации существенно уменьшается. (грубо говоря в 2 раза)
Также примечательное свойство данного генератора ландшафтов (в целом генератора) — отображаемая карта (512х512) просчитывается практически за константное время, вне зависимости от размеров «полной карты». *
При размерах от 512 и до 1.073.741.824 время генерации отстаётся неизменным в пределах погрешностей.
Имеется ввиду как раз первичный просчёт, когда в «кэше» нет ни одного элемента и необходимо считать все.
_____________ * Данное поведение проявилось в реализации на С++, с использованием stl::map, в качестве ключа взята структура {dword x; dword y;}, вместо предлагаемого в оригинале строкового ключа «x+'_'+y». Однако же в браузерном исполнении JS-варианта прослеживается заметное увеличение времени генерации при росте «размера карты».
В результате более охватывающего тестирования к сожалению было выявлено, что предложенный мной способ вычисления PRN(x1,...,xn) для существенно больших размеров карты ведёт себя неприемлимо — начинают проявляться артефакты: диагональная симметрия и периодичность «островков» карты.
Это происходит при ширине квадрата карты примерно от 128М и более (смотрел до 4Г, т.е. до карт шириной и высотой по 4*1024^3 клеток).
Между тем, deNull, твой метод выдаёт результат ничем не хуже, чем для карт малых размеров.
В результате приходится продолжить поиск более совершенного алгоритма, который с одной стороны работал бы быстро и выглядел красиво (что характерно для элегантных и эффективных решений), и с другой не давал бы никаких заметных артефактов вплоть до размеров используемой при вычислениях разрядности (в нашем случае 2^32).
Пока что экспериментирование с различными операциями и вариациями на тему дополнительных перемешиваний почти не принесло видимых результатов.
Что же касается предложенного выше алгоритма randFromPair — его вполне успешно можно использовать для не очень больших карт (до 100млн х 100млн), получая при этом заметный выигрыш производительности. Для экстремально больших карт же пока остаётся актуальным только метод автора статьи.
Поэкспериментировал, и предлагаю такой вариант функции:
function randFromPair(x, y) {
var s = seed * 1972854929;
s ^= (x * 2971902361) ^ (y * 3572953751);
s = 0x6C078965 * s;// & 0xFFFFFFFF;
/*
s ^= s >> 11;
s ^= (s << 7) & 0x9D2C5680;
s ^= (s << 15) & 0xEFC60000;
s ^= s >> 18;
*/
return (s & 0x7FFFFFFF) * 4.656612875245796924105750827168e-10; //(1./2147483647.);;
}
Скорость работы (в моём хроме) поднялась почти в два раза.
Каких-либо артефактов или закономерностей я не заметил, результат выглядит столь же неплохо.
К сожалению, метод такой же — простые числа 1972854929, 2971902361, 3572953751 взяты "с потолка", математическое доказательство или исследование «подходящести» данного способа генерации ПСЧ на основе зерна {x,y,seed} — также открытая задача.
Возможно другие простые числа могут вести себя лучше.
s = 0x6C078965 * s;// & 0xFFFFFFFF; и далее
— взято из всеми любимого Вихря Мерсенна.
Закомментированный блок битового перемешивания — отключен поскольку он не производил видимых улучшений результирующей картины. (так и незачем его считать, для наших целей)
Сама строка «s = 0x6C...» оставлена по той же причине — без неё не происходит минимально необходимого перемешивания данных исходной тройки {x,y,seed}
Попробовать сейчас твой фрактальный ландшафт с моим вариантом функции можно здесь.
Я тоже буду рад помощи в доведении данного вопроса {x1,x2,...,xn} => PRN до итогового результата.
Причём даже больший интерес представляет расширенная задача, где исходные данные x1,...,xn — вещественные числа, и накладывается требование непрерывности построенного по ним поля PRN.
Функция randFromPair(x, y) — очень заинтересовала.
Да, идёт генерация псевдослучайного числа на основе «состояния» {x,y}. Всё в лучших добрых традициях ГПСЧ — простые числа, остатки от деления и последующие математические операции.
Но позвольте спросить, — откуда взяты именно такие простые числа?
А именно, 7; 13; 1301081 для X, и 8461; 105467; 105943 для Y?
Чем обусловлен выбор именно этих чисел и именно по три штуки?
Вопрос про 80-1 проездов напильником по результату также остаётся открытым.
К сожалению, наш мир настолько безумен, что перспектива — ввиде фотоаппаратов со встроенной блокировкой фотографирования копирайтного контента с мониторов, книг и др.носителей, ровно как и уголовное преследование юзеров со старыми мыльницами и принтскринщиков — не кажется такой невозможной…
Кстати, кнопка PrintScreen на этих ваших Виндах тут же при нажатии посылает оповещение в органы. А вы не знали? Им просто лень вами заниматься! ))
PS: Ох как не хотел бы пророком оказаться насчёт перспектив…
На мой взгляд, 80 прогонов у тебя избыточны, хватает 32 раз. Соответственно время генерации существенно уменьшается. (грубо говоря в 2 раза)
Также примечательное свойство данного генератора ландшафтов (в целом генератора) — отображаемая карта (512х512) просчитывается практически за константное время, вне зависимости от размеров «полной карты». *
При размерах от 512 и до 1.073.741.824 время генерации отстаётся неизменным в пределах погрешностей.
Имеется ввиду как раз первичный просчёт, когда в «кэше» нет ни одного элемента и необходимо считать все.
_____________
* Данное поведение проявилось в реализации на С++, с использованием stl::map, в качестве ключа взята структура {dword x; dword y;}, вместо предлагаемого в оригинале строкового ключа «x+'_'+y». Однако же в браузерном исполнении JS-варианта прослеживается заметное увеличение времени генерации при росте «размера карты».
Это происходит при ширине квадрата карты примерно от 128М и более (смотрел до 4Г, т.е. до карт шириной и высотой по 4*1024^3 клеток).
Между тем, deNull, твой метод выдаёт результат ничем не хуже, чем для карт малых размеров.
В результате приходится продолжить поиск более совершенного алгоритма, который с одной стороны работал бы быстро и выглядел красиво (что характерно для элегантных и эффективных решений), и с другой не давал бы никаких заметных артефактов вплоть до размеров используемой при вычислениях разрядности (в нашем случае 2^32).
Пока что экспериментирование с различными операциями и вариациями на тему дополнительных перемешиваний почти не принесло видимых результатов.
Что же касается предложенного выше алгоритма randFromPair — его вполне успешно можно использовать для не очень больших карт (до 100млн х 100млн), получая при этом заметный выигрыш производительности. Для экстремально больших карт же пока остаётся актуальным только метод автора статьи.
/ Большой респект за хорошую статью! /
Продолжаю поиски грааля.
function randFromPair(x, y) {
var s = seed * 1972854929;
s ^= (x * 2971902361) ^ (y * 3572953751);
s = 0x6C078965 * s;// & 0xFFFFFFFF;
/*
s ^= s >> 11;
s ^= (s << 7) & 0x9D2C5680;
s ^= (s << 15) & 0xEFC60000;
s ^= s >> 18;
*/
return (s & 0x7FFFFFFF) * 4.656612875245796924105750827168e-10; //(1./2147483647.);;
}
Скорость работы (в моём хроме) поднялась почти в два раза.
Каких-либо артефактов или закономерностей я не заметил, результат выглядит столь же неплохо.
К сожалению, метод такой же — простые числа 1972854929, 2971902361, 3572953751 взяты "с потолка", математическое доказательство или исследование «подходящести» данного способа генерации ПСЧ на основе зерна {x,y,seed} — также открытая задача.
Возможно другие простые числа могут вести себя лучше.
s = 0x6C078965 * s;// & 0xFFFFFFFF; и далее
— взято из всеми любимого Вихря Мерсенна.
Закомментированный блок битового перемешивания — отключен поскольку он не производил видимых улучшений результирующей картины. (так и незачем его считать, для наших целей)
Сама строка «s = 0x6C...» оставлена по той же причине — без неё не происходит минимально необходимого перемешивания данных исходной тройки {x,y,seed}
Попробовать сейчас твой фрактальный ландшафт с моим вариантом функции можно здесь.
Я тоже буду рад помощи в доведении данного вопроса {x1,x2,...,xn} => PRN до итогового результата.
Причём даже больший интерес представляет расширенная задача, где исходные данные x1,...,xn — вещественные числа, и накладывается требование непрерывности построенного по ним поля PRN.
Да, идёт генерация псевдослучайного числа на основе «состояния» {x,y}. Всё в лучших добрых традициях ГПСЧ — простые числа, остатки от деления и последующие математические операции.
Но позвольте спросить, — откуда взяты именно такие простые числа?
А именно, 7; 13; 1301081 для X, и 8461; 105467; 105943 для Y?
Чем обусловлен выбор именно этих чисел и именно по три штуки?
Вопрос про 80-1 проездов напильником по результату также остаётся открытым.
К сожалению, наш мир настолько безумен, что перспектива — ввиде фотоаппаратов со встроенной блокировкой фотографирования копирайтного контента с мониторов, книг и др.носителей, ровно как и уголовное преследование юзеров со старыми мыльницами и принтскринщиков — не кажется такой невозможной…
Кстати, кнопка PrintScreen на этих ваших Виндах тут же при нажатии посылает оповещение в органы. А вы не знали? Им просто лень вами заниматься! ))
PS: Ох как не хотел бы пророком оказаться насчёт перспектив…
Ага, заинтриговал )
PS: Думаю, авторы полиморфных вирусов тоже могут что-то интересное в тему рассказать, относящееся к кодогенерации, только асма на асме (: