Случайные числа и поток локального хранилища - PullRequest
Новая
       9

Случайные числа и поток локального хранилища

0 голосов
/ 21 сентября 2010

Принятый ответ на этот вопрос , и подобное обсуждение сегодня на работе заставило меня задуматься о чем-то.

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

Допустим, у нас одновременно запущены два потока (вполне возможно в многоядерной системе), и оба вызывают конструктор Random по умолчанию для создания иинициализировать генератор случайных чисел в локальном хранилище потока.Поскольку они не передали параметр seed, Random использует системное время в качестве seed.Таким образом, оба генератора случайных чисел были инициализированы с одним и тем же начальным числом.Оба они будут генерировать одну и ту же последовательность случайных чисел.

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

At startup, two requests come in simultaneously.
Two threads are created, each initializing a random number generator with the same seed.

Each thread generates three random numbers.  They will be identical in both threads.

Next request comes in.  It's assigned to thread #1.
It generates a random number and exits.

Some period of time elapses.

Next request comes in.  It's assigned to thread #2.
It generates the same random number that thread #1 did just a while ago.

Это может продолжаться бесконечно, хотя я сомневаюсь, что это будет пинг-понг довольно сильно.Дело в том, что оба потока имеют одинаковый PRNG и вероятность повторения последовательности очень высока.Я понимаю, что P в PRNG означает «псевдо», но это немного много.

Я думаю, что несколько потоков могут инициализировать экземпляр Random с тем же начальным значением.Если это произойдет, то "случайность" по крайней мере некоторых вещей в приложении пострадает.Последствия этого, конечно, зависят от приложения.

Что я не знаю, так это то, что если PRNG инициализируются с разными начальными значениями, делает ли последовательность, видимая клиентом, более случайной, менее случайной,или примерно так же?То есть, если бы я написал: 

var rnd1 = new Random(123);
var rnd2 = new Random(654);
for (int i = 0; i < OneMillion; ++i)
{
    numbers.Add(rnd1.Next());
 numbers.Add(rnd2.Next());
}

Была бы последовательность чисел, которую я сгенерировал, более или менее случайной, чем если бы я просто генерировал два миллиона из любого из PRNG?

Ответы [ 2 ]

1 голос
/ 21 сентября 2010

Уровень случайности должен быть примерно одинаковым, поскольку оба ряда генерируются с помощью одного и того же алгоритма .

Как вы определяете случайность?Будет ли одна серия казаться более случайной или нет, вполне может зависеть от пользователя и от того, что приложение делает с серией чисел.

Если вы беспокоитесь о том, что то же семя используется длянесколько генераторов случайных чисел, вы всегда можете отсеять все ваши генераторы случайных чисел из последовательности, сгенерированной другим единственным генератором.Таким образом, по крайней мере, ваша начальная точка отсчета будет несколько произвольной.

1 голос
/ 21 сентября 2010

Сгенерированные числа являются такими же случайными, как и заданное вами начальное число. Если два потока заканчиваются одним и тем же начальным числом, они будут иметь одинаковую последовательность «случайных» чисел.

Чтобы предотвратить это, используйте синхронизацию, чтобы убедиться, что каждому сохраненному в TLS генератору случайных чисел присвоен уникальный начальный номер. 

private static object _sync = new object();
[ThreadStatic]
private static Random _rand;

...

if (_rand == null) {
    lock(_sync) {
        _rand = new Random(DateTime.Now.Ticks);
        Thread.Sleep(_rand.Next(0,3));
    }
}

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

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

...