从具有均匀分布概率的流中选择元素

Question

给你:

1. 流(流的末尾是EOF)
2. 一个函数,next()用于获取流中的下一个元素并使流中的指针前进
3. 随机生成器生成0到1之间的浮动(包含)均匀

输出:

• 被证明是随机(均匀分布)选择的元素

你可以有一两个变量.

你不能使用数组/列表,你不能这样说trying to get all elements out and store them all and then pick.

---

这是一个面试问题.

我的想法是:

1. 我使用var cur来存储最近保存的元素
2. 所以,如果我得到一个新元素,我生成一个随机0或1使用生成器,如果它是0那么cur = new element; 否则,继续;
3. 如果我得到EOF,那么返回cur

---

我的想法是否正确？怎么证明？

---

这是一个相同的问题

你如何在未知长度的链表中选择一个统一的随机元素？

Answer 1

让当前元素的索引为i.

选择以概率"记住"当前元素1/i.当达到EOF时,产生你记得的元素.

最后,对于具有索引的每个元素,i都有可能被选择:

根据这些指南,可以使用归纳进行正式证明.

Answer 2

此算法以1/2的概率选择流中的最后一个元素,因此除非流的大小= 2,否则这不是有效的解决方案.

一种有效的方法是将从[0..1]之间的均匀分布中绘制的随机浮点值分配给每个元素,并返回末尾具有最大(或最小)值的那个.这可以在O(1)辅助空间中完成,您只需要记住最大值和相关元素.