首先是和某个知名算法题相反的问题。这里给定一个可以概率均等地生成0到6的随机数生成器要求用这个生成器创造出能概率均等地生成0到4的随机数生成器。有人可能会立刻给出这样的答案func rand5() int {return rand7() % 5}然而这个答案只满足了输出的范围在0到4不满足概率均等所以不正确。这种时候列表法的作用就显现出来了rand7的输出rand7 % 500112233445061发现问题了吗0和1出现了两次它们出现的概率是其他数字的两倍因此概率分布并不均等。通过列表法我们其实也发现了这个问题真正的解法除掉5和6的话剩下的输出不仅符合要求概率也是均等的所以代码会变成这样func rand5() int {n : rand7()for n 5 {n rand7()}return n}上面的代码其实就是随机采样算法中非常重要的一种拒绝采样。同样上面的rand7生成rand5也可以归类成一大类问题给定一组满足规律或者特征是g(x)的样本现在需要从这些样本中筛选出或者生成另一组满足特征是f(x)的样本。解决这类问题的算法很多而拒绝采样是比较直观的判断g(x)的样本是否符合要求不符合的就排除取下一个样本符合要求的就归类到满足f(x)的样本集合中。按照这个角度来看上面的问题可以划分为几个基本元素g(x)rand7f(x): rand5需要拒绝的样本大于等于5的整数拒绝采样在大多数时间都能获得理想的结果但还有采样率需要注意。采样率就是g(x)的样本中有多少可以被接受采样率太低的时候意味着算法的效率也会非常低。所以我们简单算算rand5的采样率是七分之五大约70%。这个概率不大不小勉强合适。当采样率过低的时候要么得改变拒绝采样的标准或范围要么就不能再使用拒绝采样了。go标准库的做法标准库里当然不会有rand5和rand7但它提供了一个叫Int63n的函数它解决的问题是如何从均匀分布在[0, 2⁶⁴)范围上的随机整数中生成均匀分布在范围[0, n)上的随机整数。换句话说虽然范围不一样了但还是同一个问题。我们肯定不能像上面那样把大于等于n的样本全丢了因为2⁶⁴包含至少1844京1E16个整数样本这会带来低得无法接受的采样率。但因为我们是用mod来选择范围内的随机数的因此我们可以选择n的倍数这个证明太简单了列表法加归纳就行。或者还可以这么想有一个整数常数Cx % n和Cx % n能产生的输出的种类和它们的数量都是完全相同的所以如果样本能均匀分布在[0, n)的范围上那么范围[0, C·n]只不过是[0, n)重复了C次所以样本在每一段上都是均匀分布的整个合起来的区间上也是均匀的。有了常数C这样使得我们可以尽可能地让更多的样本被采样这样能降低重试的次数。C其实也很好选择取一个2⁶⁴内的n的最大的倍数就行如果C本身能被2⁶⁴整除那么C就是2⁶⁴/n。所以标准库是这样写的:func (r *Rand) Int63n(n int64) int64 {if n 0 {panic(invalid argument to Int63n)}if n(n-1) 0 { // n is power of two, can maskreturn r.Int63() (n - 1)}max : int64((1 63) - 1 - (163)%uint64(n))v : r.Int63()for v max {v r.Int63()}return v % n}代码还是很简单的超过C·n的样本全部拒绝采样剩下的样本就能保证在mod n的时候获得分布均匀的随机整数了。采样率是多少我们可以利用拒绝率来反推这里拒绝率还挺好算的就是(163)%uint64(n)算下来拒绝了少的时候是百亿分之一多的时候是数千万分之一——都很低基本上大多数时间最多两次重试就能获得想要的结果了。但作为标准库它的性能还不够尤其是go的编译优化非常弱的现实下更需要高效的算法弥补。问题出在哪首先不是采样率这个采样率是足够的问题出在它需要两次64位除法除法运算相比其他运算比如右移要慢很多何况还是两次别的语言中的标准库采用的算法只需要0到1次除法就够了。好在go提供了math/rand/v2采用了更高效的算法。新算法依旧基于拒绝采样但对采样的范围进行了变更具体是这样的依然用概率均等的rand64生成一个随机整数x现在把x*n这样生成的值的范围是[0, n·2⁶⁴)因为是对已有范围的等比扩大所以x*n在[0, n·2⁶⁴)依旧是均匀分布的不过要注意范围扩展了但样本的总量不变还是2⁶⁴个[0, n·2⁶⁴)可以均等分成n个范围分别是[0, 2⁶⁴),[2⁶⁴, 2*2⁶⁴),[2*2⁶⁴, 3*2⁶⁴)...[(n-1)*2⁶⁴, n*2⁶⁴)这样每一个均等分割的范围整除以2⁶⁴就可以得到一个整数kk一定在[0, n)内k可以当作符合要求的结果而整除以2⁶⁴实际上可以转换成位运算这样除法运算可以减少一次。新算法有几个问题第一个是x*n在大多数情况下会超过2⁶⁴但这不用担心因为go提供了高性能128位整数运算。第二个是x*n虽然在[0, n·2⁶⁴)均匀分布但我们怎么保证在均等分割的每个[(k-1)*2⁶⁴, k*2⁶⁴)上也是均等分布的呢答案是如果只有上面写的六个步骤我们保证不了。原因是因为要想保证x*n均匀分布在每个[(k-1)*2⁶⁴, k*2⁶⁴)上我们就要保证x本身要均匀分布在[(k-1)*(2⁶⁴/n), k*(2⁶⁴/n))上换人话说就是把2⁶⁴分割成n份每份里的样本数量都要一致。因为我们的样本都是整数而不是实数所以动动脚趾就能想到很多数是不能整除2⁶⁴的因此会留下“余数”。但我们的新算法实际上假设了x均匀分布在2⁶⁴分割出来的均等的范围内。不能整除的情况下意味着即使按最均匀的办法分割也会存在一部分范围比其他的范围多几个样本或者少几个样本会多还是会少取决与你对2⁶⁴/N取整的方式。但这问题不大通常分段直接的数量差异对概率产生的误差非常小比如我们把n取6按尽可能均匀的分割就存在4个分段比剩下的分段里的样本总数多1个但每个分段的样本数量都有超过3E18个多一个还是多两个带来的影响几乎可以忽略不计。然而标准库最重要的是要保证结果的正确性即使可能性是3E18分之一它依旧不是0函数的实现是不正确的更何况根据n的选择n越大分段的样本数量越少分段之间数量差异带来的影响就会越来越大总有一个n能让结果的误差大到无法忽略。问题其实也好解决因为我们知道始终会有一些分组的样本是多余的我们只要保证分组里的样本数量一致就行不需要关心具体剔除的样本是什么。假设我们采用向下取整的办法那么会存在一些理论上应该在分段k上的样本跑到k1的分组上这些样本通常分布在分段的起始位置上我们可以把这些样本拒绝采样这样比较容易实现。这些样本乘以n之后会落在[k*2⁶⁴, k*2⁶⁴(2⁶⁴%n))上。剔除这些样本后我们就能保证x*n在每个[(k-1)*(2⁶⁴/n), k*(2⁶⁴/n))上都是均匀分布的了。思路理解了看代码也就不难了func (r *Rand) uint64n(n uint64) uint64 {if is32bit uint64(uint32(n)) n {return uint64(r.uint32n(uint32(n)))}if n(n-1) 0 { // n is power of two, can maskreturn r.Uint64() (n - 1)}hi, lo : bits.Mul64(r.Uint64(), n)if lo n {thresh : -n % n // 2⁶⁴ % n 的简化形式for lo thresh {hi, lo bits.Mul64(r.Uint64(), n)}}return hi}精髓在于利用(x*n) 64来避免了x % n带来的除法运算。而且新算法不用一开始就算余数因此运气好的时候可以一次除法都不做。还有一个小疑问128位乘法够了吗肯定够了因为n最大也只能取到2⁶⁴这意味这x*n的范围最大也只到[0, 2⁶⁴·2⁶⁴)128位乘法刚好够用。最后做下性能测试标准库里已经提供了在我的10代i5上旧算法一次调用需要18ns新算法只需要5ns两者使用的随机数发生器是一样的因此可以说新算法快了3倍提升还是很可观的。从rand5生成rand7上一节讨论了从更大的样本空间里筛选出特定特征的子集这一节我们反过来从范围更小的样本空间里派生出有某一特征的超集。同时这也是一道常见的中等难度的算法题。首先要考虑的是如何把受限的样本空间尽量扩张。上一节我们用乘法来扩展了样本分布的范围然而乘法尤其是乘以常数是没法增加样本数量的因此这个做法只能pass。加法可以平移样本的范围但也不能增加样本总量而且我们需要样本空间是[0, x)平移之后起点都变了因此也不行。那剩下的可行的也最稳定的办法是rand5() * rand5()。它像乘法一样能扩张样本的范围同时因为不是乘以常数因此还有机会产生新的样本。我们列个表看看rand5rand5rand5 * rand5000010020030040100111122133144200212224236248300313326339341240041442843124416确实有新样本出现了但不够连续比如没有7和10。因此这条路是不通的。这时候就要上原汁原味的拒绝采样算法了我们使用5 * rand5 rand5rand5rand55 * rand5 rand5000011022033044105116127138149201021112212231324143015311632173318341940204121422243234424