大文件随机取K行[2013网易笔试]

1.给定一个巨大的文件（无法全部放入内存），如何从中选出k行，随处输出k行到文件中。
要求每一行出现的概率都相等。设计算法、说明思路，算法复杂度。

8 个解决方案

#1

假设一共有n行，用ai=0表示第i行没选，ai=1表示第i行选中，所以我们要求的就是序列a(n,k) = [a1,a2....,an]。

取[0, 1)的随机数R, 则a(n,k) = [0, a(n-1, k)] (如果 R>k/n) 或者 a(n,k) = [1, a(n-1, k-1)] (如果 R<=k/n)，由这个递推式就可以求出a1到an，边界条件是k=0，那么剩下的元素全为0，或者n=k，那么剩下的元素全为1。算法时间复杂度为O(n)

这个数学证明貌似难度比较高，搞不定

#2

设文件大小=f

v = random(0, f)  随机一个位置
l = getline(v)    获取这个包含位置的一行数据
n = strlne(l)     获取这一行数据的长度

然后就可以归结为 几率与长度成反比的问题, 
几率要完全相同要获取行的平均长度k

再取随机数m
m*n/k 大于定制就输出, 否则重新选取

#3

感谢楼上两位，好像都没体现文件是巨大文件的特性

#4

编程珠玑里面的例子

#5

可否先遍历一次文件，记录下每一行的起始位置。

然后再根据随机的算法从中取出k个值，去文件中读取对应的行。

#6

蓄水池抽样 公式很容易推导

先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n

#7

引用 3 楼  的回复:

感谢楼上两位，好像都没体现文件是巨大文件的特性

每次只读取一行，选中了就输出，没选中就跳过，所以占用的内存也就是每行长度的最大值
而且只需要从头到尾扫描一遍文件，这是最低开销了。当然如果事先不知道n，那就要扫描两遍

#8

引用 6 楼  的回复:

蓄水池抽样 公式很容易推导

先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n

这个方法适合数据流，也就是无法事先知道n的大小的情况，但是如果k很大，比如k > 2^32，内存会爆的