Read n random lines from a potentially huge file

Question

This challenge is about reading random lines from a potentially huge file without reading the whole file into memory.

Input

An integer n and the name of a text file.

Output

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.

Notes

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.

Motivation

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.

Answer 1

Ruby, 104 94 92 90 bytes

File name and number of lines are passed into the command line. For example, if the program is shuffle.rb and the file name is a.txt, run ruby shuffle.rb a.txt 3 for three random lines.

-4 bytes from discovering the open syntax in Ruby instead of File.new

f=open$*[0]
puts [*0..f.size/n=f.gets.size+1].sample($*[1].to_i).map{|e|f.seek n*e;f.gets}

Also, here's a 85-byte anonymous function solution that takes a string and a number as its arguments.

->f,l{f=open f;puts [*0..f.size/n=f.gets.size+1].sample(l).map{|e|f.seek n*e;f.gets}}

Answer 2

Dyalog APL, 63 bytes

⎕NREAD¨t 82l∘,¨lׯ1+⎕?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍞⎕NTIE 0

Prompts for file name, then for how many random lines are desired.

Explanation

⍞ Prompt for text input (file name)
⎕NTIE 0 Tie the file using next available tie number (-1 on a clean system)
t← Store the chosen tie number as t
83 80,⍨ Append [83,80] yielding [-1,83,80]
⎕NREAD Read the first 80 bytes of file -1 as 8-bit integers (conversion code 83)
10⍳⍨ Find the index of the first number 10 (LF)
l← Store the line length as l
(⎕NSIZE t)÷ Divide the size of file -1 with the line length
⎕ Prompt for numeric input (desired number of lines)
? X random selections (without replacement) out the first Y natural numbers
¯1+ Add -1 to get 0-origin line numbers*
l× Multiply by the line length to get the start bytes
t 82l∘,¨ Prepend [-1,82,LineLength] to each start byte (creates list of arguments for ⎕NREAD)
⎕NREAD¨ Read each line as 8-bit character (conversion code 82)

Practical example

File /tmp/records.txt contains:

Hello
Think
12345
Klaus
Nilad

Make the program RandLines contain the above code verbatim by entering the following into the APL session:

∇RandLines
⎕NREAD¨t 82l∘,¨lׯ1+⎕?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍞⎕NTIE 0
∇

In the APL session type RandLines and press Enter.

The system moves the cursor to the next line, which is a 0-length prompt for character data; enter /tmp/records.txt.

The system now outputs ⎕: and awaits numeric input; enter 4.

The system outputs four random lines.

Real life

In reality, you may want to give filename and count as arguments and receive the result as a table. This can be done by entering:

RandLs←{↑⎕NREAD¨t 82l∘,¨lׯ1+⍺?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍵⎕NTIE 0}

Now you make MyLines contain three random lines with:

MyLines←3 RandLs'/tmp/records.txt'

How about returning just a single random line if count is not specified:

RandL←{⍺←1 ⋄ ↑⎕NREAD¨t 82l∘,¨lׯ1+⍺?(⎕NSIZE t)÷l←10⍳⍨⎕NREAD 83 80,⍨t←⍵⎕NTIE 0}

Now you can do both:

MyLines←2 RandL'/tmp/records.txt'

and (notice absence of left argument):

MyLine←RandL'/tmp/records.txt'

Making code readable

Golfed APL one-liners are a bad idea. Here is how I would write in a production system:

RandL←{ ⍝ Read X random lines from file Y without reading entire file
    ⍺←1 ⍝ default count
    tie←⍵⎕NTIE 0 ⍝ tie file
    length←10⍳⍨⎕NREAD 83 80,⍨tie ⍝ find first NL
    size←⎕NSIZE tie ⍝ total file length
    starts←lengthׯ1+⍺?size÷length ⍝ beginning of each line
    ↑⎕NREAD¨tie 82length∘,¨starts ⍝ read each line as character and convert list to table
}

---

^{*I could save a byte by running in 0-origin mode, which is standard on some APL systems: remove ¯1+ and insert 1+ before 10.}

Answer 3

Haskell, 240 224 236 bytes

