Read random line from a large text file

Question

I have a file with 5000+ lines. I want to find the most efficient way to choose one of those lines each time I run my program. I had originally intended to use the random method to choose one (that was before I knew there were 5000 lines). Thought that might be inefficient so I thought I'd look at reading the first line, then deleting it from the top and appending it to the bottom. But it seems that I have to read the whole file and create a new file to delete from the top.

What is the most efficient way: the random method or the new file method?

The program will be run every 5 mins and I'm using c# 4.5

Answer 1

In .NET 4.*, it is possible to access a single line of a file directly. For example, to get line X:

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

Full example:

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);

Answer 2

Lets assume file is so large that you cannot afford to fit it into RAM. Then, you would want to use Reservoir Sampling, an algorithm designed to handle picking randomly from lists of unknown, arbitrary length that might not fit into memory:

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;

At a high level, reservoir sampling follows a basic rule: Each further line has a 1/N chance of replacing all previous lines.

This algorithm is slightly unintuitive. At a high level, it works by having line N have a 1/N chance of replacing the currently selected line. Thus, line 1 has a 100% chance of being selected, but a 50% chance of later being replaced by line 2.

I've found understanding this algorithm to be easiest in the form of a proof of correctness. So, a simple proof by induction:

1) Base case: By inspection, the algorithm works if there is 1 line.
2) If the algorithm works for N-1 lines, processing N lines works because:
3) After processing N-1 iterations of an N line file, all N-1 lines are equally likely (probability 1/(N-1)).
4) The next iteration insures that line N has a probability of 1/N (because that's what the algorithm explicitly assigns it, and it is the final iteration), reducing the probability of all previous lines to:

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

If you know how many lines are in the file in advance, this algorithm is more expensive than necessary, as it always reads the entire file.

Answer 3

I assume that the goal is to randomly choose one line from a file of 5000+ lines.

Try this:

1. Get the line count using File.ReadLines(file).Count().
2. Generate a random number, using the line count as an upper limit.
3. Do a lazy read of the file with File.ReadLines(file).
4. Choose a line from this array using the random number.

EDIT: as pointed out, doing File.ReadLines(file).toArray() is pretty inefficient.

Answer 4

Here's a quick implementation of @LucasTrzesniewskis proposed method in the comments to the question:

// 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());
    }
}

I don't have any VS near me at the moment, so this is untested.