Efficiently choosing a random line from a text file with uniform probability in C?

Question

This is essentially a more constrained version of this question.

Suppose we have a very large text file, containing a large number of lines.

We need to choose a line at random from the file, with uniform probability, but there are constraints:

• Because this is a soft realtime application, we cannot iterate over the entire file. The choice should take a constant-ish amount of time.
• Because of memory constraints, the file cannot be cached.
• Because the file is permitted to change at runtime, the length of the file cannot be assumed to be a constant.

My first thought is to use an lstat() call to get the total filesize in bytes. fseek() can then be used to directly access a random byte offset, getting something like O(1) access into a random part of the file.

The problem is that we can't then do something like read to the next newline and call it a day, because that would produce a distribution biased toward long lines.

My first thought at solving this issue is to read until the first "n" newlines (wrapping back to the file's beginning if required), and then choose a line with uniform probability from this smaller set. It is safe to assume the file's contents are randomly ordered, so this sub-sample should be uniform with respect to length, and, since its starting point was selected uniformly from all possible points, it should represent a uniform choice from the file as a whole. So, in pseudo-C, our algorithm looks something like:

 lstat(filepath, &filestat);
 fseek(file, (int)(filestat.off_t*drand48()), SEEK_SET);
 char sample[n][BUFSIZ];
 for(int i=0;i<n;i++)
     fgets(sample[i], BUFSIZ, file); //plus some stuff to deal with file wrap around...
 return sample[(int)(n*drand48())];

This doesn't seem like an especially elegant solution, and I'm not completely confident it will be uniform, so I'm wondering if there's a better way to do it. Any thoughts?

EDIT: On further consideration, I'm now pretty sure that my method is not uniform, since the starting point is more likely to be inside longer words, and thus is not uniform. Tricky!

Answer 1

Select a random character from the file (via rand and seek as you noted). Now, instead of finding the associated newline, since that is biased as you noted, I would apply the following algorithm:

Is the character a newline character?
   yes - use the preceeding line
   no  - try again

I can't see how this could give anything but a uniform distribution of lines. The efficiency depends on the average length of a line. If your file has relatively short lines, this could be workable, though if the file really can't be precached even by the OS, you might pay a heavy price in physical disk seeks.

Answer 2

Solution was found, which works surprisingly well. Documenting here for myself and others.

This example code does around 80,000 draws per second in practice, with a mean line length that matches that of the file to 4 significant digits on most runs. In contrast, I get around 250 draws per second using the method from the cross referenced question.

Essentially what it does is sample a random place in the file, and then discard it and draw again with probability inversely proportionate to the line length. This cancels out the bias for longer words. On average, the method makes a number of draws equal to the average line length in the file before accepting one.

Some notable drawbacks:

• Files with longer line lengths will produce more rejections per draw, making this much slower.

• Files with longer line lengths require a larger constant than 50 in the rdraw function, which appears to mean much longer seek times in practice if line lengths exhibit high variance. For instance, setting it to BUFSIZ on one file I tested with reduced draw speeds to around 10000 draws per second. Still much faster than counting lines in the file though.

  int rdraw(FILE* where, char *storage, size_t bytes){
      int offset = (int)(bytes*drand48());
      int initial_seek = offset>50?offset-50:0;
      fseek(where, initial_seek, SEEK_SET);
      int chars_read = 0;
      while(chars_read + initial_seek < offset){
              fgets(storage,50,where);
              chars_read += strlen(storage);
      }
      return strlen(storage);
  }
  
  int main(){
      srand48(time(NULL));
      struct stat blah;
      stat("/usr/share/dict/words", &blah);
      FILE *where = fopen("/usr/share/dict/words", "r");
      off_t bytes = blah.st_size;
      char b[BUFSIZ+1];
  
      int i;
      for(i=0;i<1000000; i++){
              while(drand48() > 1.0/(rdraw(where, b, bytes)));
      }
  
  }