算法技术手册（原书第2 版）

316

｜

第

11

章

首先必须能够从集合中随机选择出某些元素然后对它们进行标记。由于假设集合是有限

规模的，因此在某个时间点上最后会发现随机选择函数返回了之前标记过的元素。这个

时间点拖得越长，那么数据规模就会越大。在统计学上，这叫作“重置抽样”。而根据

标记过的元素数量

k

，我们可以大概估计出

k

和

n

的关系，即：

Example 11-6. Implementation of probabilistic counting algorithm

def computeK(generator):

"""

Compute estimate of using probabilistic counting algorithm.

Doesn't know value of n, the size of the population.

"""

seen = set()

while True:

item = generator()

if item in seen:

k = len(seen)

return 2.0*k*k/math.pi

else:

seen.add(item)

Let’s start with some intuition. We must have the ability to pick random elements

from the set and mark them as being seen. Since we assume the set is finite, at some

point ...