資訊專欄INFORMATION COLUMN
摘要：最近發(fā)現(xiàn)兩個(gè)比較有意思的隨機(jī)抽樣算法，分享一下隨機(jī)抽樣且保持有序需求一家公司購(gòu)買了他們的第一批電腦，該公司的業(yè)務(wù)主要是民意調(diào)查，現(xiàn)在要開發(fā)一個(gè)程序程序的輸入是選區(qū)名列表以及整數(shù)，輸出是隨機(jī)選擇的個(gè)選區(qū)名列表。
最近發(fā)現(xiàn)兩個(gè)比較有意思的隨機(jī)抽樣算法，分享一下
1. 隨機(jī)抽樣且保持有序需求:
一家公司購(gòu)買了他們的第一批電腦，該公司的業(yè)務(wù)主要是民意調(diào)查，現(xiàn)在要開發(fā)一個(gè)程序：程序的輸入是選區(qū)名列表以及整數(shù) m，輸出是隨機(jī)選擇的 m 個(gè)選區(qū)名列表。通常選區(qū)名有幾百個(gè)，m 通常在 20 ~ 40。
程序描述:
程序的輸入包含兩個(gè)整數(shù) m 和 n，其中 m簡(jiǎn)單點(diǎn)來(lái)說(shuō)，就是有 n 個(gè)數(shù)， 隨機(jī)取 m 個(gè)，并保持有序。
解法:
我們知道了 n 和 m，輪流判斷 n 個(gè)數(shù)組成的列表中每個(gè)數(shù)的概率(m/n)，每次判斷后n=n-1，若當(dāng)前被判斷的數(shù)被選擇，則m=m-1，否則 m 不變。
假設(shè) 5 個(gè)數(shù)選 2 個(gè)，那么意味著每個(gè)數(shù)的概率都是 2/5 。我們以 2/5 的概率去判斷第 1 個(gè)數(shù)，那么結(jié)果有兩種，選擇1，不選擇。當(dāng)判斷第 2 個(gè)的時(shí)候，在以選擇了第 1 個(gè)數(shù)的情況下，選擇 2 的概率是 (2-1)/(5-1)=1/4，在以沒(méi)選擇第 1 個(gè)數(shù)的情況下，選中 2 的概率是 2/(5-1)=2/4，所以第二個(gè)數(shù)的概率：(2/5)*(1/4) + (3/5)*(2/4) = 2/5。第二個(gè)數(shù)的概率和第一個(gè)數(shù)的概率相等。
證明:
實(shí)現(xiàn):
# Python import random # 抽樣，從n個(gè)中抽m個(gè) def sampling(lists, m, n=None): selected = [] if n is None: n = len(lists) remaining = n-1 for i in range(n): # random.random()返回 0 ~ 1的隨機(jī)數(shù) if random.random() * remaining < m: selected.append(lists[i]) m -= 1 remaining -= 1 return selected # test lists = [i for i in range(10)] print sampling(lists, 3) # 結(jié)果 >>>[4, 5, 7]2. 在不知道總數(shù)的情況下隨機(jī)選一個(gè)如何從 n 個(gè)對(duì)象（可以依次看到這 n 個(gè)對(duì)象，但事先不知道 n 的值）中隨機(jī)選取一個(gè)？例如，如何在事先不知道文本行數(shù)的情況下讀取該文件，從中隨機(jī)選擇并輸出一行？解法:
我們先設(shè)一個(gè)變量叫selected，選擇第 1 行賦值給 selected，并以 1/2 的概率選擇第 2 行并重新賦值給selected， 以 1/3 的概率選擇第 3 行并重新賦值給selected。在這以過(guò)程結(jié)束時(shí)， 每一行的選中概率都是相等的（都是 1/n， 其中 n 是文件的總行數(shù)）
要證明這個(gè)概率可以從最后一行算起,設(shè)最后一行的概率為P(n)=1/n, 倒數(shù)第二行的概率為P(n-1)=(1-P(n))*(1/(n-1)) = 1/n,倒數(shù)第m-1行概率為：
代碼：
# Python import random def getRandLine(text): i = 1 selected = "" for line in text.splitlines(): if (random.random() < (1.0/i)): selected = line i += 1 return selected # test text = """ line1 line2 line3 line4 line5 line6 line7 line8 line9 line10 """ print getRandLine(text) # 結(jié)果 >>>line9參考: 編程珠璣
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/42828.html
摘要：輸出的結(jié)果如下上面輸出了每個(gè)數(shù)字被取樣到的次數(shù)，通過(guò)圖表可以清晰的看到分布情況可以看出蓄水池算法對(duì)于隨機(jī)抽樣還是非常適合的，每個(gè)元素的抽樣概率都相同。 showImg(https://segmentfault.com/img/remote/1460000015901186); 現(xiàn)在有一組數(shù)，不知道這組數(shù)的總量有多少，請(qǐng)描述一種算法能夠在這組數(shù)據(jù)中隨機(jī)抽取k個(gè)數(shù)，使得每個(gè)數(shù)被取出來(lái)的概率...
摘要：相反，這些數(shù)來(lái)源于統(tǒng)計(jì)抽樣，統(tǒng)計(jì)抽樣通過(guò)抽樣小部分群體來(lái)獲得更大群體的特征。但調(diào)查機(jī)構(gòu)的報(bào)告與統(tǒng)計(jì)也經(jīng)常帶有所謂的置信區(qū)間，也稱為偏差。在進(jìn)行一個(gè)多變量測(cè)試時(shí)，消息推送的目標(biāo)是測(cè)試全體，但是同一細(xì)分中的其他用戶不會(huì)收到該條消息。 摘要：Appboy 正在過(guò)手機(jī)等新興渠道嘗試一種新的方法，讓機(jī)構(gòu)可以與顧客建立更好的關(guān)系，可以說(shuō)是市場(chǎng)自動(dòng)化產(chǎn)業(yè)的一個(gè)前沿探索者。在移動(dòng)端探索上，該公司已經(jīng)取...
摘要：在每一層學(xué)習(xí)到的結(jié)果表示作為下一層的輸入用監(jiān)督訓(xùn)練來(lái)調(diào)整所有層加上一個(gè)或者更多的用于產(chǎn)生預(yù)測(cè)的附加層當(dāng)前，國(guó)外在這方面的研究就是三分天下的局面，的與微軟合作，的和合作，以及的計(jì)算機(jī)科學(xué)家和。深度學(xué)習(xí)的入門材料。 轉(zhuǎn)載自：http://doctorimage.cn/2013/01/04/%e5%85%b3%e4%ba%8e%e6%b7%b1%e5%ba%a6%e5%ad%a6%e4%b9%a0...
閱讀 2305·2021-09-30 09:47
閱讀 2223·2021-09-26 09:55
閱讀 2954·2021-09-24 10:27
閱讀 1543·2019-08-27 10:54
閱讀 971·2019-08-26 13:40
閱讀 2499·2019-08-26 13:24
閱讀 2423·2019-08-26 13:22
閱讀 1735·2019-08-23 18:38
