Подтвердить что ты не робот

RNGCryptoServiceProvider - быстрее генерировать число в диапазоне и сохранять распределение?

Сначала я нахожусь на телефоне, поэтому, пожалуйста, простите плохое форматирование!

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

Я использую поставщика криптоваторов RNG для генерации чисел в диапазоне поистине наивным способом:

byte[] bytes = new byte[4];
int result = 0;
while(result < min || result > max)
{
   RNG.GetBytes(bytes);
   result = BitConverter.ToInt32(bytes);
}

Это здорово, когда диапазон достаточно широк, так что есть достойный шанс получить результат, но ранее сегодня я попал в сценарий, где диапазон достаточно мал (в пределах 10 000 номеров), что может занять возраст.

Итак, я пытаюсь думать о лучшем способе, который обеспечит достойное распространение, но будет быстрее. Но теперь я углубляюсь в математику и статистику, которые я просто не делал в школе, или, по крайней мере, если бы я это сделал, я забыл все это!

Моя идея:

  • получить наивысшие заданные битовые позиции min и max, например. для 4 это было бы 3, а для 17 было бы 5
  • выберите количество байтов из prng, которые могут содержать по крайней мере высокие биты, например, в этом случае для 8 бит
  • проверьте, установлены ли какие-либо из верхних бит в допустимом диапазоне (3-5)
  • если да, включите это число до и включите высокий бит
  • если это число находится между min и max, return.
  • Если какой-либо из предыдущих тестов завершился с ошибкой, начните снова.

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

Но, конечно, скорость не является моей единственной заботой, иначе я бы просто использовал Random (вам нужно несколько галочек, чтобы правильно отформатировать, если кто-то будет достаточно любезен - они не на клавиатуре Android!).

Самая большая проблема, с которой я сталкиваюсь с вышеприведенным подходом, заключается в том, что я всегда отбрасываю до 7 бит, которые были сгенерированы prng, что кажется плохим. Я думал о способах их включения (например, простое добавление), но они кажутся ужасно ненаучными хаками!

Я знаю о трюке мод, где вам нужно только создать одну последовательность, но я также знаю о ее слабостях.

Это тупик? В конечном счете, если лучшее решение будет состоять в том, чтобы придерживаться текущей реализации, я просто чувствую, что должен быть лучший способ!

4b9b3361

ОТВЕТЫ

Ответ 1

Стивен Туб и Шон Фаркас совместно написал прекрасную статью о MSDN под названием Tales From The CryptoRandom, которую вы обязательно должны прочитать, re экспериментируя с RNGCryptoServiceProviders

В нем они предоставляют реализацию, которая наследуется от System.Random(которая содержит хороший диапазон-случайный метод, который вы ищете), но вместо использования псевдослучайных чисел их реализация использует RNGCryptoServiceProvider.

Способ, которым он реализовал метод Next (min, max), выглядит следующим образом:

public override Int32 Next(Int32 minValue, Int32 maxValue)
{
    if (minValue > maxValue) 
        throw new ArgumentOutOfRangeException("minValue");
    if (minValue == maxValue) return minValue;
    Int64 diff = maxValue - minValue;
    while (true)
    {
        _rng.GetBytes(_uint32Buffer);
        UInt32 rand = BitConverter.ToUInt32(_uint32Buffer, 0);

        Int64 max = (1 + (Int64)UInt32.MaxValue);
        Int64 remainder = max % diff;
        if (rand < max - remainder)
        {
            return (Int32)(minValue + (rand % diff));
        }
    }
}

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

Thread safe bufferred CryptoRandom

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

Я написал это для очень специфического сценария, поэтому вы должны, конечно, профиль, имеет ли значение для вас конкретный аргумент и concurrency атрибуты вашего приложения. Я бросил код на github, если вы не хотите его проверить.

Threadsafe буферизованный CryptoRandom на основе реализации Stephen Toub и Shawn Farkas

Когда я это написал (пару лет назад), я, похоже, тоже сделал профилирование

Results produced by calling Next() 1 000 000 times on my machine (dual core 3Ghz)

System.Random completed in 20.4993 ms (avg 0 ms) (first: 0.3454 ms)
CryptoRandom with pool completed in 132.2408 ms (avg 0.0001 ms) (first: 0.025 ms)
CryptoRandom without pool completed in 2 sec 587.708 ms (avg 0.0025 ms) (first: 1.4142 ms)

|---------------------|------------------------------------|
| Implementation      | Slowdown compared to System.Random |
|---------------------|------------------------------------|
| System.Random       | 0                                  |
| CryptoRand w pool   | 6,6x                               |
| CryptoRand w/o pool | 19,5x                              |
|---------------------|------------------------------------|

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

Ответ 2

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

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

int vSize = 20*4;
byte[] vBytes = new byte[vSize];
RNG.GetBytes(vBytes);
int vResult = 0;
int vLocation = 0;
while(vResult < min || vResult > max)
{
    vLocation += 4;
    vLocation = vLocation % vSize;
    if(vLocation == 0)
        RNG.GetBytes(vBytes);
    vResult = BitConverter.ToInt32(vBytes, vLocation);
}

