インデックスを使った指定行取り出しプログラム[2010-08-10-1]
についての記事を先日公開した。
そのプログラムを作成した動機の一つが
「リードオンリーのテキストファイル（それもメモリに読み込むのがうんざりするくらいに巨大なやつ）からランダムに複数の行を取り出したい」
というもの。

この記事ではランダム複数行取り出しタスクについて、先日の記事[2010-08-10-1]に沿って先頭から走査する方法とインデックスを用いた方法を紹介する。

頭から操作する方法

ランダムに一行だけ取り出すには定番の方法がある。
詳しくは[2004-11-30-5]を参照のこと。
エッセンスだけ一行で書くとこんな感じ：

rand($.) < 1 && ($line = $_) while <>;

複数行を取り出すのも同じようにできそうなんだけど分からない（未調査）。

なのでここではファイルの頭から走査するナイーブな方法で実装。
@lns に取り出したい行番号リストが格納される。

■コード（getlines-naive.pl）：

#!/usr/bin/perl
use strict;
use warnings;
my $num = shift @ARGV;
my $tgtfn = shift @ARGV;

open(my $fh, "<", $tgtfn) or die;

while (<$fh>) { }
my $line_max = $.;
die if $line_max < $num;

my @lns;
my %seen;
for (my $i = 0; $i < $num; $i++) {
    do {
        $lns[$i] = int(rand($line_max));
    } while (defined $seen{$lns[$i]});
    $seen{$lns[$i]} = 1;
}

seek $fh, 0, 0;
$. = 0;
my @res = ();
while (<$fh>) {
    for (my $i = 0; $i < $num; $i++) {
        next if $. != $lns[$i] + 1;
        $res[$i] = $_;
        last;
    }
}

close $fh;

print @res;

以下、小さいファイルでの実行例。
第一引数は取り出したい行の数。

■実行例：

% cat test.dic
Japan
Tokyo
Yokohama
This is a pen
Hello World
% ./getlines-naive.pl 3 test.dic
Tokyo
This is a pen
Yokohama
% ./getlines-naive.pl 3 test.dic
Yokohama
Tokyo
Hello World
% ./getlines-naive.pl 3 test.dic
Japan
This is a pen
Yokohama

行番号をランダムに生成するには事前に全体の行数を知る必要があるため最初に一回走査する。

何度も呼び出すことを考えるとちょっとわずらわしい。
走査する時点でインデックス作っちゃった方がいいし。

インデックスを使う方法

ということでインデックスを使う。
前回の記事と同じく mkidx.pl [2010-08-10-1]で作成。

■コード（mkidx.pl）：

#!/usr/bin/perl
use strict;
use warnings;
my $ip = 0;
while (<>) {
    print pack("N", $ip);
    $ip += length($_);
}

行数はインデックスファイルのサイズで分かるので、あとはランダムに行番号を選んで指定行取り出しを行うだけ。

■コード（getlines.pl）：

#!/usr/bin/perl
use strict;
use warnings;

my $len_of_N = 4;

my $num = shift @ARGV;
my $tgtfn = shift @ARGV;
my $idxfn = shift @ARGV || $tgtfn.".ary";

my $tfsz = -s $tgtfn;
my $ifsz = -s $idxfn;
my $line_max = $ifsz / $len_of_N;
die if $line_max < $num;

my @lns;
my %seen;
for (my $i = 0; $i < $num; $i++) {
    do {
        $lns[$i] = int(rand($line_max));
    } while (defined $seen{$lns[$i]});
    $seen{$lns[$i]} = 1;
}

open(my $fi, "<", $idxfn) or die;
open(my $fh, "<", $tgtfn) or die;

my @res = ();
for (my $i = 0; $i < $num; $i++) {
    my ($ixf, $len) = get_info($fi, $lns[$i]);
    my $str = get_string($fh, $ixf, $len);
    $res[$i] = $str;
}

close $fi;
close $fh;

print @res;

sub get_info {
    my ($fh, $qidx) = @_;
    my $buf = "";
    seek $fi, $qidx * $len_of_N, 0;
    read $fi, $buf, $len_of_N;
    my $ixf = unpack("N", $buf);
    my $ixt = (tell $fi < $ifsz) ? do {
        read $fi, $buf, $len_of_N;
        unpack("N", $buf);
    } : $tfsz;
    return ($ixf, $ixt-$ixf);
}

sub get_string {
    my ($fh, $ixf, $len) = @_;
    my $buf = "";
    seek $fh, $ixf, 0;
    read $fh, $buf, $len;
    return $buf;
}

以下、小さいファイルでの実行例。
getlines.pl の第一引数は取り出したい行の数。

■実行例：

% cat test.dic
Japan
Tokyo
Yokohama
This is a pen
Hello World
% ./mkidx.pl test.dic > test.dic.ary
% ./getlines.pl 3 test.dic
Hello World
Yokohama
Japan
% ./getlines.pl 3 test.dic
This is a pen
Tokyo
Japan
% ./getlines.pl 3 test.dic
Tokyo
Japan
Yokohama

速度比較

速度の差は前回のタスクと同じなので割愛。
理論的には O(N) と O(logN) の差。

関連記事

- [を] インデックスを使った指定行取り出しプログラム(Pure Perl)[2010-08-10-1]
（前回のタスク）
- [を] chalowの記事をランダムに取り出して表示[2004-11-30-5]
（ランダムに1行だけ取り出す手法の解説あり）