从大型文本文件中读取随机行

本文关键字：读取 随机 文件 大型 文本 | 更新日期: 2023-09-27 18:10:36

我有一个5000多行的文件。我想找到每次运行程序时选择其中一行的最有效方法。我最初打算使用随机方法来选择一个(那是在我知道有5000行之前)。我觉得这样可能效率不高，所以我想我应该先读第一行，然后把它从顶部删除，然后把它附加到底部。但是，我似乎必须读取整个文件，并创建一个新文件从顶部删除。

什么是最有效的方法:随机方法还是新文件方法?

程序将每5分钟运行一次，我使用c# 4.5

从大型文本文件中读取随机行

在。net 4。*，可以直接访问文件中的一行。例如，要获取行X:

string line = File.ReadLines(FileName).Skip(X).First();

完整的示例:

var fileName = @"C:'text.txt"
var file = File.ReadLines(fileName).ToList();
int count = file.Count();
Random rnd = new Random();
int skip = rnd.Next(0, count);
string line = file.Skip(skip).First();
Console.WriteLine(line);

假设文件太大，您无法将其放入RAM中。然后，你可能想要使用水库采样，这是一种算法，旨在处理从未知的任意长度的列表中随机选择，这些列表可能不适合内存:

Random r = new Random();
int currentLine = 1;
string pick = null;
foreach (string line in File.ReadLines(filename)) 
{
    if (r.Next(currentLine) == 0) {
        pick = line;
    }
    ++currentLine;
}   
return pick;

在高水平上，储层采样遵循一个基本规则:每条进一步的线有1/N的机会取代所有之前的线。

这个算法有点不直观。在高层次上，它的工作原理是让行N有1/N的机会替换当前选择的行。因此，第一行有100%的机会被选中，但有50%的机会稍后被第2行取代。

我发现以正确性证明的形式来理解这个算法是最简单的。一个简单的归纳法证明:

1)基本情况:通过检查，如果有1行，算法有效。
2)如果算法对N-1行有效，则处理N行有效，因为:
3)在处理N行文件的N-1次迭代后，所有N-1行都是等可能的(概率为1/(N-1))。
4)下一次迭代确保第N行具有1/N的概率(因为这是算法显式分配给它的，并且是最后一次迭代)，将前面所有行的概率降低到:

1/(N-1) * (1-(1/N))  
1/(N-1) * (N/N-(1/N))  
1/(N-1) * (N-1)/N  
(1*(N-1)) / (N*(N-1))  
1/N

如果您提前知道文件中有多少行，则该算法的开销比必要的要大，因为它总是读取整个文件。

我假设目标是从5000多行文件中随机选择一行。

试试这个:

  1. 使用file . readlines (file). count()获取行数。
  2. 生成随机数，以行数为上限。
  3. 使用file . readlines (file)惰性读取文件。
  4. 使用随机数从数组中选择一行。

编辑:正如所指出的，执行file . readlines (file). toarray()是非常低效的。

下面是@LucasTrzesniewskis在对问题的评论中提出的方法的快速实现:

// open the file
using(FileStream stream = File.OpenRead("yourfile.dat"))
{
    // 1. index all offsets that are the beginning of a line
    List<Long> lineOffsets = new List<Long>();
    lineOffsets.Add(stream.Position); //the very first offset is a beginning of a line!
    int ch;
    while((ch = stream.ReadByte()) != -1) // "-1" denotes the end of the file
    {
        if(ch == ''n')
            lineOffsets.Add(stream.Position);
    }
    // 2. read a random line
    stream.Seek(0, SeekOrigin.Begin); // go back to the beginning of the file
    // set the position of the stream to one the previously saved offsets
    stream.Position = lineOffsets[new Random().Next(lineOffsets.Count)];
    // read the whole line from the specified offset
    using(StreamReader reader = new StreamReader(stream))
    {
        Console.WriteLine(reader.ReadLine());
    }
}

目前我附近没有任何VS，所以这是未经测试的

相关文章：