５万件対５万件のデータを高速で内容比較

質問

perlのみを用いて５万件対５万件のデータを内容比較したいのですが、
一件ずつ取り出す、単純比較をすると処理にかなり長時間かかってしまいました。
高速で比較できる良い方法はないでしょうか？

回答No.3

toysmith · ベストアンサー

ファイル１：５万件
ファイル２：５万件
ファイルA－Z：ファイル１を頭文字に分類したファイルファイル

手順１．ファイル１→ファイルA-Zに分類
手順２．ファイル２を１件ずつ読んでファイルA-Zに存在するかどうかをチェック

この手順だとファイルアクセスが多すぎます。
（特にオーバヘッドの高いオープン処理とクローズ処理が多すぎる）

手順１でファイル１の内容を１件ずつ読み込んで処理しているのだからここでハッシュテーブルを作ってはどうでしょう？
手順２でハッシュ検索を行えばマッチングは単純です。

ファイル１の内容を「５万件＊平均数十バイト」と想定すると数メガバイトに収まります。
一般的なPerlが動作する処理系ではメモリ内で処理可能な容量だと思いますが…

お礼

アドバイスありがとうございました。
おかげで解決しそうです。
又、宜しくお願いします。

補足

ご指摘ありがとうございます。
ハッシュテーブルがどういうものか良く分からないのですが、

以下のように処理すれば良いということでしょうか？
これなら、処理が早そうな気がします。

foreach (@data_a){ $flag{$_} = 1; }

foreach (@data_b){
if(!$flag{$_}){ print "$_はデータAに存在しません。\n"; }
else{ print "$_はデータAに存在します。\n"; }
}

もっと良い方法があれば教えてください。
宜しくお願いします。

回答No.4

osamuy

＞ ファイルAのデータ　1234567　と完全一致するデータがファイルBに存在するかを確認したいです。

ということであれば、

% cat b.pl
open( IN, $ARGV[0] ) or die "?! $ARGV[0] - $!,";
while ( <IN> ){ chomp; $hash{ $_ } = 1; }
close( IN );
open( IN, $ARGV[1] ) or die "?! $ARGV[1] - $!,";
while ( <IN> ){ chomp;
$rc = defined $hash{ $_ } ? 'Exist' : 'None';
print $_, ' - ', $rc, ".\n";
}
close( IN );

――ってのは、どうでしょう。toysmithさんが回答されている連想配列を使ったもの。
実験：

% cat a.pl
for ( $i = 0; $i < 50000; $i++ ){
$l = int( rand( 3 ) ) + 3;
$s = '';
for ( $k = 0; $k < $l; $k++ ){
$s .= ( '0' .. '9', 'a' .. 'z', 'A' .. 'Z', '+', '-', '*', '/' )[　int( rand( 64 ) ) ];
}
print $s, "\n";
}
% perl a.pl >a.dat
% perl a.pl >b.dat
% time perl b.pl a.dat b.dat > result.txt
0.910u 0.070s 0:01.45 67.5% 0+0k 0+3io 0pf+0w

――２秒かかんないですね。
PowerPC/500MHz+Mem320MB+Mac OS X 10.2+perl5.6.0で試してます。

お礼

アドバイスありがとうございました。
おかげで解決しそうです。
又、宜しくお願いします。

回答No.2

osamuy

sortしてdiffとか。

toysmithさんもおっしゃってますが、結局、アルゴリズムを改良しなくてはいけませんが、そのために必要な、データの詳細についての説明が不足しているので、なんとも言いかねるかと。

補足

すいません。説明不足でした。

データ5万件とは
1234567
f39a4000
c4f7
という感じの桁数もランダムな乱数のデータ5万件が入ったファイル対ファイルです。

ファイルAのデータ　1234567　と完全一致するデータがファイルBに存在するかを確認したいです。

現在、試してみた処理として、
ファイルAのデータを頭文字毎に分別したファイルを作成・出力(a.txt,b.txt・・・)し、
ファイルBのデータの頭文字から、出力ファイルを読み込んで存在の有無を確認してます。
これでは厳しいでしょうか？

データベースはSQLとかのことでしょうか？
そうであれば、使える環境がありません

回答No.1

toysmith

比較ってどういう比較ですか？
「レコードごとにキー項目一致を抽出」という前提なら手っ取り早くデータベースを使うのが一般的では？
データベースが使えない状況ならハッシュを実装するか。

詳細がわからない（データ属性、比較条件など）ので一般論に過ぎません。
よって自信なし。

補足

すいません。説明不足でした。

データ5万件とは
1234567
f39a4000
c4f7
という感じの桁数もランダムな乱数のデータ5万件が入ったファイル対ファイルです。

ファイルAのデータ　1234567　と完全一致するデータがファイルBに存在するかを確認したいです。

現在、試してみた処理として、
ファイルAのデータを頭文字毎に分別したファイルを作成・出力(a.txt,b.txt・・・)し、
ファイルBのデータの頭文字から、出力ファイルを読み込んで存在の有無を確認してます。
これでは厳しいでしょうか？

データベースはSQLとかのことでしょうか？
そうであれば、使える環境がありません。