水库采样

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

随着证据接近结束.

Answer 2

按照Knuth(1981)的描述,储层采样(算法R)可以实现如下:

import random

def sample(iterable, n):
    """
    Returns @param n random items from @param iterable.
    """
    reservoir = []
    for t, item in enumerate(iterable):
        if t < n:
            reservoir.append(item)
        else:
            m = random.randint(0,t)
            if m < n:
                reservoir[m] = item
    return reservoir