16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why the downvote? \$\endgroup\$ – user9206 May 5 '16 at 8:39
  • 3
    \$\begingroup\$ This is trivial in languages like C that have fseek, and impossible in others. Additionally, what if n is greater than the number of lines in the file? \$\endgroup\$ – Mego May 5 '16 at 8:47
  • 4
    \$\begingroup\$ @Mego: regarding your point b): you can calculate the number of lines by dividing the file size by the length of a line. \$\endgroup\$ – nimi May 5 '16 at 9:01
  • 8
    \$\begingroup\$ Do X without Y is a warning that starts with "This isn't always bad". The main problem is artificial restrictions like "don't use +" which gives advantage to languages which have a sum(). Not reading a file into memory is a clear and consistent restriction which is in no way arbitrary. It can be tested with a file larger than memory, which cannot be worked around by language differences. It also happens to have real world applications (although that isn't necessary for a golf...). \$\endgroup\$ – trichoplax May 5 '16 at 9:52
  • 1
    \$\begingroup\$ It looks like this is actually a restricted complexity code golf where the memory usage is limited despite potentially huge files. It's not about not having certain things in your code but a limitation on how the code may act. \$\endgroup\$ – xnor May 5 '16 at 14:18

10 Answers 10

5
\$\begingroup\$

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*
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.

\$\endgroup\$
  • \$\begingroup\$ Ahh.. APL :) Is there some way to test this code in linux? \$\endgroup\$ – user9206 May 12 '16 at 6:15
  • \$\begingroup\$ @Lembik Sure, this code is cross platform. Download from dyalog.com \$\endgroup\$ – Adám May 12 '16 at 6:18
  • \$\begingroup\$ As I don't read APL, could you explain the code? The tricky parts are sampling lines without replacement and jumping directly to the right place in the file to read the lines. \$\endgroup\$ – user9206 May 12 '16 at 10:30
  • \$\begingroup\$ @Lembik That part is easy. ⎕NREAD's argument is TieNumber ConversionCode BytesToRead [StartByte]. It reads just the required bytes. The rest is just figuring out what to read. \$\endgroup\$ – Adám May 12 '16 at 21:13
  • \$\begingroup\$ @Lembik I'm curious why my answer didn't win the bounty. \$\endgroup\$ – Adám May 14 '16 at 21:59
7
+50
\$\begingroup\$

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}}
\$\endgroup\$
  • \$\begingroup\$ Below 100 bytes! Maybe Ruby is the best golfing language after all. Does 'sample' avoid repetitions? \$\endgroup\$ – user9206 May 8 '16 at 5:16
  • \$\begingroup\$ @Lembik ruby-doc.org/core-2.2.0/Array.html#method-i-sample It does avoid repetitions. Don't tell me... was I supposed to have repetitions? \$\endgroup\$ – Value Ink May 8 '16 at 6:03
  • \$\begingroup\$ No you are perfect :) \$\endgroup\$ – user9206 May 8 '16 at 7:08
  • \$\begingroup\$ Can you save any bytes by reading from stdin? ruby shuffle.rb 3 < a.txt gives you a seekable stdin. IDK Ruby, though. \$\endgroup\$ – Peter Cordes May 14 '16 at 4:33
  • 1
    \$\begingroup\$ @PeterCordes That makes sense, but as mentioned, the point of failure is Ruby being unable to read the file size of stdin, so it didn't work out. \$\endgroup\$ – Value Ink May 14 '16 at 8:15
5
\$\begingroup\$

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!).

\$\endgroup\$
  • \$\begingroup\$ Haskell rocks :) \$\endgroup\$ – user9206 May 5 '16 at 19:22
  • 1
    \$\begingroup\$ How does it avoid picking a line which was already chosen? \$\endgroup\$ – feersum May 5 '16 at 21:47
  • \$\begingroup\$ @feersum: oh, I missed that part. Fixed. \$\endgroup\$ – nimi May 6 '16 at 9:41
  • \$\begingroup\$ I see stackoverflow.com/questions/13779630/… is somewhat verbose! \$\endgroup\$ – user9206 May 6 '16 at 10:07
  • 1
    \$\begingroup\$ Maybe there should be a separate challenge on sampling without replacement in small space. \$\endgroup\$ – user9206 May 6 '16 at 11:17
3
\$\begingroup\$

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.1 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 

