Javenue logo

Javenue

Программирование на Java

Информационные технологии

Генератор случайных чисел - java.util.Random

Как говорится: случайность - частный случай закономерности. Поэтому наверняка вы используете случайные числа в некоторых своих разработках.

В Java есть класс для работы со случайными (точнее псевдослучайными) числами - java.util.Random. Тем не менее, некоторые люди пользуются им не совсем так, как надо.

Пример:

public class TestRandom {
    private static Random random = new Random();

    static int generateRandom(int n) {
        return Math.abs(random.nextInt()) % n;
    }
}

Казалось бы, что тут такого плохого?

Давайте рассмотрим следующий метод (можете поместить его в класс TestRandom):

static void test1() {
    int n = (Integer.MAX_VALUE / 3) * 2;
    int bottom = 0;
    for (int i=0; i<1000000; i++) {
        if (generateRandom(n) < n/2)
            bottom++;
    }
    System.out.println(“bottom=” + bottom);
}

По идее, в нижнюю половину диапазона должно попасть около 500000 чисел. Но мы видим, что туда попадает около 666666. Это число приближается к 500000 по мере увеличения делителя в первой строке метода. Но все равно, непорядок.

Есть еще одна проблема. Метод Math.abs(k) возвращает Integer.MIN_VALUE, если k = Integer.MIN_VALUE, так как не может взять модуль этого числа. То есть в случае, когда nextInt() вернет Integer.MIN_VALUE, не исключено, что generateRandom() вернет отрицательное число. Это не получится только в том случае, когда n - степень числа 2.

Следующий метод демонстрирует нам потенциальный крах программы:

static void test2() {
    int n = Math.abs(Integer.MIN_VALUE) % 4;
    System.out.println(n);
    n = Math.abs(Integer.MIN_VALUE) % 14;
    System.out.println(n);
}

А выход есть - используйте Random.nextInt(int), не зря же его дядьки умные придумали.

Updated (28.01.2008): В литературе мне встречалась информация, что если n - степень двойки, то последовательность псевдослучайных чисел будет повторятся через довольно короткий период. Как я и обещал ранее, привожу небольшой тест, который подтверждет это утверждение:

public class Randomizer {
    public static final int INITIAL_LENGTH = 1000000;
    public static final int POWER_OF_TWO = 2;

    private static class Sequence {
        private int index = 0, count = 0;

        public Sequence(int index) {
            this.index = index;
        }

        public int getIndex() { return index; }

        public void increase() { count++; }

        public int getCount() { return count; }

        void reset() { count = 0; }

        void setIndex(int index) { this.index = index; }
    }

    private static class SequencesPool {
        private List sequences = new ArrayList();

        public Sequence getSequence(int index) {
            if (sequences.size() == 0) {
                return new Sequence(index);
            }
            Sequence sequence = sequences.remove(0);
            sequence.setIndex(index);
            return sequence;
        }

        public void returnToPool(Sequence sequence) {
            sequence.reset();
            sequences.add(sequence);
        }
    }

    private static Random random = new Random();

    static int generateRandom(int n) {
        return Math.abs(random.nextInt()) % n;
    }

    public static void main(String[] args) {
        SequencesPool pool = new SequencesPool();
        List list = 
            new ArrayList(INITIAL_LENGTH + 1);
        List sequences = new ArrayList();

        int newRnd = generateRandom(POWER_OF_TWO);
        list.add(newRnd);

        for (int i = 0; i < INITIAL_LENGTH; i++) {
            newRnd = generateRandom(POWER_OF_TWO);
            list.add(newRnd);
            if (newRnd == list.get(0)) {
                Sequence sequence = pool.getSequence(i);
                sequences.add(sequence);
            }

            Iterator iterator = sequences.iterator();
            while (iterator.hasNext()) {
                Sequence sequence = iterator.next();
                if (newRnd == list.get(sequence.getCount())) {
                    sequence.increase();
                } else {
                    iterator.remove();
                    pool.returnToPool(sequence);
                }
            }
        }

        for (Sequence sequence : sequences) {
            System.out.print(sequence.getIndex() + "; ");
        }
    }
}

Программа для POWER_OF_TWO = 2 дает следующий результат:

131071; 262143; 393215; 524287; 655359; 786431; 917503; 999999;

То есть с периодом 131072 последовательность чисел повторяется. Для POWER_OF_TWO = 4 мощности моего компьютера не хватает. Попробую как-нибудь на машине посерьезнее...

Надеюсь, статья была вам интересна. До скорой встречи.


Комментариев: 0

  Выйти

  * для публикации комментариев нужно