随机读取文件中一行数据

问题描述：对于一个事先不知道有多少行的文件，设计一种算法，能够快速地随机读取文件中的一行数据。

思路1：先统计文件又多少行数据，假设共有N行。然后根据k = rand()%N得到选择的行，再从文件头开始，逐行读取，一直到第k行，作为随机读取的一行数据。这种思路简单直白，但是效率不高。

思路2：只读取一遍文件，就能以相同的概率选出文件中的一行数据。具体做法是使用一个变量lineData以概率1/k来记录第k行的内容，这样就能保证lineData中最终保存文件中每一行的概率都是相同的。

证明如下：

假设文件共有N行，那么对于文件中的任意第i行数据，被选中的概率是：

其中 1/i 表示会以的概率将lineData中的数据替换成为地i行的数据；i/(i+1) 表示读取到第i+1行的时候会以的概率保留lineData中的值；后面的各个分式含义相同。

至此，思路2能够以O(N)的复杂的从文件中随机读取一行数据，而思路1的平均复杂度是O(1.5N)，最坏复杂度是O(2N)。因此思路2更好些。

代码如下：

#include <iostream>
#include <fstream>
#include <ctime>
#include <string>
using namespace std;

string getRandLine(const string& fileName )
{
	ifstream inf(fileName.c_str()) ;
	string lineData ;
	int i = 1 ;
	string tmpLine ;
	srand((unsigned int)time(NULL)) ;
	while (getline(inf, tmpLine))
	{
		if (rand()%i == 0)
			lineData = tmpLine ;
		++ i ;
	}
	inf.close() ;
	return lineData ;
}


int main(int argc, char** argv)
{
	cout << getRandLine("data.txt") << endl ;
	return 0 ;
}