RNGCryptoServiceProvider-更快地生成范围内的数字并保留分发

本文关键字：数字 保留 范围内 RNGCryptoServiceProvider- | 更新日期: 2023-09-27 17:58:44

我使用RNG加密提供程序以真正天真的方式生成一个范围内的数字：

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

当范围足够宽，有很大的机会得到结果时，这是很好的，但今天早些时候，我遇到了一个场景，范围足够小（在10000个数字以内），可能需要一段时间。

所以我一直在想一种更好的方法，既能实现体面的分配，又能更快。但现在我正在深入学习我在学校根本没有做过的数学和统计学，或者至少如果我做了，我已经忘记了这一切！

我的想法是：

  • 获得最小值和最大值的最高设置位位置，例如，对于4，它将是3，对于17，它将为5
  • 从prng中选择一个字节数，该字节数至少可以包含高位，例如，在这种情况下，8位为1
  • 查看是否设置了允许范围（3-5）中的任何高位
  • 如果是，请将其转换为高达并包括高位的数字
  • 如果该数字介于最小值和最大值之间，则返回
  • 如果前面的任何测试失败，请重新开始

正如我所说，这可能非常天真，但我相信它会比当前的实现更快地在小范围内返回匹配。我现在不在电脑前，所以不能测试，我将在英国时间明天早上测试。

当然，速度并不是我唯一关心的问题，否则我只会使用Random（如果有人足够友善的话，需要几个勾号才能正确格式化——他们不在安卓键盘上！）。

我对上述方法最大的担忧是，我总是丢弃prng生成的多达7个比特，这似乎很糟糕。我想了一些方法来考虑它们（例如一个简单的加法），但它们似乎非常不科学！

我知道mod技巧，你只需要生成一个序列，但我也知道它的弱点。

这是一条死胡同吗？最终，如果最好的解决方案是坚持当前的实现，我会的，我只是觉得必须有更好的方法！

RNGCryptoServiceProvider-更快地生成范围内的数字并保留分发

Stephen Toub和Shawn Farkas在MSDN上共同撰写了一篇名为《来自加密随机的故事》的优秀文章，如果您正在尝试RNGCryptoServiceProviders ，您一定应该阅读这篇文章

在它中，他们提供了一个继承自System.Random的实现（其中包含您正在寻找的不错的范围随机方法），但他们的实现没有使用伪随机数，而是使用RNGCryptoServiceProvider。

他实现Next（最小，最大）方法的方式如下：

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));
        }
    }
}

选择实现的理由以及关于随机性损失的详细分析，以及他们正在采取哪些步骤来产生高质量的随机数，都在他们的文章中。

线程安全缓冲加密随机

我已经编写了Stephen类的扩展实现，该类使用了随机缓冲区，以最大限度地减少调用GetBytes（）的开销。我的实现还使用同步来提供线程安全，从而可以在所有线程之间共享实例，以充分利用缓冲区。

我是为一个非常特定的场景写这篇文章的，因此您当然应该分析一下，考虑到应用程序的特定争用和并发属性，这对您来说是否有意义。如果你不想查看的话，我把代码扔到了github上。

基于Stephen Toub和Shawn Farkas实现的线程安全缓冲CryptoRandom

当我写它的时候（几年前），我似乎也做了一些分析

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                              |
|---------------------|------------------------------------|

请注意，这些测量仅描述了一个非常具体的非现实世界场景，仅应用于指导，测量您的场景以获得正确的结果。

如果使用while循环，这将是缓慢的，并且基于未知数量的迭代。

您可以在第一次尝试时使用模运算符（%）来计算它。

但是，如果我们用模压缩结果，我们会立即在概率分布中产生不平衡。

这意味着，如果我们只关心生成数的速度，而不关心概率随机性的话，就可以应用这种方法。

这里有一个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())
        {
            var 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 内的任意数字

小型测试：

var 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

您可以用很小的开销一次生成更多的字节。RNGCrptoService的主要开销是填充字节的调用本身。

虽然你可能会丢弃未使用的字节，但我会尝试一下，因为我从这个和模方法（你没有使用）中获得了非常好的速度。

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;
}

以下是对@Andrey WD上述答案的改编，但不同之处在于，您只需发送一个已经生成的随机数（在这种情况下，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;
    }

以下是如何有效地获得一个干净的随机数数组。我喜欢它如何干净地封装获取随机数，使用它的代码不必在每次迭代中都进行字节转换，就可以使用BitConverter获得int或long。我还认为，通过将字节奇异地转换为数组类型，可以提高性能。

    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);
        }

public int RandomNumber(int min = 1, int max = int.MaxValue)
{
    using (var rng = new RNGCryptoServiceProvider())
    {
       byte[] buffer = new byte[4];
       rng.GetBytes(buffer);
       return (int)(BitConverter.ToUInt32(buffer, 0) >> 1) % ((max - min) + 1);
    }
}
相关文章：