pick N random lines from a file

[David Garamond]

I'm trying to extend the Perl cookbook recipe on how to pick a random
line from a file:

#!/usr/bin/perl
rand($.) < 1 && ($line = $_) while <>;
print $line;

for picking up to N random lines from a file:

------------start code--------------
#!/usr/bin/perl

die "Usage: $0 <N>, where N is the number of lines to pick\n"
if @ARGV < 1;
$N = shift @ARGV;

@pick = ();
while (<>) {
if (@pick < $N) {
push @pick, $_;
($r1, $r2) = (rand(@pick), rand(@pick));
($pick[$r1], $pick[$r2]) = ($pick[$r2], $pick[$r1]);
} else {
rand($.) <= $N and $pick[rand(@pick)] = $_;
}
}

print @pick;
-------------end code---------------

Could anyone verify if the algorithm is correct?

Thanks in advance,
--
dave

[Kevin Old]

On Wed, 2003-12-10 at 11:12, David Garamond wrote:

> I'm trying to extend the Perl cookbook recipe on how to pick a random
> line from a file:
>
> #!/usr/bin/perl
> rand($.) < 1 && ($line = $_) while <>;
> print $line;
>
> for picking up to N random lines from a file:
>
> ------------start code--------------
> #!/usr/bin/perl
>
> die "Usage: $0 <N>, where N is the number of lines to pick\n"
> if @ARGV < 1;
> $N = shift @ARGV;
>
> @pick = ();
> while (<>) {
> if (@pick < $N) {
> push @pick, $_;
> ($r1, $r2) = (rand(@pick), rand(@pick));
> ($pick[$r1], $pick[$r2]) = ($pick[$r2], $pick[$r1]);
> } else {
> rand($.) <= $N and $pick[rand(@pick)] = $_;
> }
> }
>
> print @pick;
> -------------end code---------------
>
> Could anyone verify if the algorithm is correct?

Dave,

Yes, your algorithm seems to work. I just made a file with a number
(1-20) on each line, then ran it and it seems to work just fine.

HTH,
Kevin
--
Kevin Old <kold@kold.homelinux.com>

[Robert Brown]

Kevin Old writes:

> On Wed, 2003-12-10 at 11:12, David Garamond wrote:

> > I'm trying to extend the Perl cookbook recipe on how to pick a random
> > line from a file:
> >
> > #!/usr/bin/perl
> > rand($.) < 1 && ($line = $_) while <>;
> > print $line;
> >
> > for picking up to N random lines from a file:

The classical algorithm for this is found in Knuth's "Art of computer
cproagramming, vol 2, seminumerical algorithms" on pp 121-123. Here
is a C++ routine I wrote several years ago that implements the
algorithm given in Knuth; perhaps it will help you write one in C:

9: // Knuth's random sample algotithm S, "Seminumerical Algorithms" pp 121-123.
10: //
11: void sample(prng rand, long* slot, long n, long N) { // take a random sample
12: long t; // counts up to N
13: long m = 0; // counts up to n

15: for (t = 0; m < n; t++) { // loop till all n slots are chosen
16: if (rand.next(0, N - t) < n - m) { // do we select this from 0..N?
17: slot[m++] = t; // yes,
18: }
19: }
20: }

--
-------- "And there came a writing to him from Elijah" [2Ch 21:12] --------
R. J. Brown III [email]rj@elilabs.com[/email] [url]http://www.elilabs.com/~rj[/url] voice 847 543-4060
Elijah Laboratories Inc. 457 Signal Lane, Grayslake IL 60030 fax 847 543-4061
----- M o d e l i n g t h e M e t h o d s o f t h e M i n d ------