python - 从大流中选择一个随机元素有什么大不了的？

Question

那就是问题所在:

给定一个元素流太大而无法存储在内存中，以均匀的概率从流中选择一个随机元素。

那么为什么“官方”解决方案是这样的:

import random
def pickRandom(stream):
    random_element = None
    for i, e in enumerate(stream):
        if i == 0:
            random_element = e
        elif random.randint(1, i + 1) == 1:
            random_element = e
    return random_element

而不是这个:

import random
random_element = stream[random.randint(0,len(stream))]

Answer 1

扩展我的评论:
我猜这是因为你不能知道 len(stream) 而不用尽(从中读取所有项目)。如果您想象流是一个网络套接字，有人向您发送一堆数据项然后关闭套接字，则您只能从套接字读取数据一次。你不能复制所有的数据(因为它不适合内存(而且，尽管缺乏上下文，我认为这也意味着它也不适合磁盘)所以你有效地拥有1 查看每个数据项，然后它就丢失了。
“官方”(原文如此)解决方案基于一个聪明的数学技巧。顺便说一句，这种问题是我希望在一家糟糕的公司的技术/编码面试测试中看到的那种问题，并且会让我跑一英里。