Re: Approach to efficiently choose a random line from a large file

Lets suppose you maintain a separate file (via make, maybe) which holds the line count for your data file. Call it data.count.

use Tie::File;
my $count = do '/path/to/data.count';
tie my @lines, 'Tie::File', '/path/to/data.dat';
print $lines[rand $count];
[download]

Tie::File is remarkably efficient at that sort of thing. You could avoid the auxilliary count file by calling rand @lines in the array index.

I don't see any bias for or against the fencepost lines in your proposal. There is a strong bias which favors long lines and punixhes short ones.

Utf-8 is the same as ascii in the ascii range. This code will work fine with either ascii or utf-8. You may want to open your data file first and tie to the open handle. That will let you set up the '<:utf8' mode in PerlIO.

Don't pay any attention to advice to call srand in those links. That is long superceded in perl.

After Compline,
Zaxo

Comment on Re: Approach to efficiently choose a random line from a large file Download Code

Replies are listed 'Best First'.
Re^2: Approach to efficiently choose a random line from a large file by ikegami (Patriarch) on Dec 12, 2004 at 06:09 UTC
If you're gonna keep an external file, why not put the (32 bit packed) starting index of each line in it instead of the line count? Get a random 4 byte record, unpack it, seek to that location in the file with the lines, and bingo! unbiased.	[reply]
Re^3: Approach to efficiently choose a random line from a large file by Zaxo (Archbishop) on Dec 12, 2004 at 06:54 UTC
I thought of doing something similar with an array, but decided the memory cost was too high. That was a guess, but even your much more compact idea of a packed string will occupy 40MB for a ten-million line data file. That's not necessarily prohibitive, but it might be so on a busy machine. Here's a short bit to write the packed offsets to a file: `#!/usr/bin/perl open my $out, '>:raw', '/path/to/data.offsets' or die $!; open my $in, '<', '/path/to/data.dat' or die $!; my $offset = 0; local ($_,$\); my ($this, $last) = 0; while (<$in>) { ($last, $this) = ($this, tell $in); print $out pack 'i', $last; } close $in or warn $!; close $out or warn $!;` [download] That file can be read and used like this: `my $index = do { local $/; open my $idx, '<:raw', '/path/to/data.offsets' or die $!; <$idx> }; open my $dat, '<', '/path/to/data.dat' or die $!; my ($offset) = unpack 'i', substr $index, 4*rand(length($index)/4), 4; seek $dat, $offset, 0 or warn $!; print scalar <$dat> or warn $!; close $dat or warn $!; close $idx or warn;` [download] After Compline, Zaxo	[reply] [d/l] [select]