大量データから抽出する効率よいperlプログラムは

質問

以前も質問させていただきましたが、
大量データから抽出する際の効率よいperlプログラム作成について
また、教えてください。
例）
大量データ　Aファイル　3列　可変値（数値、URL、数値）タブ区切り　重複値あり
123　http://www.XX.co.jp/XX　4567
1111　http://www.XX.co.jp/XX　3333
3　http://www.XX.co.jp/YZ　4567
1111　http://www.YYY…　116
…
抽出対象データ　Bファイル　1列（URL）重複なし
http://www.XX.co.jp/X
http://www.YYY.co.jp
…

BファイルにあるURLで始まるURLがAファイルにある場合　Aファイルのその行を抽出したい。
grepで実施すると　すごい時間がかかってしまうため、効率よい抽出方法をおしえてください。
今回は、完全一致ではなく、Bファイルに入っているリストのURLから始まるものにしたいと考えているので、前の手法（hash連想配列）が使えないと考えております。
Aファイルが容量大きいため、ｇｒｅｐ処理では1週間たっても終わらないのです。

回答No.7

sholmes · ベストアンサー

本当に終わるか気になったので、自分のPCで試してみました。
メモリ4Gであれこれ普通に使いながら、次のものです。
ただ、内一個は途中でやめちゃいました。

まず、こんなかんじでdummyファイルを作りました

Ruby
# dummy作成
http://ideone.com/TDxut
→1Gバイトで約2000万件の嘘データ
# フィルタ元リスト作成
→dummyの頭50件の、URL内ドメイン箇所までのリスト

Ruby
# 文字列マッチ
http://ideone.com/xPsku
→約25分

# 正規表現マッチ
http://ideone.com/kvSff
→途中でやめた為不明

GNU/grep
# grep -F -f 元リスト.txt dummy.txt
→1分弱!

ということで、少なくともRubyでは全く太刀打ちできませんでした。
でも、終わる分量ではあると思います。特にPerlならきっともっと早いんでしょう
やっぱりgrepがおすすめですね

お礼

処理試してみました。
まだ、2日間ｐｅｒｌプログラムを回しても終わらなかったのが、
ほんの数分で完了しました。
プログラム知識がないので、ファイル内容を読み取り　ｇｒｅｐ関数が処理してくれるという方法を知らなかったので、助かりました。
ありがとうございました。

回答No.9

TYWalker

＃１です。

＞今回は、完全一致ではなく、Bファイルに入っているリストのURLから始まるものにしたいと考えているので、前の手法（hash連想配列）が使えないと考えております。

＞この方法は　Bファイル内のURLと完全一致のものを探すということになりませんでしょうか？

あっそうか。
じゃindex関数使えばいいんじゃないでしょうか。
http://perl.enstimac.fr/perl5.6.1/5.6.1/pod/perlfunc.html#item_index

★

ｏｐｅｎ　Ｂ，”Ｂ．ｔｘｔ”　ｏｒ　ｄｉｅ　＄！；　＃タブ区切りなので拡張子を変更
ｗｈｉｌｅ（＜Ｂ＞）　｛
　ｃｈｏｍｐ；　＃改行を取る
　＄ｂ＿ｕｒｌ｛＄＿｝　＝　１；　＃ハッシュのキーに入れる。値はテキトー
｝
ｃｌｏｓｅ　Ｂ；

＠ｂ＿ｕｒｌ　＝　ｓｏｒｔ　ｋｅｙｓ　％ｂ＿ｕｒｌ；
　＃ソートはシュウォーツ変換をすると早くなる。でもこのプログラムここが律速段階ではない

ｏｐｅｎ　Ａ，”Ａ．ｔｘｔ”　ｏｒ　ｄｉｅ　＄！；
ｏｐｅｎ　Ｃ，”＞Ｘ．ｔｘｔ”　ｏｒ　ｄｉｅ　＄！；
ｗｈｉｌｅ（＜Ａ＞）　｛
　（ｕｎｄｅｆ，＄ｕｒｌ）＝ｓｐｌｉｔ　／￥ｔ／；　＃２個目の値にしか用はない

　ｆｏｒ　＄ｂ＿ｕｒｌ（＠ｂ＿ｕｒｌ）　｛
　　＃ここは普通の配列サーチなので「番兵」を使ったりすると高速化できる
　　　ｉｆ　（ｉｎｄｅｘ（＄ｕｒｌ，＄ｂ＿ｕｒｌ））｛
　　　　　ｐｒｉｎｔ　Ｃ；
　　　　　ｌａｓｔ；
　　　｝
　｝
｝
ｃｌｏｓｅ　Ａ；　＃ファイルハンドルが間違ってた
ｃｌｏｓｅ　Ｃ；