import Test.QuickCheck
import System.IO
g=hGetLine
main=do;f<-getLine;n<-readLn;h<-openFile f ReadMode;l<-(\x->1+sum[1|_<-x])<$>g h;s<-hFileSize h;generate(shuffle[0..div s l-1])>>=mapM(\p->hSeek h(toEnum 0)(l*p)>>g h>>=putStrLn).take n

Reads filename and n from stdin.

How it works:

main=do
  f<-getLine                   -- read file name from stdin
  n<-readLn                    -- read n from stdin
  h<-openFile f ReadMode       -- open the file
  l<-(\x->1+sum[1|_<-x])<$>g h -- read first line and bind l to it's length +1
                               -- sum[1|_<-x] is a custom length function
                               -- because of type restrictions, otherwise I'd have
                               -- to use "toInteger.length"
  s<-hFileSize h               -- get file size
  generate(shuffle[0..div s l-1])>>=
                               -- shuffle all possible line numbers 
  mapM (\->p  ...  ).take n    -- for each of the first n shuffled line numbers 
     hSeek h(toEnum 0).(l*p)>> -- jump to that line ("toEnum 0" is short for "AbsoluteSeek")
     g h>>=                    -- read a line from current position
     putStrLn                  -- and print

It takes a lot of time and memory to run this program for files with many lines, because of a horrible inefficient shuffle function.

Edit: I missed the "random without replacement" part (thanks @feersum for noticing!).

Answer 4

PowerShell v2+, 209 bytes

param($a,$n)
$f=New-Object System.IO.FileStream $a,"Open"
for(;$f.ReadByte()-ne10){$l++}
$t=$f.Length/++$l-1
[byte[]]$z=,0*$l
0..$t|Get-Random -c $n|%{$a=$f.Seek($l*$_,0);$a=$f.Read($z,0,$l-1);-join[char[]]$z}

Takes input $a as the filename and $n as the number of lines. Note that $a must be a full-path filename, and assumed to be ANSI encoding.

We then construct a new FileStream object, and tell it to access the file $a with Open privilege.

