快速随机选择算法

Question

给定一个由真/假值组成的数组，选择一个随机的索引具有真值的最有效算法是什么。

一个简单的草图算法如下：

a <- the array
c <- 0
for i in a:
    if a[i] is true: c++
e <- random number in (0, c-1)
j <- 0
for i in e:
    while j is false: j++
return j

有没有人能想出一个更快的算法？也许有一种方法可以只遍历列表一次，即使一开始不知道真实元素的数量？

- momeara

---

只是好奇想知道，这些类型的算法在哪些应用中使用？之前有一次我遇到了一个类似的问题，给定一个无限大小的数组，前 n 个位置填充为 1，其余都是零。现在将此数组交给一个新用户（不知道 n 的值），找出一个标记最后一个 1 所在位置的算法。我通过二分查找来解决了这个问题。请举一些例子说明它们在哪里被使用。 - avd

在这个问题中，数组的大小为52，这可能会影响答案（例如，您可以确定大小为52的数组适合内存，而这里的“a”可能不适合）。类似问题：https://dev59.com/LEjSa4cB1Zd3GeqPFXKE。 - Steve Jessop

Answer 1

使用“从无限列表中选择随机元素”的算法。

保持当前选择的索引，以及您看到的真值数量的计数。

当您看到一个真值时，增加计数，然后用概率P=(1/count)替换当前索引的选择。(所以你总是选择找到的第一个...然后你可能会以1/2的概率切换到第二个，然后你可能会以1/3的概率切换到第三个等等。)

这只需要一次扫描列表和恒定存储。(但它确实需要您计算更多的随机数。)特别地，它不需要您缓冲列表或返回到起点-因此它可以在无限输入流上工作。

请参见此答案，其中包含简单的“选择随机元素”算法的示例LINQ实现；只需要进行小的调整即可。

- Jon Skeet

---

这里有更多细节和证明：https://dev59.com/LEjSa4cB1Zd3GeqPFXKE#1134286。虽然措辞略有不同，但这个问题在功能上与那个问题是重复的。我的直觉是，如果数据在内存中，它很可能比两遍算法慢。但如果两遍性能不可接受，值得测试。 - Steve Jessop

@Steve：这取决于“真实”值的稀疏程度和生成随机数的成本。如果列表中有一百万个条目，其中只有2个是“真实”的，则使用此方法很可能会获胜。另一方面，如果你有一百万个条目，全部都是真实的，那么两次遍历算法可能会更快。总的来说，我只是喜欢一次遍历恒定存储算法的优雅 :) - Jon Skeet

嘿，我刚刚在 Johannes 的回答中发表了与稀疏性相同的评论。我也同意关于优雅的看法，尽管我稍微担心使用大量随机数会使分析 RNG 中任何弱点的影响变得更加困难。 - Steve Jessop

谢谢Jon和Steve，我怀疑有类似这样的技巧，但是我以前不知道! - momeara

Answer 2

创建一个索引列表，该列表指向true值，并随机选择其中之一。需要 O(n)来遍历列表，并且需要尝试一次生成随机数。

- Joey

---

那肯定比我想出来的更快，但它使用O(n)的工作空间，而我的只使用恒定的工作空间。因此仍然可能有改进的空间。 - momeara

它肯定更快吗？如果真值非常罕见，那么它几乎肯定更快。如果假值非常罕见，那么它几乎肯定更慢。我不知道平衡点在哪里。 - Steve Jessop

是的，当然，真/假值的分布对于哪个算法更有效这个问题很重要。但是当这不确定时，一切都无从下手，像往常一样。尽管如此，我认为Jon的答案非常好，可能比这个更好。 - Joey

@Steve：这取决于你需要多频繁地执行此操作。建立索引只需一次，因此即使假值非常罕见，使用索引最终也会更快。 - Jerry Coffin

是的，我没有想到：在数组内容下一次更改之前，可能有一定数量的选择保证。如果我们可以稍微扩大范围，那么最好完全摆脱标志数组，只保留包含“真实”索引的结构。插入/删除会变慢，但选择会更快。 - Steve Jessop