蓄水池抽样

int32位 posted @ Mar 22, 2016 04:03:09 PM in algorithm , 2660 阅读
转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

什么是蓄水池抽样，它能解决什么问题?

从一次面试说起

百度面试以算法为主啊，手动写代码。第一道题是实现c语言库函数strcpy，这个原理很简单，但要注意以下这几点：

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

第二道题是写一个类，实现堆的操作。说实话，虽然堆的操作不难，但要真正实现它并不容易。以下需要注意的点：

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

重点是第三道题目：给定一个文件，从中随机取出n行，并计算时间复杂度。我上来便是这样的代码：

import random
def sample(filename, n = 3):
    assert(filename is not None)
    result = []
    with open(filename) as f:
        lines = f.readlines()
    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时，取出该行，问题不就解决了？ 问题是文件总行数是多少？必须知道文件总行数才能知道随机数的取值范围啊。必须先扫描一遍文件？文件很大时这样的效率如何？

后来面试官问我知不知道分治法，我说了解，但这有关系么？文件分割建索引？全错！！！

蓄水池抽样

蓄水池抽样（Reservoir Sampling ）是一个很有趣的问题，它能够在o（n）时间内对n个数据进行等概率随机抽取， 例如：从1000个数据中等概率随机抽取出100个。另外，如果数据集合的量特别大或者还在增长（相当于未知数据集合总量）， 该算法依然可以等概率抽样。

以上摘自handspeaker博客

算法步骤为：

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

利用归纳法可以证明每行被取的概率是相等的，证明过程 见handspeaker博客

回到问题

问题解决了，毫无悬念！

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):
            line = f.readline()
            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

 

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！
  • 无匹配
  • 无匹配
Small_feed 评论 (87)
1
[回复]
Haryana Board Model 说:
2022年9月03日 18:01

Haryana Board Model Paper 2023 Class 4 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Haryana Board Model Paper Class 4 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

2
[回复]
SAAD 说:
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

3
[回复]
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

4
[回复]
SAAD 说:
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
5
[回复]
SAAD 说:
2023年1月06日 19:09

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

6
[回复]
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.

7
[回复]
Bushra sheikh 说:
2023年7月28日 14:01 thank you for a great post. Learn more
8
[回复]
Bushra sheikh 说:
2023年7月28日 19:33

Great post I would like to thank you for the efforts you have made in writing this interesting and knowledgeable article. Pressure cleaning Sunshine Coast

9
[回复]
Bushra sheikh 说:
2023年7月28日 22:09

Thanks for your information, it was really very helpfull.. Toowoomba Concreting Solutions QLD

10
[回复]
Bushra batool 说:
2023年8月12日 16:10

Thanks for the post and great tips..even I also think that hard work is the most important aspect of getting success.. Arif Bhalwani

11
[回复]
Bushra batool 说:
2023年8月12日 21:11

thank you for a great post. challenger freight

12
[回复]
Bushra batool 说:
2023年8月13日 00:44

Thanks for the post and great tips..even I also think that hard work is the most important aspect of getting success.. IRS Tax Attorney

13
[回复]
Bushra batool 说:
2023年8月13日 04:23

I really appreciate this wonderful post that you have provided for us. I assure this would be beneficial for most of the people. party rentals

14
[回复]
Bushra batool 说:
2023年9月06日 14:48

Editing software like Adobe Lightroom and Photoshop allows photographers to enhance and refine their photos. Adjustments to exposure, color, and sharpness can transform an ordinary image into an extraordinary one. most famous photographers

15
[回复]
Bushra batool 说:
2023年9月07日 15:55 Measure the backset, which is the distance from the door's edge to the center of the borehole. Common backset measurements are 2⅜ inches or 2¾ inches. Locksmith Whitstable
16
[回复]
Bushra batool 说:
2023年9月08日 16:40

I really appreciate the kind of topics you post here. Thanks for sharing us a great information that is actually helpful. Good day! website link

17
[回复]
shaikhseo 说:
2023年9月10日 13:12

thanks this is good blog. Law tutors in London

18
[回复]
Naveed 说:
2023年9月17日 17:04

I know your expertise on this. I must say we should have an online discussion on this. Writing only comments will close the discussion straight away! And will restrict the benefits from this information. here are the findings

19
[回复]
Naveed 说:
2023年9月17日 19:25

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information... More Bonuses

20
[回复]
Bushra batool 说:
2023年9月22日 22:41

Photography has evolved significantly over time, from the early days of black and white film to the digital age, where images can be instantly captured, edited, and shared online. christmas photos calgary

21
[回复]
Bushra batool 说:
2023年9月24日 19:59

Themes may incorporate features for embedding or linking to game streams, video reviews, trailers, and Let's Play content. game cards templates

22
[回复]
Bushra batool 说:
2023年10月02日 01:53

thanks for this usefull article, waiting for this article like this again. uk49s

23
[回复]
Bushra batool 说:
2023年10月03日 05:20

