随机字符流选择均匀分布

Question

好吧，又是一个荒谬的日常代码问题，答案也很荒谬

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

答：

对于

i = 0

的基本情况，假设随机元素是第一个。然后我们知道它有效，因为

对于

i = 0

，我们会从

[0, 0]

中统一挑选。

对于

i > 0

，在循环开始之前，

K

中的任何元素

[0, i - 1]

都有

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

这个 elif

1/(k+1)

与

I+1

似乎是人为的，不会影响

O(n)

时间，而是使它

O(n+1)

这是与

O(n)

相同。

这个问题的真正含义是什么？这个算法看起来真的很肤浅，有什么建议真的可以打败

O(n)

吗？这种编程语言看起来很perlesque，但不知道有什么语言可以接近它？是否有更优化（更具体）的语言？

Answer 1

编程语言（一旦缩进固定）肯定是 Python。

这个问题的真正含义是什么？这个算法看起来真的很肤浅，有什么建议真的可以击败 O(n) 吗？

这个问题主要是关于空间，而不是运行时。他们提供的算法在恒定空间中运行，这就是重点。天真的答案会占用大量空间。

有一个更简单（不一定更快）的算法，它也可以用于在

k

时间和

n

空间中从

O(n log k)

元素中采样

O(k)

元素。它的工作原理如下：

在收到流中的每个元素时，将 [0, 1] 中的均匀随机实值分配给它。使用最小堆，跟踪

k

最小随机值及其关联元素。一旦流被完全处理，返回保留在堆中的元素。

对于

k = 1

来说，简单地变成：

为每个元素分配[0, 1]中的均匀随机实数值，并返回随机值最小的元素。

Answer 2

这是 @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