在生成1..n范围内的N个唯一随机数时，哪种算法的性能和顺序更好？

Question

1

拿一个n个元素的数组：{ 1, 2, 3, .... n }。使用任何标准的随机打乱算法来打乱该数组。修改后的数组的前N个元素就是您要找的结果。

2

在循环中简单地使用Random.Next()，并检查它是否已存在于Dictionary中，直到我们有N个数字为止。

请注意，N << n（N比n小得多）。

- user415789

Answer 1

这完全取决于两个值（n和N）。

对于较大的n和较小的N（例如，在零到一百万之间选择两个不同的随机值），选项二将更好。这里的预期时间可能很难计算，并且远远超出了我的周日晚上能力范围...但基本上你需要在外部循环中迭代N次；然后您需要测试是否已经返回该值（一旦您已经选择了m个值，这可能是O(m)）；然后，如果您发现该值，需要重新尝试-这将没有时间上限，但有复杂的概率计算时间。

当n和N彼此接近时（例如，在1到100之间选择99个随机值），那么对选项一进行微调（实际上只挑选所需数量的值，而不是打乱整个数组）将更好。使用Fisher-Yates shuffle，您将获得O(n)。

在实践中：

• 如果我知道n很大而N很小，我会选择第二个选项
• 如果我知道n的值与N的值“差别不是很大”，我可能会选择第一个选项
• 如果难以决定但我提前知道了这些值，我会分别运行几次并对两者进行基准测试
• 如果我完全不知道这些值，我会在许多不同的(n, N)组合上多次运行这两个选项，以尝试更好地找到平衡点。

- Jon Skeet

Answer 2

这两种方法都不是最好的。您需要使用 Fisher-Yates 洗牌算法。随机解决方案的问题在于您需要在前面做很多不必要的工作。第二个解决方案的问题在于重复的可能性随着时间的推移而增加，因此您需要丢弃很多值。

对于一个非常高效的解决方案，它可以为您提供一个子集，零可能出现重复（并且没有不必要的排序），Fisher-Yates 是最好的选择。

dim n[N]                  // gives n[0] through n[N-1]
for each i in 0..N-1:
    n[i] = i              // initialise them to their indexes
nsize = N                 // starting pool size
do N times:
    i = rnd(nsize)        // give a number between 0 and nsize-1
    print n[i]
    nsize = nsize - 1     // these two lines effectively remove the used number
    n[i] = n[nsize]

通过从一个数字池中随机选择一个数字，将其替换为该池的顶部数字，然后缩小池的大小，您可以获得一次洗牌而无需担心大量的交换。

如果数字很高，这非常重要，因为它不会引入不必要的启动延迟。

例如，检查以下基准测试，选择10个数字从10个数字中：

<------ n[] ------>
0 1 2 3 4 5 6 7 8 9  nsize  rnd(nsize)  output
-------------------  -----  ----------  ------
0 1 2 3 4 5 6 7 8 9     10           4       4
0 1 2 3 9 5 6 7 8        9           7       7
0 1 2 3 9 5 6 8          8           2       2
0 1 8 3 9 5 6            7           6       6
0 1 8 3 9 5              6           0       0
5 1 8 3 9                5           2       8
5 1 9 3                  4           1       1
5 3 9                    3           0       5
9 3                      2           1       3
9                        1           0       9

随着你的操作，你会看到池中的数量减少，因为你总是用未使用过的替换已使用过的，所以不会重复。

- paxdiablo

---

那不是#1所追求的具体例子吗？ - jason

不，它不是这样的。#1 首先对整个数组进行排序，而且你需要比 N 更多的交换来获得一个良好的分布，因为有些交换会替换已经被交换过的元素。Fisher-Yates 完全没有前期成本，只在必要时进行交换（在 n-from-m 场景中仅进行 n 次交换，而不是 some-multiple-of-m 次）。 - paxdiablo

我提到过 N << n!，其中 N 远小于 n!。 - user415789

@paxdiablo：Fisher-Yates是一种用于生成有限集合的随机洗牌算法。#1建议对包含数字[1，n]的数组进行随机洗牌，该数组是一个有限集合。听起来Fisher-Yates算法很适合这个任务。 - jason

@Jason。问题要求提供性能友好的解决方案。FY是一种有效地获取集合的随机子集（可能是完整集合，但不一定）的方法。随机洗牌整个数组是不必要且效率不高的。举个例子，让我们从1000个元素中选出5个。为了改变数组的前5个元素，你需要很多交换操作，因为平均而言，第一个元素（例如）只会在500次迭代中被交换一次。当Fisher Yates可以用五次交换给你相同的结果时，这是相当低效的。 - paxdiablo

@HPT：我提到过N << n!，N比n!小得多。如果你担心内存限制，请尝试我链接的代码。它具有O（N）空间和O（N）时间复杂度。 - Andras Vass

Answer 3

部分Fisher-Yates算法，经过一些调整*：

在范围为[0,8000]内生成1000个不同整数的算法？

&

如何选择一组随机的值？

_{* 主要的收获在于减少了内存使用，因此它现在最多与所选项目的数量成比例，而不是可选择项目的数量。如果 N << n（正如您所提到的），这可以提供重大节省。（无论 N 接近 n 多少，空间使用都被限制在 O(n/2)。）}

_{运行时间为 O(N)。}

_{除此之外，这是一个相当常见的部分 Fisher-Yates，也称为 Knuth shuffle。}

- Andras Vass

Answer 4

在极端情况下，2 可能永远无法完成，因为它生成的每个数字都可能已经在列表中了。 但是，通常情况下，您将迭代超过 N 个数字。

1 保证以有限的时间完成。

- ChrisF