This challenge is about reading random lines from a potentially huge file without reading the whole file into memory.
n and the name of a text file.
n lines of the text file chosen uniformly at random without replacement.
You can assume that
n is in the range 1 to the number of lines in the file.
Be careful when sampling
n numbers at random from the range that the answer you get is uniform.
rand()%n in C is not uniform for example. Every outcome must be equally likely.
Rules and restrictions
Each line of the text file will have the same number of characters and that will be no more than 80.
Your code must not read any of the contents of text file except:
- Those lines it outputs.
- The first line to work out how many characters per line there are in the text file.
We can assume each character in the text file takes exactly one byte.
Line separators are assumed to be 1 byte long. Solutions may use 2 bytes long line separators only if they specify this need. You may also assume the last line is terminated by a line separator.
Your answer should be a complete program but you can specify the input in any way that is convenient.
Languages and libraries
You can use any language or library you like.
There was a concern about calculating the number of lines in the file. As nimi points out in the comments, you can infer this from the file size and the number of chars per line.
In chat some people asked if this is really a "Do X without Y" question. I interpret this to ask if the restrictions are unusually artificial.
The task of randomly sampling lines from huge files is not uncommon and is in fact one I sometimes have to do. One way to do this is in bash:
shuf -n <num-lines>
This is however very slow for large files as it reads in the whole file.