猫和桃子去吃回转寿司。桃子让猫从转盘上随机取下k个碟子。猫应该怎么做?
已知:
1、猫和桃子坐在最上游的位置,从厨房伸出来的传送带会在第一时间把厨师做好的寿司送到他们面前。
2、从猫眼前经过的寿司如果不被猫取下来,则会被坐在下家的兔子们吃光,而不会再转回来。(每个寿司只经过一次)
3、桌子上只能容纳下k个碟子。
4、如果取下的寿司没有被吃过,可以被重新放回去。
5、虽然厨师已经停止生产新的寿司了,但是传送带在厨房里的部分很长,猫不知道已经生产了多少寿司。(为了讨论方便,设一共N碟寿司,并且N≥k)
6、猫脑袋可以生成随机数。
Ok,以上表述纯粹是好玩。实际上是做这样一件事情:
从包含N个项目的集合S中随机选取k个样本,其中N为一很大、未知的数量,以至于不能把所有N个项目都存放到主内存。要求只对N遍历一次。
Jeffrey Scott Vitter在其论文[1]中提出了该问题并给出了一个精妙的算法:
1、把桌子清空,留出编号为1~k的k个位置存放寿司。
2、把前k个(第1~k个)寿司分别放在1~k号位置。
3、当第j个寿司经过面前时(k+1≤j≤N),猫脑袋生成一个1~j之间的随机整数r。
4、若r≤k,则把桌子上r号位置的寿司替换为当前(第j个)寿司;否则不操作。
5、如此(3、4步骤)直至所有寿司在猫面前经过。
这个算法的规范描述及其证明[2][3]并不复杂。我们可以计算传送带上第i个寿司最终被选取的概率P(i),说明P(i)=k/N,从而证明该算法:
如果i≤k,则一开始它就被放在了桌子上,对它产生“威胁”的寿司是第k+1~N个寿司。第j(k+1≤j≤N)个寿司把它替换掉的概率为1/j,即“安全”的概率为(j-1)/j。由概率基本常识我们知道:P(i)=[k/(k+1)]×[(k+1)/(k+2)]×...×[(N-1)/N]=k/N。
对于i>k的情形,有兴趣的读者可以自己完成这部分证明。
这个算法的精妙之处在于它的时间复杂度是O(N),空间复杂度是O(k)。
果壳网[4]上给出了这个问题的一个没有太大意义的答案,有兴趣的读者可以去看看。
相关推荐
开源项目-miku-rsampling.zip,Simple reservoir sampling for the command line.
MULTIGRID METHOD FOR RESERVOIR SIMULATION
reservoir engineering modelling opportunities
Android Reservoir存取本地数据
这是一个关于双重介质试井的小程序。welltest是主程序,其他是子程序。fun和fun1分别是压力计算函数和压力导数计算函数。计算过程中可以改变不同参数的取值,绘制图形,研究各参数对压力响应的敏感性。...
Reservoir connectivity evaluation based on the reservoir architecture,尹太举,张昌民,Reservoir connection is a key factor for water flooding recovery. Ways for connection evaluation is though well ...
Simulation platform for pattern recognition based on reservoir computing with memristor networks_基于忆阻网络储层计算的模式识别仿真平台.pdf
libraryDependencies += "lgbt.princess" %% "reservoir-core" % "0.4.0" // the core library supporting synchronous reservoir sampling libraryDependencies += "lgbt.princess" %% "reservoir-akka-stream" % ...
很基础的一本油藏数值模拟教材,感兴趣的可以好好看看
学习建模的好教程,欢迎大家下载!
Application of FPGA to Real‐Time Machine Learning Hardware Reservoir Computers and Software Image Processing 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国...
Good book about engineering
os-fast-reservoir 快速近似水库采样的Python实现。 安装 $ pip install os-fast-reservoir 用法 原料药 from os_fast_reservoir import ReservoirSampling rs = ReservoirSampling(100) for i in range(1000):...
Application of FPGA to Real‐Time Machine Learning Hardware Reservoir Computers and Software Image Processing 英文无水印原版pdf pdf所有页面使用FoxitReader、PDF-XChangeViewer、SumatraPDF和Firefox测试...
Seismic low-frequency effects from fluid-saturated reservoir
使用matlab隐式求解油藏中压力分布,油井产量,网格分布已给定。
Matlab reservoir toolbox, it analyses the data and plot the corresponding figures.
用粒子群算法求解单一水库优化调度,只需要修改相应的约束条件就可以进行优化计算了(With a single particle swarm algorithm is optimizing reservoir operation, only need to modify the corresponding ...
Estimating The Sediment Deposit Volume in Khashm Elgirba Reservoir – Sudan,Ahmed Mohammed Osman,anwar adam,Khashm Elgirba reservoir is located in the upper of Atbara River, which carries the ...