やりたいことは、
OldFile.txt
NewFile.txt
の2つのテキストファイルがあります。
この2つのファイルを比較して、OldFile.txtに記載が無く、NewFile.txtのみに書かれている行をOut.txtファイルに書き出すプログラムです。下記のスクリプトで数GB程度であれば問題なく動くのですが、ファイルのサイズが、OldFile,NewFile共に、それぞれ50GB程度、10億行程度(1行は長くても300byte)となると当然ですがメモリを膨大に消費し上手く動きません。また、一時ファイルを作るタイプも作ってみたのですが、コードが悪いようで何十時間も演算していますのでお手上げです。
素早く動作する方法をすぐ使えるスクリプト(外部ソフト組込み可)と共に教えて下さい。とりあえず、すぐにテストできるよう、スクリプトの提示は必須でお願い致します。
$file1 = "OldFile.txt";
$file2 = "NewFile.txt";
open (IN, "<$file1");
for (<IN>){
$hash{$_} = 1;
}
close(IN);
open (IN2, "<$file2");
for (<IN2>){
unless($hash{$_} == 1){
open(WR,">>Out.txt");
print WR $_;
close(WR);
}
}
close(IN2);
環境
Core i5 メモリ 12GB Windows 7 x64 ActivePerl
この課題、巨大なデータに対する高速な検索および比較は本質的に難しいものです。
ここでソースコードがぱっと出てくるようなものではないですよ。
そのデータ規模だとPerlに向いている処理ではありません。
そしてそれなりの容量のメモリ、高速なストレージがないと高速に処理を行えません。
単純に考えて1G行に対応する32bitハッシュキーだけでも2GBになるので、これを連想マップとして保持するとしたら10GB以上は消費するのではないでしょうか。
メモリに乗せないで処理するとなると、ディスクへ検索用インデックスを保存しておいて読み込むことになるので、SSDを使用するなどの工夫が必要でしょう。
メモリを多く使用するので、32bitOSの4GBでは不足だと思います。64bitOSで処理した方が良いでしょうね。
私ならば以下の戦略を検討します。
* split/sort/uniq/diff
Linuxのコマンドを使います。
ファイルAをsplitで100個以上に分割。各ファイルをsort。sort -m で分割したファイルをマージソートして1つのファイルに結合。uniqで重複行削除。
ファイルBに対してもsplit/sort/sort -m/uniqを実行。
生成された2つのファイルをdiffで比較。
分割数はメモリ使用量を見て調整します。ファイル内容によってはメモリを大量に消費するかもしれません。
* メモリ上でハッシュキー検索
ファイルAの各行のハッシュキーを計算してメモリへ保存。ファイルBの各行のハッシュキーを計算してメモリ上を検索。検索にヒットしなかった行をまとめてファイルAを読み込みながら再確認。メモリは少なくとも32GBは必要でしょう。
言語はC/C++で。
* KVS
KVSやNoSQLと呼ばれているデータベースを使用して、ファイルAの各行を保存。ファイルBの各行をキーとして1G回の問い合わせをする。ディスクはSSD。
* RDBMS
MySQL、PostgreSQLなどのRDBMSへファイルAの各行とファイルBの各行を別々のテーブルに保存。差分を問い合わせる。ディスクはSSD。
回答いただきありがとうございます。
2012/04/01 12:04:29なかなか難しいようですね・・・