Thanks for sharing nice information with us. i like your post and all you share with us is uptodate and quite informative, i would like to bookmark the page so i can come here again to read you, as you have done a wonderful job. consultants

24
[回复]
Bushra batool 说:
2023年10月04日 03:31

Nice Informative Blog having nice sharing.. Luxury Rehab

25
[回复]
Bushra batool 说:
2023年10月04日 14:34

I found your this post while searching for some related information on blog search...Its a good post..keep posting and update the information. https://www.shopfrontdesign.co.uk/

26
[回复]
Bushra batool 说:
2023年10月04日 16:20

This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post! container rental near me

27
[回复]
Bushra batool 说:
2023年10月04日 19:57

Most of the time I don’t make comments on websites, but I'd like to say that this article really forced me to do so. Really nice post! https://loftinsulationinstallers.co.uk/

28
[回复]
Bushra batool 说:
2023年10月04日 21:53

Thanks for your information, it was really very helpfull.. director redundancy payment

29
[回复]
Bushra batool 说:
2023年10月09日 01:37

Your website is really cool and this is a great inspiring article. Thank you so much. League Coaching

30
[回复]
asim 说:
2023年10月10日 04:27

I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business. newport residences price

31
[回复]
asim 说:
2023年10月12日 05:03

I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business. KIU

32
[回复]
Bushra batool 说:
2023年10月17日 22:14 Please share more like that. Dapp Development
33
[回复]
Bushra batool 说:
2023年10月21日 02:40

thanks for this usefull article, waiting for this article like this again. Mobile pet grooming Miami

34
[回复]
Bushra batool 说:
2023年10月22日 15:53

Thank you for the update, very nice site.. glow4d login

35
[回复]
Bushra batool 说:
2023年10月24日 15:22

thanks this is good blog. Pet grooming Miami

36
[回复]
Bushra batool 说:
2023年10月24日 18:12 thanks for this usefull article, waiting for this article like this again. bathroom remodeling Chicago
37
[回复]
Bushra batool 说:
2023年10月25日 19:08

thanks for this usefull article, waiting for this article like this again. CBD for cats

38
[回复]
Bushra batool 说:
2023年10月25日 22:15

thanks for this usefull article, waiting for this article like this again. CBD for sleep

39
[回复]
asim 说:
2023年10月25日 22:51

New web site is looking good. Thanks for the great effort. cbd cream

40
[回复]
Bushra batool 说:
2023年10月26日 00:43

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!!! cbd for pain

41
[回复]
Naveed 说:
2023年11月09日 02:06 nice bLog! its interesting. thank you for sharing.... https://industrialpaintingcontractors.co.uk/
42
[回复]
Naveed 说:
2023年11月09日 14:24

Exactly, you're very kind of us about comment!. new building regs cavity wall This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information... new building regs cavity wall

43
[回复]
Naveed 说:
2023年11月09日 18:24

Interesting topic for a blog. I have been searching the Internet for fun and came upon your website. Fabulous post. Thanks a ton for sharing your knowledge! It is great to see that some people still put in an effort into managing their websites. I'll be sure to check back again real soon. what does knotweed look like

44
[回复]
Naveed 说:
2023年11月09日 20:40

This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article. outdoor advertisement

45
[回复]
Naveed 说:
2023年11月12日 00:42

I know your expertise on this. I must say we should have an online discussion on this. Writing only comments will close the discussion straight away! And will restrict the benefits from this information. lift maintenance company

46
[回复]
Naveed 说:
2023年11月12日 13:53

Very useful post. This is my first time i visit here. I found so many interesting stuff in your blog especially its discussion. Really its great article. Keep it up. 5g football pitch

47
[回复]
Naveed 说:
2023年11月12日 14:40

Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place.. https://www.tenniscourtconstruction.org.uk/

48
[回复]
Bushra batool 说:
2023年11月19日 03:56

thanks for this usefull article, waiting for this article like this again. Expert Generator Hire

49
[回复]
Bushra batool 说:
2023年11月19日 16:00

Thank you for taking the time to publish this information very useful! loft insulation fitter

50
[回复]
Bushra batool 说:
2023年11月19日 20:41 Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!THANKS!!!!!! outdoor advertisements
51
[回复]
Bushra batool 说:
2023年11月20日 14:28

Thanks for a wonderful share. Your article has proved your hard work and experience you have got in this field. Brilliant .i love it reading. Sell land in Michigan quickly

52
[回复]
Bushra batool 说:
2023年11月20日 15:48

thank you for a great post. Ohio land liquidation services

53
[回复]
Naveed 说:
2023年11月21日 16:15

I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business. 메이저놀이터

54
[回复]
Naveed 说:
2023年11月23日 00:39

I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post. kontol kuda

55
[回复]
Naveed 说:
2023年11月24日 05:12

These are some great tools that i definitely use for SEO work. This is a great list to use in the future.. situs porno

