蓄水池抽样

Question

从一个大小未知的数组中检索 k 个随机数，我们使用一种称为蓄水池抽样的技术。 能否有人简要介绍一下如何使用示例代码?

- Jony

---

这个页面包含了一个很好的解释和伪代码。（我最初链接的维基百科页面不清楚，而且伪代码也不完整。） - Stephen C

我几个月前写了一篇关于这个问题的博客文章，其中包含C#实现：http://gregbeech.com/blog/sampling-very-large-sequences。我发现最好的工作原理描述在这里：http://gregable.com/2007/10/reservoir-sampling.html。 - Greg Beech

相关问题 https://dev59.com/U3VD5IYBdhLWcg3wNIvc - Ian Mercer

Answer 1

我其实不知道这个有一个名称，所以我从零开始证明并实现了它：

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

附近有证明。

- Larry

---

@Larry：你的代码中accept it with probability s/k部分在哪里？[引自http://blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx的算法] - Lazer

好巧，似乎在那篇文章和我的代码中，我们使用相同的变量，但用于不同的事情。 我的“K”似乎是他们的“S”，我的代码中的“N”似乎是他们的“K”。 换句话说，我以 K/N 的概率接受事物，其中 N 是事物的当前计数。 - Larry

我想问的是你在代码中如何实现概率。不管怎样，现在我明白了。谢谢！ - Lazer

不太明白你的问题，但是如果你能具体说明，我可以更详细地解释这段代码！=） - Larry

有没有一种方法可以从一个无界流中创建多个不同大小的水库？也就是说，能够遍历一次流并将其采样到多个水库之一？假设每个水库的大小可以不同或相等。 - CMCDragonkai

Answer 2

根据Knuth（1981）的描述，Reservoir Sampling（算法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

- sam

---

这个与被接受的回答有什么不同呢？我认为这两者是完全一样的，即使这段代码更优雅。 - Quentin Pradet

如果有人对更详细的解释或Knuth的证明感兴趣，它可以直接与已发表的研究(Knuth, 1981)相关联。 - sam

在random.randint中，满足0 <= random.randint(0,t) <= t。 - Ahmed Fasih

@sam randint 不是包含在内的吗？ - user76284

@user76284 正确的，而且应该是这样的。让iterable包含11个我们想要从中抽取n=10的项目。对于第11个项目，t将为10（因为enumerate从0开始），我们生成一个介于0和10之间的随机整数（即11种可能性），使得将第11个项目添加到reservoir的概率为n/t = 10/11。 - sam

Answer 3

Java

import java.util.Random;

public static void reservoir(String filename,String[] list)
{
    File f = new File(filename);
    BufferedReader b = new BufferedReader(new FileReader(f));

    String l;
    int c = 0, r;
    Random g = new Random();

    while((l = b.readLine()) != null)
    {
      if (c < list.length)
          r = c++;
      else
          r = g.nextInt(++c);

      if (r < list.length)
          list[r] = l;

      b.close();}
}

- Srba

---

@alestanis 但现在是Java！ - CMCDragonkai

Answer 4

Python解决方案

import random

class RESERVOIR_SAMPLING():
    def __init__(self, k=1000):
        self.reservoir = [] 
        self.k = k
        self.nb_processed = 0

    def add_to_reservoir(self, sample):
        self.nb_processed +=1
        if(self.k >= self.nb_processed):
            self.reservoir.append(sample)
        else:
            #randint(a,b) gives a<=int<=b
            j = random.randint(0,self.nb_processed-1)
            if(j < k):
                self.reservoir[j] = sample

k = 10
samples = [i for i in range(10)] * k
res = RESERVOIR_SAMPLING(k)
for sample in samples:
    res.add_to_reservoir(sample)

print(res.reservoir)

out[1]: [9, 8, 4, 8, 3, 5, 1, 7, 0, 9]

- Firas Omrane