池中錦鯉的自我修養,聊聊蓄水池算法

面試如泡池,蓄水似人生

起初你滿懷期待跳進大廠池子,以為自己是天選之子,結果發現池子里早擠滿了和你一樣的“錦鯉候選人”。HR的漁網一撒,撈誰全看概率——這不就是蓄水池算法的精髓嗎?

  1. 初入池(i≤k):前k個幸運兒直接進池,像極了校招提前批的“VIP通道”。
  2. 概率博弈(i>k):第k + 1個候選人開始,以k / i的概率被撈,同時池子里隨機一位“前輩”出局。
    • “面完三面等消息?恭喜,你進入了k / N的量子糾纏態。”
  3. 公平玄學:無論你是第100還是第1000號候選人,最終被撈的概率都是k / N——池子越深,緣分越隨機

所以,下次面試官問你“如何公平抽獎”,請優雅地回答:

“簡單,像泡池子一樣,先到的不一定穩,后來的未必涼,一切交給蓄水池的數學之美。”

畢竟,泡池子的終極奧義是:
“池中躺平,等一個伯樂;算法加持,信命不認輸。”


機器持續吐出編號遞增的球(1,2,3…),你有一個容量為k的袋子(k=10),怎么保證機器吐出第N個球時,每個球進入袋子的概率都是k/N?

直接上蓄水池采樣規則:

階段處理邏輯
前k個球直接放入袋子(100%保留)
第k+1個球起對第i個球:
- 以k/i概率決定是否保留
- 若保留,隨機替換袋中一個球

每個球進入袋子的概率都是k / N的證明:

情況1:前k個球(1 ≤ i ≤ k)的保留概率推導

  1. 初始狀態:前k個球直接入袋,保留概率為 1
  2. 處理第k+1個球時
    • k+1個球入袋的概率為 k/(k+1)
    • 若入袋,隨機替換袋中某球的概率為 1/k,即第i號球被淘汰的概率為 (k/(k+1)) × (1/k) = 1/(k+1)
    • 因此,第i號球的保留概率為 1 - 1/(k+1) = k/(k+1)
  3. 處理第k+2個球時
    • k+2個球入袋的概率為 k/(k+2)
    • 淘汰第i號球的概率為 (k/(k+2)) × (1/k) = 1/(k+2)
    • 保留概率為 1 - 1/(k+2) = (k+1)/(k+2)
  4. 遞推至第N個球
    • 每一步的保留概率依次為 k/(k+1), (k+1)/(k+2), …, (N-1)/N
    • 最終保留概率為各步概率的乘積:
      k k + 1 × k + 1 k + 2 × ? × N ? 1 N = k N \frac{k}{k+1} \times \frac{k+1}{k+2} \times \cdots \times \frac{N-1}{N} = \frac{k}{N} k+1k?×k+2k+1?×?×NN?1?=Nk?

情況2:后N-k個球(k < i ≤ N)的保留概率推導

  1. 第i號球入袋時
    • 入袋概率為 k/i
  2. 處理第i+1個球時
    • i+1個球入袋的概率為 k/(i+1)
    • 淘汰第i號球的概率為 (k/(i+1)) × (1/k) = 1/(i+1)
    • 保留概率為 1 - 1/(i+1) = i/(i+1)
  3. 處理第i+2個球時
    • 保留概率為 (i+1)/(i+2)
  4. 遞推至第N個球
    • 每一步的保留概率依次為 i/(i+1), (i+1)/(i+2), …, (N-1)/N
    • 最終保留概率為各步概率的乘積:
      k i × i i + 1 × i + 1 i + 2 × ? × N ? 1 N = k N \frac{k}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times \cdots \times \frac{N-1}{N} = \frac{k}{N} ik?×i+1i?×i+2i+1?×?×NN?1?=Nk?

結論
無論球的編號i在哪個區間(1 ≤ i ≤ N),其最終留在蓄水池中的概率均為 k/N,即實現了等概率采樣。


