随机读取文件中一行数据

喜欢ヅ旅行 2022-09-20 06:04 168阅读 0赞

# 随机读取文件中一行数据 #

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

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

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

证明如下：

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

![SouthEast][]

其中 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 ;
    }

[SouthEast]: /images/20220828/896ea69a9d514195b9d486791f3ce634.png