algorithm - 水库取样

Question

为了从大小不确定的数组中检索 k 个随机数，我们使用了一种称为水库采样的技术。任何人都可以用示例代码简要地强调它是如何发生的吗？

Answer 1

我实际上并没有意识到这个有一个名字，所以我从头开始证明并实现了这个:

import random
def random_subset( iterator, K ):
    result = []
    N = 0

    for item in iterator:
        N += 1
        if len( result ) < K:
            result.append( item )
        else:
            s = int(random.random() * N)
            if s < K:
                result[ s ] = item

    return result

发件人:http://web.archive.org/web/20141026071430/http://propersubset.com:80/2010/04/choosing-random-elements.html

在接近尾声时给出证明。