C++代碼實現(改寫左神Java版本)

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>using namespace std;class Pool {
private:int size;vector<int> bag;public:Pool(int s) : size(s), bag(s) {}// 判斷是否選擇第i號球bool pick(int i) {return rand() % i < size;}// 隨機選擇袋子中的一個位置int where() {return rand() % size;}// 處理新進入的球void enter(int i) {if (i <= size) {bag[i - 1] = i;} else {if (pick(i)) {bag[where()] = i;}}}// 獲取袋子中的球vector<int> getBag() {return bag;}
};int main() {srand(time(NULL)); // 初始化隨機數種子cout << "測試開始" << endl;int n = 41;        // 一共吐出多少球int m = 10;        // 袋子大小多少int testTimes = 10000; // 進行多少次實驗vector<int> cnt(n + 1, 0);for (int k = 0; k < testTimes; k++) {Pool pool(m);for (int i = 1; i <= n; i++) {pool.enter(i);}vector<int> bag = pool.getBag();for (int num : bag) {cnt[num]++;}}cout << "機器吐出到" << n << "號球, " << "袋子大小為" << m << endl;cout << "每個球被選中的概率應該接近" << (double)m / n << endl;cout << "一共測試" << testTimes << "次" << endl;for (int i = 1; i <= n; i++) {cout << i << "被選中次數 : " << cnt[i] << ", 被選中概率 : " << (double)cnt[i] / testTimes << endl;}cout << "測試結束" << endl;return 0;
}    
測試開始
機器吐出到41號球, 袋子大小為10
每個球被選中的概率應該接近0.243902
一共測試10000次
1被選中次數 : 2484, 被選中概率 : 0.2484
2被選中次數 : 2414, 被選中概率 : 0.2414
3被選中次數 : 2445, 被選中概率 : 0.2445
4被選中次數 : 2439, 被選中概率 : 0.2439
5被選中次數 : 2456, 被選中概率 : 0.2456
6被選中次數 : 2434, 被選中概率 : 0.2434
7被選中次數 : 2452, 被選中概率 : 0.2452
8被選中次數 : 2405, 被選中概率 : 0.2405
9被選中次數 : 2385, 被選中概率 : 0.2385
10被選中次數 : 2387, 被選中概率 : 0.2387
11被選中次數 : 2413, 被選中概率 : 0.2413
12被選中次數 : 2463, 被選中概率 : 0.2463
13被選中次數 : 2425, 被選中概率 : 0.2425
14被選中次數 : 2405, 被選中概率 : 0.2405
15被選中次數 : 2463, 被選中概率 : 0.2463
16被選中次數 : 2434, 被選中概率 : 0.2434
17被選中次數 : 2406, 被選中概率 : 0.2406
18被選中次數 : 2456, 被選中概率 : 0.2456
19被選中次數 : 2400, 被選中概率 : 0.24
20被選中次數 : 2467, 被選中概率 : 0.2467
21被選中次數 : 2403, 被選中概率 : 0.2403
22被選中次數 : 2415, 被選中概率 : 0.2415
23被選中次數 : 2432, 被選中概率 : 0.2432
24被選中次數 : 2438, 被選中概率 : 0.2438
25被選中次數 : 2464, 被選中概率 : 0.2464
26被選中次數 : 2514, 被選中概率 : 0.2514
27被選中次數 : 2416, 被選中概率 : 0.2416
28被選中次數 : 2546, 被選中概率 : 0.2546
29被選中次數 : 2440, 被選中概率 : 0.244
30被選中次數 : 2350, 被選中概率 : 0.235
31被選中次數 : 2398, 被選中概率 : 0.2398
32被選中次數 : 2483, 被選中概率 : 0.2483
33被選中次數 : 2405, 被選中概率 : 0.2405
34被選中次數 : 2472, 被選中概率 : 0.2472
35被選中次數 : 2449, 被選中概率 : 0.2449
36被選中次數 : 2431, 被選中概率 : 0.2431
37被選中次數 : 2494, 被選中概率 : 0.2494
38被選中次數 : 2515, 被選中概率 : 0.2515
39被選中次數 : 2507, 被選中概率 : 0.2507
40被選中次數 : 2384, 被選中概率 : 0.2384
41被選中次數 : 2411, 被選中概率 : 0.2411
測試結束

