最快的随机数生成器 [英] The fastest random number Generator
问题描述
我打算通过Swift 3实现一个随机数生成器.我有三种不同的方法可以不间断地生成一万次整数(在0和50000之间).
I'm intending to implement a random number generator via Swift 3. I have three different methods for generating an integer (between 0 and 50000) ten thousand times non-stop.
这些生成器是否使用生成值的相同数学原理?
Do these generators use the same math principles of generating a value or not?
哪个生成器在运行时(具有10000次迭代)消耗的CPU和RAM更少?
What generator is less CPU and RAM intensive at runtime (having 10000 iterations)?
方法A :
var generator: Int = random() % 50000
方法B :
let generator = Int(arc4random_uniform(50000))
方法C :
import GameKit
let number: [Int] = [0, 1, 2... 50000]
func generator() -> Int {
let random = GKRandomSource.sharedRandom().nextIntWithUpperBound(number.count)
return number[random]
}
推荐答案
所有这些文档都有很好的记录，并且大多数都已发布源代码.
All of these are pretty well documented, and most have published source code.
var generator: Int = random() % 50000
Well, first of all, this is modulo biased, so it certainly won't be equivalent to a proper uniform random number. The docs for random explain it:
random()函数使用非线性加性反馈随机数生成器，该函数采用大小为31个长整数的默认表.它返回范围内的连续伪随机数 从0到(2 ** 31)-1.该随机数生成器的周期非常大，大约为16 *((2 ** 31)-1).
The random() function uses a non-linear, additive feedback, random number generator, employing a default table of size 31 long integers. It returns successive pseudo-random numbers in the range from 0 to (2**31)-1. The period of this random number generator is very large, approximately 16*((2**31)-1).
但是您可以在Apple的 libc的源代码.
But you can look at the full implementation and documentation in Apple's source code for libc.
对比arc4random_uniform(没有模偏差)的文档:
Contrast the documentation for arc4random_uniform (which does not have modulo bias):
这些函数使用加密的伪随机数生成器非常快速地生成高质量的随机字节.一个数据池用于流程中的所有使用者，因此消耗 在程序流程下可以充当额外的搅拌.该子系统会定期从内核随机数子系统中重新植入，也可以在fork(2)上重新植入.
These functions use a cryptographic pseudo-random number generator to generate high quality random bytes very quickly. One data pool is used for all consumers in a process, so that consumption under program flow can act as additional stirring. The subsystem is re-seeded from the kernel random number subsystem on a regular basis, and also upon fork(2).
和源代码也可用.从arc4random_uniform要注意的重要一点是，它可以通过正确地调整模数然后生成随机数直到其在正确的范围内来避免模数偏差.原则上，这可能需要生成无限数量的随机值；在实践中，极少需要生成一个以上的东西，而且难以置信的是，它会产生更多的东西.
And the source code is also available. The important thing to note from arc4random_uniform is that it avoids modulo bias by adjusting the modulo correctly and then generating random numbers until it is in the correct range. In principle this could require generating an unlimited number of random values; in practice it is incredibly rare that it would need to generate more than one, and rare-to-the-point-of-unbelievable that it would generate more than that.
GKRandomSource.sharedRandom()也有据可查:
系统随机源与C函数的arc4random系列共享状态.使用此源生成随机数会修改对这些函数的将来调用的结果，而调用这些函数会修改此源所生成的随机值的序列.因此，该来源既不是确定性的也不是独立的，仅用于不依赖那些属性的琐碎游戏玩法.
The system random source shares state with the arc4random family of C functions. Generating random numbers with this source modifies the outcome of future calls to those functions, and calling those functions modifies the sequence of random values generated by this source. As such, this source is neither deterministic nor independent—use it only for trivial gameplay mechanics that do not rely on those attributes.
为了提高性能，您希望random()最快，因为它永远不会从系统熵池中植入种子，因此它也不会降低系统中的熵(尽管arc4random仅定期执行此操作，我相信大约每1.5MB随机字节生成一次；并非针对每个值).但是，与所有性能一样，您必须进行概要分析.当然，由于random()本身不会重新设定种子，因此它的随机性要小于arc4random，而arc4random本身的随机性要小于系统中的熵源(/dev/random).
For performance, you would expect random() to be fastest since it never seeds itself from the system entropy pool, and so it also will not reduce the entropy in the system (though arc4random only does this periodically, I believe around every 1.5MB or so of random bytes generated; not for every value). But as with all things performance, you must profile. Of course since random() does not reseed itself it is less random than arc4random, which is itself less random than the source of entropy in the system (/dev/random).
如有疑问，请使用GameplayKit.苹果根据他们认为在大多数情况下效果最好的方式选择了sharedRandom()的实现.否则，请使用arc4random.但是，如果您真的需要最小化相当好"(但不是密码)随机数对系统的影响，请查看random.如果您愿意采用如果您不太仔细看就可以随机获取"的数字，并且对系统的影响甚至更低，请查看rand.并且，如果您希望对系统几乎没有影响(保证为O(1)，可内联)，请参见 XKCD的getRandomNumber() .
When in doubt, if you have GameplayKit available, use it. Apple selected the implementation of sharedRandom() based on what they think is going to work best in most cases. Otherwise use arc4random. But if you really need to minimize impact on the system for "pretty good" (but not cryptographic) random numbers, look at random. If you're willing to take "kinda random if you don't look at them too closely" numbers and have even less impact on the system, look at rand. And if you want almost no impact on the system (guaranteed O(1), inlineable), see XKCD's getRandomNumber().
这篇关于最快的随机数生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