Еще одна вещь, которую вы можете сделать, - это сравнение, в котором вы думаете о поразрядном. Тем не менее, я бы сосредоточился на том, соответствует ли диапазон байту, короткому, int или длинному. Затем вы можете по модулю результата int получить максимум этого типа (предоставляя бит младшего порядка).

//We want a short, so we change the location increment and we modulo the result.
int vSize = 20*4;
byte[] vBytes = new byte[vSize];
RNG.GetBytes(vBytes);
int vResult = 0;
int vLocation = 0;
while(vResult < min || vResult > max)
{
    vLocation += 2;
    vLocation = vLocation % vSize;
    if(vLocation == 0)
        RNG.GetBytes(vBytes);
    vResult = BitConverter.ToInt32(vBytes, vLocation) % 32768;
}

Ответ 3

Вам не нужно возиться с while. Этот подход будет медленным и основан на неизвестном числе итераций.

Вы можете вычислить его с первой попытки, используя modulo operator (%).

Но, если мы сжимаем результаты по модулю, мы сразу создаем дисбаланс в распределениях вероятностей.

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

Вот утилита RNG, которая может удовлетворить ваши потребности:

using System;
using System.Security.Cryptography;

static class RNGUtil
{
    /// <exception cref="ArgumentOutOfRangeException"><paramref name="min" /> is greater than <paramref name="max" />.</exception>
    public static int Next(int min, int max)
    {
        if (min > max) throw new ArgumentOutOfRangeException(nameof(min));
        if (min == max) return min;

        using (var rng = new RNGCryptoServiceProvider())
        {
            byte[] data = new byte[4];
            rng.GetBytes(data);

            int generatedValue = Math.Abs(BitConverter.ToInt32(data, startIndex: 0));

            int diff = max - min;
            int mod = generatedValue % diff;
            int normalizedNumber = min + mod;

            return normalizedNumber;
        }
    }
}

В этом случае RNGUtil.Next(-5, 20) будет отображать произвольное число в пределах диапазона -5..19

Небольшой тест:

LinkedList<int> list = new LinkedList<int>();

for (int i = 0; i < 10000; i++)
{
    int next = RNGUtil.Next(-5, 20);
    list.AddLast(next);
}

bool firstNumber = true;
foreach (int x in list.Distinct().OrderBy(x => x))
{
    if (!firstNumber) Console.Out.Write(", ");
    Console.Out.Write(x);
    firstNumber = false;
}

Выход: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

Ответ 4

Ниже приведена адаптация @ответа Andrey-WD выше, но с той разницей, что вы просто отправляете произвольное число, которое вы уже создали (a ulong в этом случае можно изменить на uint). Там, где это очень эффективно, когда вам нужно несколько случайных чисел в диапазоне, вы можете просто сгенерировать массив таких чисел через RNGCryptoServiceProvider (или что угодно, даже с Random, если это соответствует вашим потребностям). Это, я уверен, будет гораздо более результативным, когда вам нужно создать несколько случайных чисел в пределах диапазона. Все, что вам нужно, это приступы случайных онемений для подачи функции. См. Мою заметку выше на @Andrey-WD ответ, мне любопытно, почему другие не делают этот упрощенный маршрут модуля, который не требует нескольких итераций. Если действительно существует причина для множественного маршрута итераций, я был бы рад услышать это.

    public static int GetRandomNumber(int min, int max, ulong randomNum)
    {
        if (min > max) throw new ArgumentOutOfRangeException(nameof(min));
        if (min == max) return min;

        //var rng = new RNGCryptoServiceProvider();
        //byte[] data = new byte[4];
        //rng.GetBytes(data);
        //int generatedValue = Math.Abs(BitConverter.ToInt32(data, startIndex: 0));

        int diff = max - min;
        int mod = (int)(randomNum % (ulong)diff); // generatedValue % diff;
        int normalizedNumber = min + mod;

        return normalizedNumber;
    }

Здесь вы можете эффективно получить чистый массив случайных чисел. Мне нравится, как это чисто инкапсулирует получение случайных чисел, код, который использует это, тогда не должен быть загроможден преобразованием байта на каждой итерации, чтобы получить int или long с BitConverter. Я также предполагаю, что это выигрыш достигается за счет сингулярного преобразования байтов в тип массива.

    public static ulong[] GetRandomLongArray(int length)
    {
        if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
        ulong[] arr = new ulong[length];
        if (length > 0) { // if they want 0, why 'throw' a fit, just give it to them ;)
            byte[] rndByteArr = new byte[length * sizeof(ulong)];
            var rnd = new RNGCryptoServiceProvider();
            rnd.GetBytes(rndByteArr);
            Buffer.BlockCopy(rndByteArr, 0, arr, 0, rndByteArr.Length);
        }
        return arr;
    }

Использование:

        ulong[] randomNums = GetRandomLongArray(100);
        for (int i = 0; i < 20; i++) {
            ulong randNum = randomNums[i];
            int val = GetRandomNumber(10, 30, randNum); // get a rand num between 10 - 30
            WriteLine(val);
        }