面向面试编程-蓄水池算法

前置知识:

  • 数学

面向面试编程-蓄水池算法

题目要求

给定一个极其大的数据流,大到无法存入内存,要求在所有数据中随机选取k个元素。

解法:蓄水池算法

假设读取第i个数据,从1开始计数。如果i小于等于k,则存入蓄水池。如果i大于k,则随机取从1到i之间的随机数m,如果m处于1到k中,那么将i元素替换蓄水池中m元素。
证明
对于蓄水池中的元素,被选中的概率是不被蓄水池外的元素替换掉的概率。即k×(k+1)×…×(N-1)/((k+1)×(k+2)×…×(N)) = k/N。
对于蓄水池外的元素,假设位置i,那么概率为选中的概率乘以不被后面元素替代的概率。即(k/i)×(i/(i+1))×…×((N-1)/N) = k/N。

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×