C # Генерация случайных int - тайна

Question

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

Мои потребности были просты: я генерировал случайныеинтегральные (Int32) идентификаторы и стремились минимизировать коллизии.Время генерации не было проблемой.

Я пробовал эти методы для генерации случайных целых чисел:

1.)

   return rnd.Next();

где rnd - поле класса типаПроизвольное с помощью Seed из метода # 3.

2.)

   return rnd.Next(Int32.MinValue, Int32.MaxValue);

, где rnd - снова поле класса типа Random с Seed из метода # 3.

3.)

   var buffer = new byte[sizeof(int)];
   using (var rng = new RNGCryptoServiceProvider())
   {
        rng.GetBytes(buffer);
   }            
   return BitConverter.ToInt32(buffer, 0);

Примечание: я также пытался сделать так, чтобы RNGCryptoServiceProvider в качестве поля класса инициализировался один раз при инициализации связывающего класса, чтобы упростить работу GC, но я взял то же самое время для генерации, так что я думал, что это будет "more random ".

4.)

   return new Random(Method3()).Next();

5.)

   return new Random(Method3()).Next(Int32.MinValue, Int32.MaxValue);

Я знаю, что создание нового Random (int seed) при каждом вызове - это времяпотребляет, но столкновений меньше, верно?

Ну, теперь загадочная часть.Я предполагал, что большинство коллизий будет иметь метод № 1 и № 2, где № 1 будет немного быстрее и более без столкновений, а наименьшее количество коллизий будет иметь метод № 4 и № 5, где № 4 будет немного быстрее и более без столкновений и метод №3 будет своего рода компромиссом.

Поэтому я сделал тест, чтобы доказать свои предположения.Я сгенерировал 10х (в среднем) один миллион случайных чисел, используя каждый упомянутый метод, и взял среднее число столкновений и среднее время, необходимое для генерации миллиона чисел.Результаты (ниже) немного удивляют меня.

Результаты: продолжительность - часы: минуты: секунды: миллисекунды

Method1: AvgCollisions: 235, AvgDuration: 00:00:00.3561967
Method2: AvgCollisions: 116, AvgDuration: 00:00:00.4042033
Method3: AvgCollisions: 115, AvgDuration: 00:00:04.6037259
Method4: AvgCollisions: 234, AvgDuration: 00:00:09.2195856
Method5: AvgCollisions: 233, AvgDuration: 00:00:09.1788223

Я несколько раз запускал тест, и это быловсегда примерно одно и то же.

Тебе тоже не странно?Времена совсем не удивительны, это то, что я предположил, но результаты для меня значат, что метод2 лучше всего генерирует случайные числа, так как он самый случайный, самый быстрый, и вы можете установить минимальное и максимальное генерируемое число,Не знаю, насколько Method2 более предсказуем по сравнению с Method3, так как я не знаю, как бы я его протестировал.

Может кто-нибудь объяснить мне, что я делаю неправильно или почему методы № 4 и № 5 не имеют наименьших коллизий, и почему процент коллизий всегда одинаков?Разве это не должно быть случайным?

РЕДАКТИРОВАТЬ: Вот Visual Studio 2010 Решение этого теста я сделал: http://bit.ly/nxLODw

Answer 1

Единственное странное поведение с методом 5.

В методах 1, 4 вы генерируете число в диапазоне от 0 до int.MaxValue.

В методах 2, 3 и 5 вы генерируете число в диапазоне от int.MinValue до int.MaxValue.

Так что для методов 2 и 3 у вас есть диапазон, который примерно вдвое больше, и они имеют примерно половину столкновений по сравнению с методами 1, 4. Это кажется мне вполне нормальным.

Так почему метод 5 производит столько же коллизий, сколько методов 1 и 4, даже если он генерирует числа в большем диапазоне? Что ж, получается, что конструктор System.Random принимает абсолютное значение начального числа. Другими словами, это уменьшает количество случайных последовательностей до половины того, что могло бы быть. Поэтому, даже если вы получаете числа из большего диапазона, вы генерируете их из меньшего числа различных последовательностей.

Answer 2

Пока вы там, вы можете изменить # 3 следующим образом:

        var buffer = new byte[sizeof(int)];

        using (var rng = new RNGCryptoServiceProvider())
        {
            rng.GetBytes(buffer);
        }

        return BitConverter.ToInt32(buffer, 0);

Это а) гарантирует, что ваш массив имеет размер типа int (а не магическое число 4) и b)IDisposable правильно утилизирует RNGCryptoServiceProvider.