生成唯一（不重复）随机数的高效算法

Question

我希望解决以下问题。我需要从一个非常大的集合中进行抽样，数量级约为10^20，并提取一个大小约为10％-20％的无重复样本。考虑到集合的大小，我认为像Fisher-Yates这样的算法是不可行的。

我想到了类似随机路径树的算法，可以在O(n log n)内完成，但我想问一下是否已经有类似的实现。

谢谢您的时间！

- Santiago Hernandez Orozco

---

你真的想要采样10^19到2 * 10^19个项目吗？你有多少百万兆字节的存储空间？ - gnasher729

@gnasher729：时间也是一个因素。10^19纳秒比三百年多一点。这表明需要一个大规模并行算法。 - rici

是的，我有一台超级计算机可供使用，但我们必须非常好地计划这次执行。我已经尝试在同类型的较小数据集上进行替换抽样，正如预测的那样，它不起作用。分布本身是非标准的。幸运的是，存储不是问题，我们实时生成对象并将结果记录在有限大小的哈希表中，然后可以将其丢弃。 - Santiago Hernandez Orozco

另一个选择是线性反馈移位寄存器，它可以被配置为以伪随机顺序生成从1到N的所有值，而且不会重复。 - Jim Mischel

Answer 1

我不知道下面描述的技术在正式的随机性测试中表现如何，但它确实产生了“看起来像随机”的结果。

你可以使用乘法逆元来实现这个过程。思路是使用数学函数将范围在1-N内的每个整数映射到相同范围内的唯一整数。这通常用于生成混淆密钥，但你可以通过更改种子值和提取项的范围来适应它以生成随机子集。

我之前写过一篇博客文章，介绍了如何生成混淆的连续键。以下是代码：

private void DoIt()
{
    const long m = 101;         // Number of keys + 1
    const long x = 387420489;   // must be coprime to m

    // Compute the multiplicative inverse
    var multInv = MultiplicativeInverse(x, m);

    // HashSet is used to hold the obfuscated value so we can ensure that no duplicates occur.
    var nums = new HashSet<long>();

    // Obfuscate each number from 1 to 100.
    // Show that the process can be reversed.
    // Show that no duplicates are generated.
    for (long i = 1; i <= 100; ++i)
    {
        var obfuscated = i * x % m;
        var original = obfuscated * multInv % m;
        Console.WriteLine("{0} => {1} => {2}", i, obfuscated, original);
        if (!nums.Add(obfuscated))
        {
            Console.WriteLine("Duplicate");
        }
    }    
}

private long MultiplicativeInverse(long x, long modulus)
{
    return ExtendedEuclideanDivision(x, modulus).Item1 % modulus;
}

private static Tuple<long, long> ExtendedEuclideanDivision(long a, long b)
{
    if (a < 0)
    {
        var result = ExtendedEuclideanDivision(-a, b);
        return Tuple.Create(-result.Item1, result.Item2);
    }
    if (b < 0)
    {
        var result = ExtendedEuclideanDivision(a, -b);
        return Tuple.Create(result.Item1, -result.Item2);
    }
    if (b == 0)
    {
        return Tuple.Create(1L, 0L);
    }
    var q = a / b;
    var r = a % b;
    var rslt = ExtendedEuclideanDivision(b, r);
    var s = rslt.Item1;
    var t = rslt.Item2;
    return Tuple.Create(t, s - q * t);
}

该程序的前几行输出如下：

1 => 43 => 1
2 => 86 => 2
3 => 28 => 3
4 => 71 => 4
5 => 13 => 5
6 => 56 => 6
7 => 99 => 7
8 => 41 => 8
9 => 84 => 9
10 => 26 => 10

如果您想改变函数开始的m和x值来反映您的数字范围，这将对您有用。而不是总是从1开始并获取前10或20％，您可以从50％标记开始，然后从那里开始。或者使用一些技术来提取每个第五个数字，或者任何其他东西，只要您的方法不重复访问相同的数字。

如果需要更多运行，请更改x值。

生成乘法逆元（将其视为随机数生成器的种子）是O（log n）操作。之后，生成每个数字都是O（1）。

当然，如果您处理的数字在10 ^ 20的范围内，您将不得不修改代码以使用大整数类。

- Jim Mischel