生成具有一定最大值的均匀随机整数
我想生成满足0 <= result <= maxValue
统一整数。
我已经有一个生成器,它在内置的无符号整数类型的整个范围内返回统一值。 让我们调用这个byte Byte()
的方法byte Byte()
, ushort UInt16()
, uint UInt32()
和ulong UInt64()
。 假设这些方法的结果是完全一致的。
我想要的方法的签名是uint UniformUInt(uint maxValue)
和ulong UniformUInt(ulong maxValue)
。
我在找什么:
- 正确性
我更喜欢在给定的时间间隔内分配返回值。
但如果显着提高性能,则可以接受非常小的偏差。 我的意思是指一个订单的偏差,允许区分符的概率为2/3给定2 ^ 64个值。
它必须适用于任何maxValue
。 - 性能
该方法应该很快。 - 效率
该方法确实消耗很少的原始随机性,因为取决于底层生成器,生成原始字节可能是昂贵的。 浪费几个比特很好,但消耗128比特来生成一个数字可能是过多的。
在某些成员变量中,还可以缓存前一次调用中的一些遗留随机性。
小心int溢出和包装行为。
我已经有了一个解决方案(我会将其作为答案发布),但这对我的口味来说有点难看。 所以我想获得更好的解决方案的想法。
关于如何使用大型maxValue
进行unit testing的建议也不错,因为我无法生成具有2 ^ 64个桶和2 ^ 74个随机值的直方图。 另一个复杂因素是,对于某些错误,只有一些maxValue
发行版有很多偏见,而其他发行版只有很小的偏差。
像这样的通用解决方案怎么样? 该算法基于Java的nextInt
方法使用的算法,拒绝任何会导致非均匀分布的值。 只要你的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,则每次要求四个字节的随机性可能没有意义。 另一方面,总是检查实际需要的额外成本可能会超过请求更少字节的性能优势。 (当然,一旦你掌握了具体的信息,你就可以继续优化和测试,直到你的结果足够好。)
我不确定,他的答案是肯定的。 它绝对需要比评论更多的空间,所以我必须在这里写,但我愿意删除,如果其他人认为这是愚蠢的。
从OQ我得到,那
- 熵位非常昂贵
- 其他一切都应该被认为是昂贵的,但不如熵。
我的想法是使用二进制数字到一半,quater … 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是你的熵源的最佳值),并将其转换为空。
我目前的解决方案 我的口味有点难看。 每个生成的数字也有两个分区,这可能会对性能产生负面影响(我还没有对此部分进行过分析)。
上述就是C#学习教程:生成具有一定最大值的均匀随机整数分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---计算机技术网(www.ctvol.com)!
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(); }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/1042921.html