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

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

No.3 ベストアンサー 回答者： toysmith 回答日時： 2002/09/06 23:51

ファイル１：５万件

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

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

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

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

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

この回答への補足

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

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

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

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

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

補足日時：2002/09/07 01:38

この回答へのお礼

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

お礼日時：2002/09/11 05:27

No.4 回答者： osamuy 回答日時： 2002/09/07 01:41

＞ ファイル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で試してます。

この回答へのお礼

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

お礼日時：2002/09/11 05:27

No.2 回答者： osamuy 回答日時： 2002/09/06 09:30

sortしてdiffとか。

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

この回答への補足

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

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

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

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

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

補足日時：2002/09/06 23:18

No.1 回答者： toysmith 回答日時： 2002/09/06 07:26

比較ってどういう比較ですか？

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

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

この回答への補足

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

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

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

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

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

補足日時：2002/09/06 22:51