56
[回复]
Bushra batool 说:
2023年12月05日 00:51

Thank you very much for the sharing! COOL.. website link

57
[回复]
Bushra batool 说:
2023年12月05日 03:23

It was wondering if I could use this write-up on my other website, I will link it back to your website though.Great Thanks. read here

58
[回复]
Bushra batool 说:
2023年12月05日 14:36

I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business. official statement

59
[回复]
Bushra batool 说:
2023年12月06日 03:21

thanks for this usefull article, waiting for this article like this again. center cam webcam

60
[回复]
Bushra batool 说:
2023年12月06日 22:40

thanks this is good blog. gym equipment service

61
[回复]
Bushra batool 说:
2023年12月07日 03:37

Wow what a Great Information about World Day its very nice informative post. thanks for the post. Gym Equipment Removals

62
[回复]
Bushra batool 说:
2023年12月07日 21:05

I am hoping the same best effort from you in the future as well. In fact your creative writing skills has inspired me. treadmill service and repair

63
[回复]
Bushra batool 说:
2023年12月07日 23:06

Great! It sounds good. Thanks for sharing.. Used Gym Equipment

64
[回复]
Naveed 说:
2023年12月08日 00:56

I really appreciate the kind of topics you post here. Thanks for sharing us a great information that is actually helpful. Good day! Commercial Gym Equipment Suppliers

65
[回复]
Naveed 说:
2023年12月08日 01:48

Love to read it,Waiting For More new Update and I Already Read your Recent Post its Great Thanks. new gym cross trainers

66
[回复]
Naveed 说:
2023年12月09日 19:43

I am definitely enjoying your website. You definitely have some great insight and great stories. Selling vacant land in Arizona

67
[回复]
Naveed 说:
2023年12月09日 20:22

Great survey, I'm sure you're getting a great response. Selling land for cash process

68
[回复]
Bushra batool 说:
2023年12月12日 16:44

Thank you for the update, very nice site.. 18 Prosperity Way, Andrews Farm SA 5114

69
[回复]
Bushra batool 说:
2023年12月14日 01:16

This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post! private rehab

70
[回复]
Naveed 说:
2023年12月14日 02:04

Great Information sharing .. I am very happy to read this article .. thanks for giving us go through info.Fantastic nice. I appreciate this post. prime resin flooring

72
[回复]
Naveed 说:
2023年12月15日 00:18

Great Information sharing .. I am very happy to read this article .. thanks for giving us go through info.Fantastic nice. I appreciate this post. Atlantic Jet Partners

73
[回复]
richerson 说:
2023年12月15日 00:56 Great post I would like to thank you for the efforts you have made in writing this interesting and knowledgeable article. USMLE Step 2
74
[回复]
Bushra batool 说:
2023年12月15日 22:35

This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post! HVAC installers

75
[回复]
shaikhseo 说:
2023年12月17日 20:00

Thank you very much for this useful article. I like it. tubidy mp3 download

76
[回复]
shaikhseo 说:
2023年12月18日 17:44

Thank you very much for the sharing! COOL.. gold coast building and pest inspections

77
[回复]
shaikhseo 说:
2023年12月19日 00:51

Thank you very much for this useful article. I like it. Mobile pet grooming Pembroke Pines

78
[回复]
Bushra batool 说:
2023年12月19日 01:02

Thanks for sharing the info, keep up the good work going.... I really enjoyed exploring your site. good resource... โต๊ะทำงานเมลามีน

79
[回复]
Bushra batool 说:
2023年12月23日 21:56

i read a lot of stuff and i found that the way of writing to clearifing that exactly want to say was very good so i am impressed and ilike to come again in future.. THCjD Godis

80
[回复]
Bushra batool 说:
2023年12月27日 18:48

Please share more like that. Atlantic Jet Partners

81
[回复]
sheikhqueen 说:
2023年12月30日 17:11

New web site is looking good. Thanks for the great effort. center screen camera

82
[回复]
asim 说:
2024年1月01日 05:37 Love to read it,Waiting For More new Update and I Already Read your Recent Post its Great Thanks. Geneva To Tignes
83
[回复]
asim 说:
2024年1月02日 05:06 Love to read it,Waiting For More new Update and I Already Read your Recent Post its Great Thanks. adam gant victoria
84
[回复]
shaikseo 说:
2024年1月03日 04:30

Your website is really cool and this is a great inspiring article. Thank you so much. <a href="http://www.hawkeyechapter.org/what-is-the-purpose-of-lodge/">garden office builder near me</a>

85
[回复]
shaikseo 说:
2024年1月03日 04:31

Your website is really cool and this is a great inspiring article. Thank you so much. garden office builder near me

86
[回复]
shaikhseo 说:
2024年1月17日 21:39

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post. Continue reading

87
[回复]
Naveed 说:
2024年1月23日 20:11

The website is looking bit flashy and it catches the visitors eyes. Design is pretty simple and a good user friendly interface. Dothan land clearing technology


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter