人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

Perlなどプログラムを使って、重複する行を抜き出すプログラムが欲しい。

やりたいことは、
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

●質問者: j4mika
●カテゴリ:コンピュータ 科学・統計資料
○ 状態 :キャンセル
└ 回答数 : 1/1件

▽最新の回答へ

1 ● jaga3

この課題、巨大なデータに対する高速な検索および比較は本質的に難しいものです。
ここでソースコードがぱっと出てくるようなものではないですよ。

そのデータ規模だと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。


j4mikaさんのコメント
回答いただきありがとうございます。 なかなか難しいようですね・・・
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