面試被問(wèn)到的一個(gè)問(wèn)題：從N個(gè)樣本中隨機(jī)抽取m個(gè)樣本帽蝶，要求每個(gè)樣本被抽取的概率一致蓝牲。升級(jí)1：要求精準(zhǔn)抽到m個(gè)巡莹；升級(jí)2：對(duì)每個(gè)樣本添加權(quán)重，要求抽取概率按照權(quán)重分配冰抢。
基礎(chǔ)問(wèn)題
問(wèn)題描述：從N個(gè)樣本中隨機(jī)抽取m個(gè)樣本松嘶，要求每個(gè)樣本被抽取的概率一致，求怎么樣抽瓤嫒拧喘蟆？數(shù)據(jù)量為百萬(wàn)級(jí)。
看到這個(gè)問(wèn)題鼓鲁，最先想到的方法是，依次遍歷每個(gè)樣本港谊，以的概率抽中當(dāng)前樣本作為最后
中的一個(gè)骇吭，具體操作可以是：
1、每遍歷一個(gè)樣本歧寺，生成一個(gè)之間的隨機(jī)數(shù)
燥狰，對(duì)比
和
的大小斜筐；
2龙致、若大于
，說(shuō)明屬于
概率內(nèi)顷链，不抽目代；若
小于等于
，說(shuō)明屬于
概率內(nèi)嗤练，抽它榛了；
3、直到所有樣本遍歷結(jié)束煞抬。
還可以從另一個(gè)角度證明這個(gè)算法的公平性霜大，對(duì)每個(gè)抽中的樣本來(lái)說(shuō)，它應(yīng)該是被抽中的第個(gè)樣本革答，那么它被抽中的概率是：第一次就被抽中的概率+第一次沒(méi)抽中第二次被抽中的概率+...+前
次都沒(méi)抽中最后一次抽中的概率战坤，用式子表示就是：
不考慮調(diào)用隨機(jī)數(shù)生成函數(shù)的耗時(shí)的話(huà)，這樣做還有個(gè)問(wèn)題残拐，那就是最后抽中的數(shù)不一定正好是m個(gè)途茫，因?yàn)橐淮伪闅v只保證了每個(gè)樣本等概率被抽中，沒(méi)法保證抽到的樣本量溪食。這時(shí)又想到慈省，在遍歷過(guò)程中要是抽滿(mǎn)了m個(gè)，就退出循環(huán)停止遍歷，可是當(dāng)遍歷完都沒(méi)有抽滿(mǎn)m個(gè)該怎么辦呢边败？選擇再遍歷一次的話(huà)復(fù)雜度會(huì)很高袱衷，也可能出現(xiàn)遍歷了很多次都沒(méi)抽滿(mǎn)的情況。
升級(jí)問(wèn)題1
問(wèn)題描述：從N個(gè)樣本中隨機(jī)抽取m個(gè)樣本笑窜，要求每個(gè)樣本被抽取的概率一致致燥，而且保證最后正好抽到m個(gè)數(shù)。
其實(shí)不算是升級(jí)問(wèn)題排截，因?yàn)樵谏蟼€(gè)問(wèn)題中其實(shí)已經(jīng)規(guī)定了要抽取m個(gè)嫌蚤，只是因?yàn)閮?yōu)先想到的解法出現(xiàn)了bug，所以不得不再重新思考断傲。
解法1
蓄水池算法可以很好地解決這個(gè)問(wèn)題脱吱，但這里先不介紹它，先介紹另一種同樣能實(shí)現(xiàn)的方式：第個(gè)樣本认罩，被抽中的概率是
箱蝠，
是已經(jīng)抽中的樣本個(gè)數(shù)。
1垦垂、第一個(gè)樣本以概率抽取就好宦搬；
2、若第一個(gè)樣本沒(méi)抽中劫拗，則第二個(gè)樣本抽中概率為间校；若第一個(gè)樣本被抽中了，那么第二個(gè)樣本抽中的概率為
页慷，兩種情況加起來(lái)憔足，第二個(gè)樣本被抽中的概率為
；
3酒繁、后面的樣本依次類(lèi)推四瘫，抽中概率和當(dāng)前樣本序號(hào)和已經(jīng)抽中的樣本數(shù)
有關(guān)，最后可以得到每個(gè)樣本被抽中的概率都是
欲逃。
這個(gè)算法能夠保證每個(gè)樣本被抽到的概率都為找蜜，并且最后抽到的樣本為m個(gè)。關(guān)鍵在于稳析，每遍歷或抽到一個(gè)樣本之后洗做，都要對(duì)接下來(lái)抽取的概率做調(diào)整，當(dāng)抽取的很快時(shí)彰居，概率的分子項(xiàng)會(huì)變小诚纸，后面樣本越來(lái)越難被抽到；當(dāng)抽取的比較慢陈惰，概率分子項(xiàng)會(huì)變大畦徘，后面樣本被抽到的概率也會(huì)變大。而且當(dāng)抽滿(mǎn)m個(gè)之后，后面樣本被抽到的概率就為0了井辆；當(dāng)前面的遍歷一直沒(méi)抽滿(mǎn)值关筒，
中只剩下
個(gè)樣本時(shí)，每個(gè)樣本被抽中的概率變?yōu)?杯缺，所以怎么樣都能滿(mǎn)足條件蒸播。
解法2
接下來(lái)再看蓄水池算法，該算法是針對(duì)從一個(gè)長(zhǎng)度為N的序列中隨機(jī)抽取不重復(fù)的m個(gè)數(shù)萍肆，保證每個(gè)數(shù)被抽取到的概率為這個(gè)問(wèn)題而構(gòu)建的袍榆，算法步驟為：
1、構(gòu)建一個(gè)可放m個(gè)元素的蓄水池塘揣，將序列的前m個(gè)元素放入蓄水池中包雀；
2、從第m+1個(gè)元素開(kāi)始亲铡，以的概率來(lái)決定該元素是否被替換到池子中才写；
3、當(dāng)遍歷完所有元素之后奴愉，蓄水池中的就是隨機(jī)挑選出的m個(gè)元素。
算法偽代碼為：
for i= m+1 to N
k=random(1, i);
if( k < m)
SWAP the kth value and ith value
end for
上述算法的證明：
- 對(duì)于蓄水池中的前m個(gè)樣本铁孵，最開(kāi)始被選中的概率為1锭硼，然后每個(gè)樣本留到最后的概率=（m+1到n的遍歷中，每次替換都抽不到自己的概率）蜕劝，寫(xiě)成公式是
檀头；
- 對(duì)于蓄水池之外的樣本，從第m+1個(gè)開(kāi)始岖沛，設(shè)序號(hào)為j暑始，它們最終能被換到蓄水池中的概率=遍歷到自己的時(shí)候被換進(jìn)去的概率*被換進(jìn)去之后不再被換出來(lái)的概率，寫(xiě)成公式是
因此婴削，不論剛開(kāi)始是在蓄水池內(nèi)還是在外廊镜，最后留在蓄水池內(nèi)的概率都是一樣的，而且這個(gè)算法一定保證了能選出m個(gè)樣本來(lái)唉俗，因?yàn)橐婚_(kāi)始就是基于替換的思路嗤朴。
升級(jí)問(wèn)題2
問(wèn)題描述：從N個(gè)樣本中隨機(jī)抽取m個(gè)樣本，要求每個(gè)樣本被抽取的概率一致虫溜。在此基礎(chǔ)上雹姊，為每個(gè)樣本分配一個(gè)權(quán)重值w，范圍為[1,k]衡楞，表示權(quán)值為k的樣本被抽中的概率是權(quán)值為1的樣本概率的k倍吱雏。
解法很簡(jiǎn)單，在上面解法1的步驟中添加一個(gè)權(quán)重概率就好了：第個(gè)樣本，被抽中的概率是
歧杏，
是已經(jīng)抽中的樣本個(gè)數(shù),
表示第
個(gè)樣本的權(quán)重镰惦。
1、第一個(gè)樣本以概率抽取就好得滤；
2陨献、若第一個(gè)樣本沒(méi)抽中，則第二個(gè)樣本抽中概率為懂更；若第一個(gè)樣本被抽中了眨业，那么第二個(gè)樣本抽中的概率為
，兩種情況加起來(lái)沮协，第二個(gè)樣本被抽中的概率為
龄捡；
3、后面的樣本依次類(lèi)推慷暂，抽中概率和當(dāng)前樣本序號(hào)和已經(jīng)抽中的樣本數(shù)
聘殖，以及當(dāng)前樣本權(quán)重有關(guān)，最后可以得到每個(gè)樣本被抽中的概率都是
行瑞。
在保證每個(gè)樣本等概率被抽中的基礎(chǔ)上奸腺，再加入權(quán)重的影響，就能實(shí)現(xiàn)有概率差別地抽中血久。
但這里有個(gè)問(wèn)題沒(méi)想明白突照，為什么乘上去的權(quán)重概率要除以所有權(quán)重的和，直接乘以當(dāng)前樣本的權(quán)重會(huì)出現(xiàn)什么問(wèn)題氧吐？
參考文章
1讹蘑、https://blog.csdn.net/bitcarmanlee/article/details/83016377
2、https://www.cnblogs.com/ywl925/p/3793003.html