1 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 ...

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thank you! Which part is python 3.5 only? \$\endgroup\$ – user9206 May 9 '16 at 9:01
  • 2
    \$\begingroup\$ r=range(f.seek(0,2)//l) will work, which shaves off 3 bytes and removes the need for 3.5. Even better, shave off 3 more bytes by inlining the range call in the sample call. Additionally, this is not a complete program - you need to actually print the list. \$\endgroup\$ – Mego May 9 '16 at 9:19
  • \$\begingroup\$ @Lembik: It was 3.5 only because i used r=[*range(f.seek(0,2)//l)] because i thought i couldn't sample a generator. Turns out I could. @Mega: It is complete because it prints a every line inside the list comprehension print(f.read(l)) \$\endgroup\$ – Alexander Nigl May 9 '16 at 10:56
  • \$\begingroup\$ You do need a print statement though. \$\endgroup\$ – user9206 May 9 '16 at 10:58
  • \$\begingroup\$ print is inside the list comprehension. \$\endgroup\$ – Alexander Nigl May 9 '16 at 11:01
2
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Lua was the first programming language I learned, and even with all I've learned since then, it's still my favorite. It's just so versatile for its ease to write. \$\endgroup\$ – Blab May 12 '16 at 3:51
2
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ I always love a bash answer but can you explain how this doesn't read the whole file? \$\endgroup\$ – user9206 May 13 '16 at 10:28
  • 2
    \$\begingroup\$ @Lembik added explanation! \$\endgroup\$ – Dom Hastings May 13 '16 at 10:35
  • 1
    \$\begingroup\$ You can bs= instead of ibs=, since setting obs as well is fine. I guess you can't replace if=$2 with <$2 though, since this is still xargs's command line. \<$2 doesn't work either (xargs uses exec directly, without a shell). \$\endgroup\$ – Peter Cordes May 14 '16 at 4:00
  • \$\begingroup\$ I hope this isn't too much but I sort of love this answer :) Just tested it with a 1GB file. \$\endgroup\$ – user9206 May 14 '16 at 15:23
  • 1
    \$\begingroup\$ re: redirecting stderr to stdin: You could also close stderr with 2>&-, so there's no danger of the output going anywhere (e.g. if stdin happened to be a read-write file descriptor). It works with GNU dd: It still produces its stdout before trying and failing to write to stderr. \$\endgroup\$ – Peter Cordes May 14 '16 at 22:16
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ The challenge requires a full program, so I'm afraid a function definition is not enough. \$\endgroup\$ – nimi May 7 '16 at 21:08
  • \$\begingroup\$ To save a byte remove space between import and *. \$\endgroup\$ – mriklojn May 7 '16 at 22:14
  • 1
    \$\begingroup\$ @nimi Requiring a full program for this challenge seems to be arbitarily overriding the default code format rules \$\endgroup\$ – pppery May 8 '16 at 0:22
  • \$\begingroup\$ @ppperry: yes, maybe, but that's just how it is. \$\endgroup\$ – nimi May 8 '16 at 0:30
  • \$\begingroup\$ To get the length of the file you could f.seek(0,2), that makes import os and os.stat obsolete. \$\endgroup\$ – Alexander Nigl May 9 '16 at 8:18
1
\$\begingroup\$

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());
    }
}
\$\endgroup\$
  • \$\begingroup\$ I don't fully follow your solution. If all lines have different lengths then the task is impossible. Also, how you are randomly sampling lines without replacement exactly? I apologise my C# isn't good enough. \$\endgroup\$ – user9206 May 12 '16 at 10:22
  • \$\begingroup\$ @Lembik You are right, i didn't think about duplicates. And I can count the amount of lines and extract lines by linenumber, which is why lines may be variable lengh. \$\endgroup\$ – Master117 May 12 '16 at 10:27
  • \$\begingroup\$ But you have to jump to a location in the file only knowing the line number don't you? You can't tell where that is unless all the lines have the same length. \$\endgroup\$ – user9206 May 12 '16 at 10:28
  • \$\begingroup\$ @Lembik File.ReadLines("pathToFile") create a Lazy enumeration on all Lines of the File, File.ReadLines("pathToFile").elementAt(19) returns the 19th Line of the File. Kinda like a Map of all Linestarts. \$\endgroup\$ – Master117 May 12 '16 at 10:41
  • \$\begingroup\$ I don't think Lazy enumeration jumps (or seeks) in the file sadly. So it doesn't fit the rules currently. \$\endgroup\$ – user9206 May 12 '16 at 10:46
1
\$\begingroup\$

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))
\$\endgroup\$
  • 3
    \$\begingroup\$ The whole point of this question is that you have to seek in the input stream. You should probably say that that's the part of the question's restrictions you're ignoring (although the read-from-a-pipe example usage makes that pretty clear). Reading from stdin with python ./randxlines.py 100 < largefile would be fine for a proper answer, though: in that case stdin will be seekable. \$\endgroup\$ – Peter Cordes May 14 '16 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy