Если нельзя, но очень хочется, то нужно обязательно и ничего в мире не стоит того, чтобы делать из этого проблему!


Интересна Java? Кликай по ссылке и изучай!
Если тебе полезно что-то из того, чем я делюсь в своем блоге - можешь поделиться своими деньгами со мной.
с пожеланием
столько времени читатели провели на блоге - 
сейчас онлайн - 

понедельник, 20 октября 2014 г.

Быстрая реализация Random - алгоритм XORShift

Как-то Серега писал о нерендомности рендомайзеров (импульс пришел отсюда). Для меня это не критично как бы, я просто хотел найти красивый большой png c белым шумом, но у гугла были только небольшие разрешения и то сжатые jpeg. Так что я стал мучить java.util.Random который оказался не таким уж и производительным. Попытки создать свой собственный ни к чему рендомному не привели, хотя было нарисовано много красивых картинок. Но я нашел что искал.

XORShift (любителям математики - goto сюда) до ужаса простой и гениальный алгоритм генерации рендомных чисел. Вот он (взято тут)

public class XORShiftRandom {
    private long last;

    public XORShiftRandom() {
        this(System.currentTimeMillis());
    }

    public XORShiftRandom(long seed) {
        this.last = seed;
    }

    public int nextInt(int max) {
        last ^= (last << 21);
        last ^= (last >>> 35);
        last ^= (last << 4);
        int out = (int) last % max;     
        return (out < 0) ? -out : out;
    }
}

Кстати на моей поделке он оказался быстрее java.util.Random в 10 раз.

А вот white noise полученный с помощью этого алгоритма черно-белый (19200х10240, 1920х1024) и цветной (19200х10240, 1920х1024). Осторожно большие размеры! Они не ужимаются ничем :) Так же, чтобы не слишком обижать java.util.Random выложу и его работы: черно-белый (19200х10240, 1920х1024) и цветной (19200х10240, 1920х1024).



Может как-то пригодится.

А чтобы проверить рендомность алгоритма я сделал следующее. Нагенерил из одного ряда png'шек шириной от 1 до 800 пикселей и высотой 600. А потом во вьюере быстренько просматривал один за другим в поисках харктерного муара. XORShift в некоторых местах все же едва "замуарил", а java.unit.Random показал немного более худший результат - в процессе изменения ширины картинки было видно движение больших массивов пикселей.

А еще я вот записал вот это видео :) Для ценителей... 600Mb за 1,5 минуты :)



2 комментария:

  1. Шум — это когда ты не чувствуешь мелодии, потому что она такая сложная, что не может уместиться в твоей голове. Может быть, чтобы услышать эту музыку, нужно быть размером со Вселенную. Просто представь, что тебе показали три числа, допустим 73, 144 и 59. И тебе никак не дано узнать — это три совсем случайных числа или крошечный кусок какой-то математической функции. Или список цен на комплект дизайнерской одежды: ботинки, штаны, куртка. И в итоге выясняется, тебе просто показали твое собственное давление и пульс. И значит, эти числа вовсе не случайные, а зависят от возраста, погоды, от количества приседаний в фитнесс-клубе или от курса твоих акций, который ты узнал секунду назад. Понимаешь? Мы слышим так мало нот, что просто не можем понять, из какой они симфонии. Но когда ты начинаешь работать с миллиардами, триллионами, квантиллионами случайных чисел, полученных от самых разных, вроде бы случайных шумов — ты начинаешь понимать, что где-то за кулисами есть Дирижер, или Композитор, или что-то типа того. Понимаешь? И это даже не про религию. Это — вообще. Просто выясняется, что у любых шумов все равно общие гармоники — что на Земле, что под землей, что в космосе. Ты думал, это был случайный порыв ветра и скрип дуба — а это вполне закономерное движение воздуха, которым дирижируют облака и приливы, а ими дирижируют вспышки на Солнце, а те подчиняются галактическим гравитационным ударам, и всё это — одна бесконечная, сложнейшая, но безумно гармоничная песня, которая звучит от Большого взрыва до наших дней...
    (c) Леонид Каганов "ПРОДАВЕЦ СЛУЧАЙНЫХ ЧИСЕЛ" http://lleo.me/arhive/2014/prodavec.htm

    ОтветитьУдалить