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

Question

1

取n个元素的数组：{ 1，2，3，...N }。使用任意随机混洗数组的标准算法对数组进行混洗。修改后的数组的前N个元素就是您要查找的内容。

2

只需在循环中使用Random.Next()并检查它在Dictionary中是否已经存在，直到我们有N个数字。

请注意，N << n(N非常小于n)

Answer 1

这两个都不是最好的。你需要一个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

您可以看到池随着时间的推移而减少，因为您总是用未使用的池替换已用的池，因此不会有重复的情况。

Answer 2

它完全取决于两个值(n和N)。

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

当n和N彼此接近时(例如，选择1到100之间的99个随机值)，那么调整到选项1(实际上只选择需要的值，而不是打乱整个数组)会更好。使用Fisher-Yates shuffle，你会得到O(n)。

在实践中：

• 如果我知道我会有一个大的n和一个小的N，我会选择第二个选项
• 如果我知道我会有一个比N“不是很大”的n值，我可能会选择第一个选项
• ，如果它太接近了，但我提前知道了这些值，我会在每种方式上运行几次，并对两个
• 进行基准测试如果我根本不知道提前的值，我会对许多不同的(n，N)配对，尝试更好地了解如何计算平衡。

Answer 3

在极端情况下，2可能永远不会结束，因为它生成的每个数字都可能已经在列表中。然而，通常情况下，您将迭代远远超过N个数字。

1保证在有限时间内完成。