★

Larry Wallによると、組み込みのgrep関数よりもPerlは速いっていうことなんですけど、どうなんでしょうね。
上のプログラムも＠ｂ＿ｕｒｌがオンメモリなんでそこそこ速いと思います。
ま、やさしい例ってことで。

お礼

index関数というものを利用すればよいということは気がつきませんでした。
これで　どのくらいの速度がでるか試してみたいと思います。
ありがとうございます。

回答No.8

_--_1l1_1_

尻のデータが引っかからないことがわかった。ちょっと改造。

sub create_index {
　　my $sumpling_interval = shift;
　　my @splited_lines　　 = @_;
　　my @index　　　　　　 = ();

　　for ( my $i = 0; ( $i * $sumpling_interval ) <= $#splited_lines; $i++ ) {
　　　　my $pos = $i * $sumpling_interval;
　　　　push @index, { pos => $pos, url => $splited_lines[$pos]->{url} };
　　}

　　# indexの尻に番兵を置く
　　push @index, { pos => $#splited_lines, url => $splited_lines[$#splited_lines]->{url} };
　　return @index;
}

回答No.6

_--_1l1_1_

適当。表示がずれるので空白2文字を全角空白で書いていることに注意

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my $words_file = shift || '/usr/share/dict/words';

my @lines = create_dummy_data( $words_file,
　　[ 'google.co.jp', 'yahoo.com', 'bing.jp' ] );
print $#lines, $/;

my @splited_lines = split_lines(@lines);
@splited_lines = sort { $a->{url} cmp $b->{url} } @splited_lines;
my @index　　　 = create_index( 1000, @splited_lines );
my @target_urls = qw(http://google.co.jp/picture http://bing.jp/illust);
my @finded　　　= find_lines( \@splited_lines, \@index, \@target_urls );

print Dumper($_), $/ for @finded;

sub find_lines {
　　my $splited_line_ref = shift;
　　my $index_ref　　　　= shift;
　　my $target_url_ref　 = shift;
　　my @finded　　　　　 = ();

URL_LIST:
　　for my $target_url ( @{$target_url_ref} ) {
　　　　my $previous_pos = -1;
　　　　for my $index ( @{$index_ref} ) {
　　　　　　if ( ( $target_url cmp $index->{url} ) <= 0 ) {
　　　　　　　　if (　 ( $previous_pos == -1 )
　　　　　　　　　　&& ( $target_url cmp $index->{url} ) != 0 )
　　　　　　　　{

　　　　　　　　　　#　Not found
　　　　　　　　　　next URL_LIST;
　　　　　　　　}

　　　　　　　　# search first match pos
　　　　　　　　my $pos = $previous_pos;
　　　　　　　　while ( $splited_line_ref->[$pos]->{url} !~ m/^$target_url/ )
　　　　　　　　{
　　　　　　　　　　if ( $pos > $index->{pos} ) {

　　　　　　　　　　　　#　Not found
　　　　　　　　　　　　next URL_LIST;
　　　　　　　　　　}
　　　　　　　　　　$pos++;
　　　　　　　　}

　　　　　　　　# founded. push data
　　　　　　　　while ( $splited_line_ref->[$pos]->{url} =~ m/^$target_url/ )
　　　　　　　　{
　　　　　　　　　　push @finded, $splited_line_ref->[$pos];
　　　　　　　　　　$pos++;
　　　　　　　　}
　　　　　　}
　　　　　　$previous_pos = $index->{pos};
　　　　}
　　}
　　return @finded;
}

sub create_index {
　　my $sumpling_interval = shift;
　　my @splited_lines　　 = @_;
　　my @index　　　　　　 = ();

　　for ( my $i = 0; ( $i * $sumpling_interval ) <= $#splited_lines; $i++ ) {
　　　　my $pos = $i * $sumpling_interval;
　　　　push @index, { pos => $pos, url => $splited_lines[$pos]->{url} };
　　}
　　return @index;
}

sub split_lines {
　　my @lines　　　　 = @_;
　　my @splited_lines = ();

　　for my $line (@lines) {
　　　　if ( $line =~ m/(\d+)\s(.+)\s(\d+)/ ) {
　　　　　　push @splited_lines, { num1 => $1, url => $2, num2 => $3 };
　　　　}
　　}
　　return @splited_lines;
}

sub create_dummy_data {
　　my $file　　　　 = shift;
　　my $base_url_ref = shift;
　　my @lines　　　　= ();

　　open my $fh, '<', $file or die "$!:$file";
　　while ( my $word = <$fh> ) {
　　　　$word =~ s/\x0D?\x0A?$//;
　　　　for my $base_url ( @{$base_url_ref} ) {
　　　　　　my $url　= 'http://' . $base_url . '/' . $word;
　　　　　　my $line = '1234' . "\t" . $url . "\t" . '56789';
　　　　　　push @lines, $line;
　　　　}
　　}
　　close $fh or die "$!:$file";
　　return @lines;
}

お礼

プログラムを具体的に書いていただき、ありがとうございます。
しかも、処理を実際に試していただき、確認までありがとうございます。
ｉｎｄｅｘ関数で考えることに気がつかなかったので、今回　大変勉強になりました。
ｐｅｒｌプログラムで処理する場合は　これを活用させていただきます。

回答No.5

sholmes

速度が求められていて尚且つUNIX環境なのであれば、
OS添付のgrepコマンドを第一選択肢にすることを自分からもおすすめします。

ただ検索対象にURLが入ってますので、-Fオプションは付けたほうがいいでしょう

grep -f b.txt -F a.txt

のように

＜おまけ＞
丁度この間同じような処理のワンライナーが話題に出ました。

http://okwave.jp/qa/q6719586.html

ここで書いたワンライナーは、みなさん同様逐次処理です。
awk/Perlはこの手の本家なので、短くかつ早いものが書けるんじゃないかなと思います。

回答No.4

t-okura

perl プログラムではなく、Linux コマンドの grep を使ってはいかがでしょうか。

grep -f Bファイル Aファイル > extract.txt

で B ファイルの各行を含む Aファイルの行が抽出されます。

grep コマンドは C で書かれているし、そもそも抽出するためのコマンドなので
高速に抽出するための最適化が行われていると期待してもよいのではないでしょうか。

perl での解決ではないので反則かな。

回答No.3

kumoz

index を使ってみましたが、どの程度時間がかかるはわかりません。

use strict;
my @search;
open IN, "B" or die "Can't open B: $!";

while (my $line = <IN>) {
chomp $line;
push @search, $line;
}

open IN, "A" or die "Can't open A: $!";

while (my $line = <IN>) {
foreach my $search (@search) {
if (index($line, $search) > -1) {
print $line;
last;
}
}
}

お礼

indexを利用することを教えていただき、ありがとうございます。
index処理を試してみたいと思います。

回答No.2

rukuku

こんばんは

＞大量データから抽出する
これは、SQL(データベースに使う言語)が得意とするところです。
可能ならば、SQLで処理できるようにする方が、Parlの中だけで行うより簡単かつ高速になると思います。

補足要求です
１．レコードの数（データの行数）はどれくらいですか？（数万、数十万など、桁を教えてください）
２．手元にあるパソコン等で行いますか？それとも、Web上で行いますか？

補足

回答ありがとうございます。
SQL利用ではなく、プログラム処理での方法ができればしりたく、
ご助言は　感謝いたしますが、grepではないよい方法がありましたら　教えてください。
レコードは　数千万行ほどです。
サーバ上で、直にプログラムをたたくつもりでおります。

回答No.1

TYWalker

Perlですからもっとうまい人が書けばもっとカッコよくなるかどうかわからないんですが・・・。

ｏｐｅｎ　Ｂ，”Ｂ．ｃｓｖ”　ｏｒ　ｄｉｅ　＄！；
ｗｈｉｌｅ（＜Ｂ＞）　｛
　ｃｈｏｍｐ；　＃改行を取る
　＄Ｂ｛＄＿｝　＝　１；　＃ハッシュのキーに入れる。値はテキトー
｝
ｃｌｏｓｅ　Ｂ；

ｏｐｅｎ　Ａ，”Ａ．ｃｓｖ”　ｏｒ　ｄｉｅ　＄！；
ｏｐｅｎ　Ｃ，”＞Ｘ．ｃｓｖ”　ｏｒ　ｄｉｅ　＄！；
ｗｈｉｌｅ（＜Ａ＞）　｛
　（ｕｎｄｅｆ，＄ｕｒｌ）＝ｓｐｌｉｔ　／￥ｔ／；　＃２個目の値にしか用はない
　ｐｒｉｎｔ　Ｃ　ｉｆ　＄Ｂ｛＄ｕｒｌ｝；　＃＄ｕｒｌがハッシュ％Ｂのキーとして存在すれば１を返すので真
｝
ｃｌｏｓｅ　Ｂ；
ｃｌｏｓｅ　Ｃ；

早く終わるかどうかわかりません。
どっちもソートしてよかったらもっと早くなるかもしれないけど・・・。

補足

回答ありがとうございます。
この方法は　Bファイル内のURLと完全一致のものを探すということになりませんでしょうか？