設計抽獎系統,在參與某廠招聘會的學生中,抽取100人送offer

等概率抽取100人,且學生不能重復報名(去重)。維護一個大小為100的蓄水池,只需要判斷學生是否首次報名,并確定是第幾個參與者即可。第i個首次報名的學生,以100 / i概率決定是否入池,若入選則隨機替換池中一人。

? 單服務器輕量級維護
? 規避多節點數據匯總
? 實時性高,無最終計算延遲


蓄水池采樣核心

在數據流持續輸入且總量未知的情況下,用固定容量的容器維護一個等概率樣本集。

典型場景及變種

  1. 判斷條件
    • 數據流式輸入且總量未知;
    • 需要等概率采樣固定數量樣本。
  2. 變種處理
    • 動態容量:將固定k改為動態k(i),概率調整為k(i)/i
    • 分布式:先本地采樣再合并二次采樣,利用分治保證概率正確性。
  • 日志采樣:分布式系統中按1/1000比例抽樣百萬級日志,保留統計特征;
  • 推薦系統冷啟動:維護固定大小的歷史交互樣本,保證新物品等概率曝光;
  • 實時彈幕過濾:從千萬級彈幕中實時抽取固定數量展示;

為什么 MapReduce中要用蓄水池采樣?

MapReduce 是一種處理海量數據的編程模型,核心思想是 “分而治之”,就像一群人分工合作完成大任務。

  • MapReduce 處理的往往是 TB 級甚至 PB 級數據(比如日志、用戶行為數據),直接全量采樣或分析不現實:
    • 全量存儲消耗大量內存和磁盤;
    • 直接處理所有數據會拖慢計算速度。
    • 蓄水池采樣能用固定大小的樣本(比如 1000 條數據)代表整體特征,大幅減少計算量。
  • 如果采樣不均勻(比如總選前 10% 的數據),樣本就會失真,無法反映整體特征。
    • 蓄水池采樣能確保每個數據被選中的概率相等。
    • 即使數據是動態流入的(不知道總量 N),也能保證等概率,這對 MapReduce 處理實時或未知總量的數據很關鍵。
  • MapReduce 的分布式架構適配蓄水池采樣
    • Map 階段:每個節點獨立對本地數據做蓄水池采樣(比如每個節點存 m 條樣本),避免傳輸全量數據,減少網絡開銷;
    • Reduce 階段:合并所有節點的樣本(總共有 M = 節點數 × m 條),再用蓄水池采樣取 m 條作為最終樣本,保證全局等概率。

如何等概率采樣1個元素,但數據量極大且只能遍歷一次?

蓄水池采樣的k=1特例,對第i個元素以1/i概率替換當前選中元素。

若數據以鏈表形式存儲,如何高效實現蓄水池采樣?

遍歷鏈表時,對第i個節點(i從1開始)用k/i概率決定是否加入蓄水池,維護大小為k的數組,替換時隨機選位置,時間復雜度O(n),空間O(m)

帶權重的蓄水池采樣如何實現?

選中概率改為權重之和的比例,元素i權重為w_i,第i步選中概率為w_i/(w?+w?+…+w_i),替換時按權重隨機選擇對象。

注:算法公平,但offer未必,建議多投幾個池子。

參考

[1] 程序員代碼面試指南
[2] 算法講解107【擴展】大廠面試中經常漫聊的有趣算法問題

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/85524.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/85524.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/85524.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Linux應用開發之網絡套接字編程

套接字&#xff08;Socket&#xff09;是計算機網絡數據通信的基本概念和編程接口&#xff0c;允許不同主機上的進程&#xff08;運行中的程序&#xff09;通過網絡進行數據交換。它為應用層軟件提供了發送和接收數據的能力&#xff0c;使得開發者可以在不用深入了解底層網絡細…

