0

Input:

  • potentially large file with text lines
  • lines count is unknown, naive assumption gives range maybe more than 100K lines, but less than 400K
  • it's unknown if lines are sorted or not
  • it's fine to keep in memory at most 10.000 lines

Limitations:

  • read lines one by one, there is no possibility to read file at once into memory.
  • read file once and sample lines at the same time, it's way too long to read all lines first to get lines count.

Goal:

Sample the minimum count of lines from file to get maximum variance

Example: Here is the file:

1,Tom,22,3000000
3,Bob,34,4000000
...
10,Tim,18,500000.05

Lines are ordered, I expect to sample

1,Tom,22,3000000
10,Tim,18,500000.05

Solution: Does it make sense? - read line by line - keep tail buffer for the recent 1000 lines - keep sample buffer for 9000 lines - add every line with index XXX (what is the right formula here?) to sample buffer - union sample buffer and tail buffer once end of file reached.

Capacytron
  • 113

1 Answers1

2

This sounds like the classic Reservoir Sampling use case. Reservoir sampling is a well studied family of algorithms addressing this problem. In reservoir sampling only the size of the resulting sample is kept in memory, not the entire input file.

The only difference in the problem statement from the classic algorithm is that it sounds like the intent is to preserve the input order. This can be done by saving the line number for each record and sorting prior to writing out the sample.

GNU Shuf is a popular and widely available implementation. It does not support retaining the original line order though. tsv-sample is an open-source program similar to GNU Shuf. It does support the preserving input order (disclaimer: I'm the author).

JonDeg
  • 136
  • that it sounds like the intent is to preserve the input order - seems like poor explanation. It' a caveat, if lines are ordered, than I can't just take first records for sampling. Sample will be skewed since first lines will be similar due to sorting. I don't know in advance if lines are sorted or not. – Capacytron May 31 '20 at 09:27
  • @Capacytron - I wrote this because from the question it is not clear to me whether the output is expected to be in the original order. The example output shows the lines in the original order, but it's not clear if that is a requirement. The vanilla Reservoir Sampling algorithms I referenced do not preserve input order. Nor does it matter if the data is sorted or not, a random sample is output in all cases. GNU Shuf outputs the random sample in random order. tsv-sample has options to output in either random order or input order. Does this help? – JonDeg Jun 01 '20 at 06:42
  • Yes, thank you. – Capacytron Jun 01 '20 at 08:28