摘要:輸出的結果如下上面輸出了每個數字被取樣到的次數,通過圖表可以清晰的看到分布情況可以看出蓄水池算法對于隨機抽樣還是非常適合的,每個元素的抽樣概率都相同。
現在有一組數,不知道這組數的總量有多少,請描述一種算法能夠在這組數據中隨機抽取k個數,使得每個數被取出來的概率相等。
如果這組數有n個,那么每個數字取到的概率就是k/n,但是這個問題的難點在于不知道這組數的總數,也就是不知道n,那么該怎么計算每個數取到的概率呢?
蓄水池算法游泳池(蓄水池)大家都不陌生,有些游泳池中的水是活的,有入水管也有出水管,那么和泳池體積相當的水流過之后,是不是泳池中所有的水都會被替換呢?當然不是,有的水在泳池中可能會存留很久,有的可能剛進去就流走了。仿照這種現象,蓄水池抽樣算法誕生了,蓄水池算法的關鍵在于保證流入蓄水池的水和已經在池中的水以相同的概率留存在蓄水池中。并且蓄水池算法可以在不預先知道總量的情況下,在時間復雜度O(N)的情況下,來解決這類采樣問題。
核心原理這一部分涉及公式,為了保證效果直接貼了圖過來。
Python實現接下來嘗試用Python實現一下蓄水池算法,由于蓄水池算法是在事先不知道總量的情況下抽樣的,所以定義一個方法來接收單個元素,并且把這個方法放在類中,以持有采樣后的數據。
import random class ReservoirSample(object): def __init__(self, size): self._size = size self._counter = 0 self._sample = [] def feed(self, item): self._counter += 1 # 第i個元素(i <= k),直接進入池中 if len(self._sample) < self._size: self._sample.append(item) return self._sample # 第i個元素(i > k),以k / i的概率進入池中 rand_int = random.randint(1, self._counter) if rand_int <= self._size: self._sample[rand_int - 1] = item return self._sample測試代碼
接下來實現一個測試用例驗證實現的算法是否正確,既然是隨機抽樣,無法通過單詞測試來驗證是否正確,所以通過多次執行的方式來驗證,比如從1-10里隨機取樣3個數,然后執行10000次取樣,如果算法正確,最后結果中1-10被取樣的次數應該是相同的,都是3000上下。
import unittest from collections import Counter from reservoir_sample import ReservoirSample class TestMain(unittest.TestCase): def test_reservoir_sample(self): samples = [] for i in range(10000): sample = [] rs = ReservoirSample(3) for item in range(1, 11): sample = rs.feed(item) samples.extend(sample) r = Counter(samples) print(r) if __name__ == "__main__": unittest.main()
輸出的結果如下
Counter({7: 3084, 6: 3042, 10: 3033, 3: 3020, 8: 3016, 5: 2997, 4: 2986, 2: 2972, 9: 2932, 1: 2918})
上面輸出了每個數字被取樣到的次數,通過圖表可以清晰的看到分布情況
可以看出蓄水池算法對于隨機抽樣還是非常適合的,每個元素的抽樣概率都相同。
代碼上述的算法和測試代碼已經放在Github,可以直接下載使用。
關注公眾號【Python私房菜】文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/42134.html
摘要:題目要求要求從單鏈表中,隨機返回一個節點的值,要求每個節點被選中的概率是相等的。假如一共有個物品,需要從其中挑選出個物品,要求確保個物品中每個物品都能夠被等概率選中。對于這種等概率問題,簡答的做法是通過隨機數獲取選中物品的下標。 題目要求 Given a singly linked list, return a random nodes value from the linked li...
閱讀 3152·2021-11-04 16:09
閱讀 3107·2021-09-23 11:49
閱讀 3603·2021-09-09 09:33
閱讀 3605·2021-08-18 10:22
閱讀 2041·2019-08-30 15:55
閱讀 3625·2019-08-30 15:53
閱讀 2653·2019-08-28 18:08
閱讀 888·2019-08-26 18:18