# 蓄水池抽样

int32位 posted @ Mar 22, 2016 04:03:09 PM in algorithm , 2376 阅读

## 从一次面试说起

• 空指针检查（包括src和dest）
• 内存重叠，要检查指针是否重叠
• 最后拷贝时，别忘了在dest追加字符串终结符号0
• 如何保证dest已分配足够内存
• 为什么从后向前拷贝？

• 泛型参数（泛化编程）
• 类型必需可比较或者提供比较器
• 不能实例泛型类型，即不能new T[]或者new T()，只能使用Object数组
• 内存动态分配，内存拷贝（数组拷贝）

import random
def sample(filename, n = 3):
assert(filename is not None)
result = []
with open(filename) as f:
while len(result) < n :
line = random.choice(lines)
if line not in result:
result.append(line.strip())
return result

• 必须把文件内容全读入内存，如果文件很大怎么办？
• 设N为文件行数，n和N接近时，越到后面，冲突越大，效率极低。
• 有人说，先随机生成n个数构成一个集合A（还是有冲突哦），读取文件，当行数属于A时，取出该行，问题不就解决了？ 问题是文件总行数是多少？必须知道文件总行数才能知道随机数的取值范围啊。必须先扫描一遍文件？文件很大时这样的效率如何？

## 蓄水池抽样

1. 从文件中取前n行，结果集result
2. 令i表示当前行数，c为当前行内容，m = random(1, i)，即m为1～i的一个随机数。
3. 若m <= n, 则令result[m] = c，即替换第m行内容，否则舍弃c。
4. 若已到文件结尾，退出算法，返回result，否则转2

## 回到问题

import random
def sample(filename, n = 5):
assert(filename is not None)
result = []
with open(filename, mode = "r") as f:
for i in range(n):
if line == '':
return result
else:
result.append(line.strip())
i = n
for line in f:
k = random.randint(0, i)
if k < n:
result[k] = line.strip()
i += 1
return result

• 无匹配
• 无匹配
Haryana Board Model 说:
2022年9月03日 18:01

2022年12月27日 18:19

Great post I would like to thank you for the efforts you have made in writing this interesting and knowledgeable article. buy shrooms online

Bushra 说:
2022年12月29日 14:03

very interesting post.this is my first time visit here.i found so mmany interesting stuff in your blog especially its discussion..thanks for the post! wildlife removal Newmarket

2022年12月30日 18:10 Wonderful article, thanks for putting this together! This is obviously one great post. Thanks for the valuable information and insights you have so provided here. Meri Saas Bhoot Hai
2023年1月06日 19:09

Wow what a Great Information about World Day its very nice informative post. thanks for the post. kelowna movers

milan 说:
2023年1月10日 22:15

Reservoir sampling is a technique for randomly selecting a subset of items from a larger population. It is often used when it is impractical to sample the entire population, or when best online engagement rings store the population is too large to store in memory. To perform reservoir sampling, we first select an item at random from the population and add it to the reservoir. Then, for each subsequent item in the population, we select it with probability proportional to its size. This ensures that each item in the population has an equal chance of being selected.

(输入验证码)
or Ctrl+Enter