-2

我想生成满足0 <= result <= maxValue.

我已经有一个生成器，它返回内置无符号整数类型的全部范围内的统一值。让我们调用 this byte Byte()、ushort UInt16()和uint UInt32()的方法ulong UInt64()。假设这些方法的结果是完全一致的。

我想要的方法的签名是uint UniformUInt(uint maxValue)and ulong UniformUInt(ulong maxValue)。

我在找什么：

  1. 正确性
    我希望返回值分布在给定的时间间隔内。
    但是如果可以显着提高性能，那么非常小的偏差是可以接受的。我的意思是，在给定 2^64 值的情况下，允许区分概率为 2/3 的顺序偏差。
    它必须对任何maxValue.
  2. 性能
    该方法应该很快。
  3. 效率
    该方法确实消耗很少的原始随机性，因为根据底层生成器，生成原始字节可能会很昂贵。浪费几位是可以的，但消耗 128 位来生成一个数字可能是多余的。

也可以在某些成员变量中缓存上一次调用中遗留的一些随机性。

小心 int 溢出和包装行为。

我已经有了一个解决方案（我会把它作为答案发布），但这对我的口味来说有点难看。所以我想获得更好的解决方案的想法。

关于如何使用大maxValues 进行单元测试的建议也很好，因为我无法生成具有 2^64 个桶和 2^74 个随机值的直方图。另一个复杂情况是，对于某些错误，只有一些maxValue分布有很大的偏差，而另一些则只有很小的偏差。

4

3 回答 3

2

像这样的通用解决方案怎么样？该算法基于Java 的nextIntmethod使用的算法，拒绝任何会导致不均匀分布的值。只要您的UInt32方法的输出完全一致，那么这也应该是。

uint UniformUInt(uint inclusiveMaxValue)
{
    unchecked
    {
        uint exclusiveMaxValue = inclusiveMaxValue + 1;

        // if exclusiveMaxValue is a power of two then we can just use a mask
        // also handles the edge case where inclusiveMaxValue is uint.MaxValue
        if ((exclusiveMaxValue & (~exclusiveMaxValue + 1)) == exclusiveMaxValue)
            return UInt32() & inclusiveMaxValue;

        uint bits, val;
        do
        {
            bits = UInt32();
            val = bits % exclusiveMaxValue;

            // if (bits - val + inclusiveMaxValue) overflows then val has been
            // taken from an incomplete chunk at the end of the range of bits
            // in that case we reject it and loop again
        } while (bits - val + inclusiveMaxValue < inclusiveMaxValue);

        return val;
    }
}

理论上，拒绝过程可以永远循环下去；在实践中，性能应该相当不错。在不知道(a)预期使用模式和(b)底层 RNG 的性能特征的情况下，很难提出任何普遍适用的优化建议。

例如，如果大多数调用者将指定最大值 <= 255，那么每次请求四个字节的随机性可能没有意义。另一方面，请求更少字节的性能优势可能会被始终检查实际需要多少字节的额外成本所抵消。（当然，一旦你有了具体的信息，你就可以继续优化和测试，直到你的结果足够好。）

于 2012-03-01T00:39:08.680 回答
1

我不确定，他是一个答案。它肯定需要比评论更多的空间，所以我必须在这里写，但如果其他人认为这是愚蠢的，我愿意删除。

从我得到的 OQ 中，

  1. 熵位非常昂贵
  2. 其他一切都应该被认为是昂贵的，但比熵少。

我的想法是使用二进制数字减半，四分之一... maxValue 空间，直到它减少为一个数字。类似的东西

我将使用 maxValue=333（十进制）作为示例并假设一个函数getBit()，它随机返回 0 或 1

offset:=0
space:=maxValue

while (space>0)

  //Right-shift the value, keeping the rightmost bit this should be 
  //efficient on x86 and x64, if coded in real code, not pseudocode
  remains:=space & 1
  part:=floor(space/2)
  space:=part

  //In the 333 example, part is now 166, but 2*166=332 If we were to simply chose one
  //half of the space, we would be heavily biased towards the upper half, so in case
  //we have a remains, we consume a bit of entropy to decide which half is bigger

  if (remains)
    if(getBit())
      part++;

  //Now we decide which half to chose, consuming a bit of entropy
  if (getBit())
    offset+=part;

  //Exit condition: The remeinind number space=0 is guaranteed to be met
  //In the 333 example, offset will be 0, 166 or 167, remaining space will be 166
}

randomResult:=offset

getBit()可以来自您的熵源，如果它是基于位的，或者通过在第一次调用时一次消耗 n 位熵（显然 n 是您的熵源的最佳值），并将其转移到空。

于 2012-02-29T13:30:59.660 回答
0

我目前的解决方案。对我的口味来说有点难看。每个生成的数字也有两个部门，这可能会对性能产生负面影响（我还没有分析这部分）。

uint UniformUInt(uint maxResult)
{
    uint rand;
    uint count = maxResult + 1;

    if (maxResult < 0x100)
    {
        uint usefulCount = (0x100 / count) * count;
        do
        {
            rand = Byte();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else if (maxResult < 0x10000)
    {
        uint usefulCount = (0x10000 / count) * count;
        do
        {
            rand = UInt16();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else if (maxResult != uint.MaxValue)
    {
        uint usefulCount = (uint.MaxValue / count) * count;//reduces upper bound by 1, to avoid long division
        do
        {
            rand = UInt32();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else
    {
        return UInt32();
    }
}

ulong UniformUInt(ulong maxResult)
{
    if (maxResult < 0x100000000)
        return InternalUniformUInt((uint)maxResult);
    else if (maxResult < ulong.MaxValue)
    {
        ulong rand;
        ulong count = maxResult + 1;
        ulong usefulCount = (ulong.MaxValue / count) * count;//reduces upper bound by 1, since ulong can't represent any more
        do
        {
            rand = UInt64();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else
        return UInt64();
}
于 2012-02-29T12:40:05.430 回答