小白的進階之路系列之六----人工智能從初步到精通pytorch數據集與數據加載器

本文將介紹以下內容: 數據集與數據加載器 數據遷移 如何建立神經網絡 數據集與數據加載器 處理數據樣本的代碼可能會變得混亂且難以維護;理想情況下,我們希望我們的數據集代碼與模型訓練代碼解耦,以獲得更好的可讀性和模塊化。PyTorch提供了兩個數據原語:torch.utils…

深入理解設計模式之中介者模式

深入理解設計模式之&#xff1a;中介者模式&#xff08;Mediator Pattern&#xff09; 一、什么是中介者模式&#xff1f; 中介者模式&#xff08;Mediator Pattern&#xff09;是一種行為型設計模式。它通過引入一個中介對象&#xff0c;來封裝一組對象之間的交互&#xff0…

基于通義千問的兒童陪伴學習和成長的智能應用架構。

1.整體架構概覽 我們的兒童聊天助手將采用典型的語音交互系統架構,結合大模型能力和外部知識庫: 2. 技術方案分解 2.1. 前端應用/設備 選擇: 移動App(iOS/Android)、Web應用,或者集成到智能音箱/平板等硬件設備中。技術棧: 移動App: React Native / Flutter (跨平臺…

Python Day40

Task&#xff1a; 1.彩色和灰度圖片測試和訓練的規范寫法&#xff1a;封裝在函數中 2.展平操作&#xff1a;除第一個維度batchsize外全部展平 3.dropout操作&#xff1a;訓練階段隨機丟棄神經元&#xff0c;測試階段eval模式關閉dropout 作業&#xff1a;仔細學習下測試和訓練代…

WordPress_suretriggers 權限繞過漏洞復現(CVE-2025-3102)

免責申明: 本文所描述的漏洞及其復現步驟僅供網絡安全研究與教育目的使用。任何人不得將本文提供的信息用于非法目的或未經授權的系統測試。作者不對任何由于使用本文信息而導致的直接或間接損害承擔責任。如涉及侵權,請及時與我們聯系,我們將盡快處理并刪除相關內容。 前…

基于Spring Boot 電商書城平臺系統設計與實現(源碼+文檔+部署講解)

技術范圍&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬蟲、數據可視化、小程序、安卓app、大數據、物聯網、機器學習等設計與開發。 主要內容&#xff1a;免費功能設計、開題報告、任務書、中期檢查PPT、系統功能實現、代碼編寫、論文編寫和輔導、論文…

LeetCode 39.組合總和:回溯法與剪枝優化的完美結合

一、問題本質與形式化定義 1.1 題目形式化描述 輸入&#xff1a;無重復整數數組candidates、目標值target輸出&#xff1a;所有和為target的組合集合&#xff0c;滿足&#xff1a; 元素可重復使用組合內元素非降序&#xff08;避免重復解&#xff09;解集無重復組合 1.2 問…

windows11安裝編譯QtMvvm

windows11安裝編譯QtMvvm 1 從github下載代碼2 官方的Download/Installtion3 自行構建編譯QtMvvm遇到的問題3.1 `qmake`問題執行命令報錯原因分析qmake報錯:找不到編譯器 cl解決方案3.2 `make qmake_all`問題執行命令報錯原因分析make命令未識別解決方案3.3 缺少`perl`問題執行…

unix/linux source 命令,其歷史爭議、兼容性、生態、未來展望

現在把目光投向unix/linux source命令的歷史爭議、兼容性、生態和未來展望,這能讓我們更全面地理解一個技術點在更廣闊的圖景中所處的位置。 一、歷史爭議與設計權衡 雖然 source (或 .) 命令功能強大且不可或缺,但在其發展和使用過程中,也存在一些微妙的爭議或設計上的權衡…

開發時如何通過Service暴露應用?ClusterIP、NodePort和LoadBalancer類型的使用場景分別是什么?

一、Service核心概念 Service通過標簽選擇器&#xff08;Label Selector&#xff09;關聯Pod&#xff0c;為動態變化的Pod集合提供穩定的虛擬IP和DNS名稱&#xff0c;主要解決&#xff1a; 服務發現負載均衡流量路由 二、Service類型詳解 1. ClusterIP&#xff08;默認類型…

從線性代數到線性回歸——機器學習視角

真正不懂數學就能理解機器學習其實是個神話。我認為&#xff0c;AI 在商業世界可以不懂數學甚至不懂編程也能應用&#xff0c;但對于技術人員來說&#xff0c;一些基礎數學是必須的。本文收集了我認為理解學習本質所必需的數學基礎&#xff0c;至少在概念層面要掌握。畢竟&…

華為IP(7)

端口隔離技術 產生的背景 1.以太交換網絡中為了實現報文之間的二層隔離&#xff0c;用戶通常將不同的端口加入不同的VLAN&#xff0c;實現二層廣播域的隔離。 2.大型網絡中&#xff0c;業務需求種類繁多&#xff0c;只通過VLAN實現二層隔離&#xff0c;會浪費有限的VLAN資源…

Docker Desktop無法在windows低版本進行安裝

問題描述 因工作需要&#xff0c;現在一臺低版本的window系統進行Docker Desktop的安裝&#xff0c;但是安裝過程當中出現了報錯信息 系統版本配置 原因分析&#xff1a; 關于本機查看了系統的版本號&#xff0c;版本號如下為1909,但是docker Desktop要求的最低的win10版本…

深入理解 Maven 循環依賴問題及其解決方案

在 Java 開發領域&#xff0c;Maven 作為主流構建工具極大簡化了依賴管理和項目構建。然而**循環依賴&#xff08;circular dependency&#xff09;**問題仍是常見挑戰&#xff0c;輕則導致構建失敗&#xff0c;重則引發類加載異常和系統架構混亂。 本文將從根源分析循環依賴的…

Git 全平臺安裝指南:從 Linux 到 Windows 的詳細教程

目錄 一、Git 簡介 二、Linux 系統安裝指南 1、CentOS/RHEL 系統安裝 2、Ubuntu/Debian 系統安裝 3、Windows 系統安裝 四、安裝后配置&#xff08;后面會詳細講解&#xff0c;現在了解即可&#xff09; 五、視頻教程參考 一、Git 簡介 Git 是一個開源的分布式版本控制系…

微服務-Sentinel

目錄 背景 Sentinel使用 Sentinel控制臺 Sentinel控制規則 Sentinel整合OpenFeign 背景 在微服務項目架構中&#xff0c;存在多個服務相互調用場景&#xff0c;在某些情況下某個微服務不可用時&#xff0c;上游調用者若一直等待&#xff0c;會產生資源的消耗&#xff0c;極端情…

智慧零工平臺前端開發實戰:從uni-app到跨平臺應用

智慧零工平臺前端開發實戰:從uni-app到跨平臺應用 本文將詳細介紹我如何使用uni-app框架開發一個支持微信小程序和H5的零工平臺前端應用,包含技術選型、架構設計、核心功能實現及部署經驗。 前言 在當今移動互聯網時代,跨平臺開發已成為提高開發效率的重要手段。本次我選擇…

Qt實現csv文件按行讀取的方式

Qt實現csv文件按行讀取的方式 場景:我有一個保存數據的csv文件,文件內保存的是按照行保存的數據,每行數據是以逗號為分隔符分割的文本數據。如下圖所示: 現在,我需要按行把這些數據讀取出來。 一、使用QTextStream文本流的方式讀取 #include <QFile>void readfil…

day17 leetcode-hot100-34(鏈表13)

23. 合并 K 個升序鏈表 - 力扣&#xff08;LeetCode&#xff09; 1.數組排序 思路 &#xff08;1&#xff09;將全部的節點存儲到數組中 &#xff08;2&#xff09;對數組進行排序 &#xff08;3&#xff09;最后創建一個全新的鏈表 具體代碼 /*** Definition for singly…