Немного о генераторе случайных чисел

Все кто программирует на java должен был слыхать хотя бы раз о Random. В javadoc о нем пишут следующее:

Класс служит для генерации потока псевдослучайных чисел, использует 48-битный seed, который изменяется по средством литейной конгруэнтной формулы. И ссылка к Дональду Кнуту на The Art of Computer Programming, Volume 2, Section 3.2.1.

В общем, цель данного поста проверить на сколько приемлемый результат обеспечивает стандартный генератор. Плюс на просторах я нашел улучшенную версию, заодно проверю и его.

Тест выглядит следующим образом. Создадим массив из ста элементов. По индексу храним счетчик значений. Запускать будем в однотонном режиме, дабы как говорит документация у нас не просела производительность. Пару слов о том, что я ожидаю получить в качестве результата. В идеальном случае значения счетчиков в массиве по окончанию работы должны стремиться к некой величине, а именно N/100, где N - это общее количество сгенерированных значений. Понятно, что на практике у нас будут отклонения, а вот какого порядка - это собственно и хочется узнать.

Тестировать будем сразу три ГСЧ:

• Стандартный Random
• Улучшенный Random
• ThreadLocalRandom

Поначалу хотел, чтоб каждый ГСЧ отработа Long.MAX_VALUE циклов, это бы обеспечило более достоверные результаты, но по времени это получалось уже как-то затратно.

public class Main {
    static final Random STANDARD_RANDOM = new Random();
    static final Random IMPROVED_RANDOM = new HighQualityRandom();

    static final int[] STANDARD_RANDOM_RESULT = new int[100];
    static final int[] IMPROVED_RANDOM_RESULT = new int[100];
    static final int[] THREAD_LOCAL_RANDOM_RESULT = new int[100];

    public static void main(String[] args) {
        for (long i = 0; i < 1000000000l; i++) {
            STANDARD_RANDOM_RESULT[STANDARD_RANDOM.nextInt(100)]++;
            IMPROVED_RANDOM_RESULT[IMPROVED_RANDOM.nextInt(100)]++;
            THREAD_LOCAL_RANDOM_RESULT[ThreadLocalRandom.current().nextInt(100)]++;
        }

        for (int i = 0; i < STANDARD_RANDOM_RESULT.length; i++) {
            System.out.println(i
                            + " " + STANDARD_RANDOM_RESULT[i]
                            + " " + IMPROVED_RANDOM_RESULT[i]
                            + " " + THREAD_LOCAL_RANDOM_RESULT[i]
            );
        }
    }
}

Скажу сразу, я ожидал худшего. Поясню, что значит худшее в данном контексте. Если провести регрессию, например линейную, то плохим результатом можно было бы считать, когда прямая идет под каким либо углом по отношению к оси X. Это значит, что ГСЧ имеет склонность выдвать значения неравномерно. В нашем же случае, выглядит так, что подобных завалов нет и при бОльшем количестве сгенерируемых чисел, кривая бы походила на прямую которая параллельна оси Х.

Пару слов о ThreadLocalRandom/ Добавлять его смысла особого не было. Исходники я не смотрел, но подозреваю, что целиком и полность это тот жесамый Random, только обернутый в ThreadLocal класс. Если ГСЧ используется в многопоточной среде, то рекомендуется испльзовать именно его в противовес обычному Random-у. Даже не смотря на то, что второй объявлен как thread safe.

Выводы

По наивности своей думал, что псевдослучайный означает непригодный для практического применения. Что в корне неверно. В интернетах пишут же, что для подобных типов генераторов можно найти закономерности(алгоритм гарантирующий угадывание следующего числа). Есть сомнения на этот счет. Для некоторых типов приложений(напрмер игры) стандартный ГСЧ может быть вполне приемлемым.

Ресурсы

• Стандартный генератор Random
• Улучшенная версия генератора
• Про линейный конгруэнтный метод
• Класс о существовании которого я не знал к своему стыду ThreadLocalRandom
• Gnuplot вэб версия