好的，用荒谬的答案解决另一个荒谬的日常代码问题
问：给定一个元素流太大而无法存储在内存中，从具有均匀概率的流中选择一个随机元素
A：
对于i = 0的基本情况，假设随机元素是第一个。然后我们知道它是有效的，因为
对于i = 0，我们会从[0, 0]中统一选取。
对于i > 0，在循环开始之前，[0, i - 1]中的任何元素K都有1 / i的机会被选择为随机元素。我们希望K有1 / (i + 1)的机会在迭代之后被选择。既然有机会已被选中但未与第i个元素交换1 / i * (1 - (1 / (i + 1)))是1 / i * i / (i + 1)或1 / (i + 1)
代码：
import random
def pick(big_stream):
random_element = None
for i, e in enumerate(big_stream):
if i == 0:
random_element = e
elif random.randint(1, i + 1) == 1:
random_element = e
return random_element
所以1/(k+1)，如果你还在一个循环中，它只是1/k，这个用I+1消除1/(k+1)似乎是人为的，不会影响O(n)的时间，而是使它成为O(n+1)，与O(n)相同。
这个问题到底是什么意思？这个算法看起来真的很肤浅，有什么建议真的可以打败O(n)吗？这种编程语言看起来很晦涩，但不是什么语言能接近它？有没有更优化(更具体(的语言？
编程语言(一旦修复了缩进(肯定是Python。
这个问题的真正含义是什么？这个算法看起来真的很肤浅，有什么建议真的可以打败O(n(吗？
这个问题主要是关于空间，而不是运行时。他们提供的算法在恒定空间中运行，这就是重点。天真的答案会占用大量的空间。
然而，有一种更简单(不一定更快(的算法，它也可以用于在O(n log k)时间和O(k)空间中对n元素中的k元素进行采样。它是这样工作的：
在接收流时，为流中的每个元素分配一个[0,1]中的统一随机实值。使用最小堆，跟踪
k最小随机值及其相关元素。一旦流被完全处理，就返回保留在堆中的元素。
对于k = 1，哪一个简单地变成：
在[0,1]中为每个元素分配一个均匀随机的实数，并返回具有最小随机值的元素。
这是@orlp为k=1:描述的算法的实现
import random
def pick(big_stream):
choice = None
minp = 1.0
for e in big_stream:
p = random.random()
if p >= minp:
continue
minp = p
choice = e
return choice