The for loop .Read()s through the first line until we hit a \n character, incrementing our line-length counter each character. We then set $t equal to the size of the file (i.e., how long the stream is) divided by how many characters per line (plus one so it counts the terminator), minus one (since we're zero-indexed). We then construct our buffer $z to also be line length.

The final line constructs a dynamic array with the .. range operator.¹ We pipe that array to Get-Random with a -Count of $n to randomly select $n line numbers without repetition. The lucky numbers are piped into a loop with |%{...}. Each iteration we .Seek to the particular location, and then .Read in a line's worth of characters, stored into $z. We re-cast $z as a char-array and -join it together, leaving the resultant string on the pipeline and output is implicit at the end of the program.

Technically we should end with a $f.Close() call to close out the file, but that costs bytes! :p

Example

a.txt:
a0000000000000000000000000000000000000000000000001
a0000000000000000000000000000000000000000000000002
a0000000000000000000000000000000000000000000000003
a0000000000000000000000000000000000000000000000004
a0000000000000000000000000000000000000000000000005
a0000000000000000000000000000000000000000000000006
a0000000000000000000000000000000000000000000000007
a0000000000000000000000000000000000000000000000008
a0000000000000000000000000000000000000000000000009
a0000000000000000000000000000000000000000000000010

PS C:\Tools\Scripts\golfing> .\read-n-random-lines.ps1 "c:\tools\scripts\golfing\a.txt" 5
a0000000000000000000000000000000000000000000000002 
a0000000000000000000000000000000000000000000000001 
a0000000000000000000000000000000000000000000000004 
a0000000000000000000000000000000000000000000000010 
a0000000000000000000000000000000000000000000000006 

---

_{¹ Technically, this means we can only support a maximum of 50,000 lines, as that's the largest range that can be dynamically created in this manner. :-/ But, we can't just loop a Get-Random command $n times, discarding duplicates each loop, since that's not deterministic ...}

Answer 5

Python 3, 146 139 bytes

from random import*
i=input
f=open(i())
l=len(f.readline())
[(f.seek(v*l),print(f.read(l)))for v in sample(range(f.seek(0,2)//l),int(i()))]
#print is here^

Input: [filename]\n[lines]\n

This solution heavily stole from @pppery but is python3.5 only and is a complete program.

Edit: Thanks to @Mego for the inline range and python3.x compatibility. Edit2: Clarification where the print is because i got two comments about it. (Comment is obviously not part of the code or the byte count.)

Answer 6

Lua, 126 122

r=io.read;f=io.open(r())c=2+f:read():len()for i=1,r()do f:seek("set",c*math.random(0,f:seek("end")/c-1))print(f:read())end

Uses 2 bytes for line breaks. Change the 2 to a 1 for 1. I only have it as 2 because that's what my test file had.

Got myself under the PHP entry, but still 2nd place (currently). Curse you, Ruby entry!

Answer 7

Bash (well, coreutils), 100 bytes

n=`head -1 $2|wc -c`;shuf -i0-$[`stat -c%s $2`/$n] -n$1|xargs -i dd if=$2 bs=$n skip={} count=1 2>&-

Explanation

This avoids reading the whole file using dd to extract the portions of the file we need without reading the file entirely, unfortunately it ends up quite large with all the options we have to specify:

if is the input file
bs is the block size (here we set it to $n which is the length of the first line
skip is set to the random integers extracted from shuf and equates to the ibs value skipping skip*ibs bytes
count the number of ibs length sections to return
status=none is needed to strip out the information normally output by dd

We get the line length using head -1 $2|wc -c and the filesize with stat -c%s $2.

Usage

Save above as file.sh and run using file.sh n filename.

Timings

time ~/randlines.sh 4 test.txt
9412647
4124435
7401105
1132619

real    0m0.125s
user    0m0.035s
sys     0m0.061s

vs.

time shuf -n4 test.txt
1204350
3496441
3472713
3985479

real    0m1.280s
user    0m0.287s
sys     0m0.272s

Times above for a 68MiB file generated using seq 1000000 9999999 > test.txt.

Thanks to @PeterCordes for his -1 tip!

Answer 8

Python 3 - 161 160 149 bytes

from random import*;
def f(n,g):f=open(g);l=len(f.readline());r=list(range(f.seek(0,2)/l));shuffle(r);[(f.seek(v*l),print(f.read(l)))for v in r[:k]]

This code defines a function which is called like f(10,'input.txt')

Answer 9

C# 259 bytes without duplicates

class Program{static void Main(string[]a){int c=Convert.ToInt32(a[1]);var h=File.ReadLines(a[0]);HashSet<int>n=new HashSet<int>();while(n.Count<c)n.Add(new Random().Next(0,h.Count()));for(;c>0;c--)Console.WriteLine(h.Skip(n.ElementAt(c-1)).Take(1).First());}}

Ungolfed

class Program{static void Main(string[] a)
{
        int c = Convert.ToInt32(a[1]);
        var h = File.ReadLines(a[0]);
        HashSet<int> n = new HashSet<int>();
        while (n.Count < c)
            n.Add(new Random().Next(0, h.Count()));           
        for (; c > 0; c--)
            Console.WriteLine(h.Skip(n.ElementAt(c-1)).Take(1).First());
    }
}

File.ReadLines is Lazy. This has the additional benefit that all lines can have different length.

Running it would be:

sample.exe a.txt 10000

C# 206 bytes with duplicates

class Program{static void Main(string[]a){var n=new Random();int c=Convert.ToInt32(a[1]);var h=File.ReadLines(a[0]);for(;c>0;c--)Console.WriteLine(h.Skip((int)(n.NextDouble()*h.Count())).Take(1).First());}}

Ungolfed

class Program
{
    static void Main(string[] a)
    {
        Random n = new Random();
        int c = Convert.ToInt32(a[1]);
        var h = File.ReadLines(a[0]);
        for (; c > 0; c--)
            Console.WriteLine(h.Skip((int)(n.NextDouble()*h.Count())).Take(1).First());
    }
}

Answer 10

Python (141 bytes)

Keeps each line with equal probability, use with pipes too. It doesn't answer the skip ahead limitation of the question though...

Usage cat largefile | python randxlines.py 100 or python randxlines 100 < largefile (as @petercordes pointed out)

import random,sys
N=int(sys.argv[1])
x=['']*N
for c,L in enumerate(sys.stdin):
    t=random.randrange(c+1)
    if(t<N):x[t] = L
print("".join(x))