N面骰子投掷M次：最快统计各面出现次数的方法

常规循环生成M个随机数再计数的方式，当M数值很大时（比如百万级以上），会因为频繁的随机数生成和数组操作产生性能瓶颈。这里有个符合真实概率分布且效率更高的实现方式，本质是多项分布的直接采样：

核心思路：基于有序分割的计数生成 #

这个方法只需要生成N-1个随机数，就能直接算出各面的出现次数，完全符合真实投掷的概率分布，步骤如下：

1. 生成N-1个范围在[0, M]的随机整数；
2. 将这组随机数排序；
3. 计算相邻数的差值（包括开头的0和结尾的M），每个差值对应骰子某一面的出现次数。

举个例子：6面骰子投10次

• 生成5个随机数：[2,5,7,8,9]
• 排序后：[2,5,7,8,9]
• 计算差值：2-0=2（第1面）、5-2=3（第2面）、7-5=2（第3面）、8-7=1（第4面）、9-8=1（第5面）、10-9=1（第6面），最终得到[2,3,2,1,1,1]，和示例结果一致。

C# 实现代码 #

using System;
using System.Linq;

int[] GenerateDiceCounts(int diceFaces, int rollTimes)
{
    if (diceFaces <= 0 || rollTimes < 0)
        throw new ArgumentOutOfRangeException();
    
    if (rollTimes == 0)
        return new int[diceFaces];
    
    Random rng = new Random();
    // 生成N-1个0到rollTimes之间的随机数
    int[] splits = Enumerable.Range(0, diceFaces - 1)
                            .Select(_ => rng.Next(0, rollTimes + 1))
                            .OrderBy(x => x)
                            .ToArray();
    
    int[] counts = new int[diceFaces];
    // 计算第一个面的次数
    counts[0] = splits[0];
    // 计算中间面的次数
    for (int i = 1; i < diceFaces - 1; i++)
    {
        counts[i] = splits[i] - splits[i-1];
    }
    // 计算最后一个面的次数
    counts[diceFaces - 1] = rollTimes - splits[diceFaces - 2];
    
    return counts;
}

为什么之前的思路有问题 #

• 期望打乱法：这种通过随机加减调整期望计数的方式，无法复现多项分布的真实概率。因为不同计数组合的概率是由组合数决定的，比如[10,10,10,10,10,10]和[12,8,10,10,10,10]的概率并不相同，而对称调整会让这些组合的概率趋于平均，不符合真实情况，同时也没有合理的调整次数标准。
• 错误的线段分割：你之前尝试的线段分割应该是没做排序或范围错误，正确的有序分割才是符合概率分布的，因为它等价于把M次投掷的结果按骰子面分组，本质和逐个投掷的统计结果概率完全一致。

性能优势 #

当M远大于N时，这个方法的性能提升非常显著：比如M=1e6、N=6，常规方法需要生成100万个随机数，而这个方法只需要生成5个随机数，排序5个元素，内存和计算开销都大幅降低。

内容的提问来源于stack exchange，提问作者name