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
みんなの回答
-
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。 -
この質問へのコメント
質問の情報
- 登録日時
- 2012-04-01 00:56:25
- 終了日時
- 2012-04-01 12:05:37
- 回答条件
- 1人5回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
この英文どうなってますか？ The boy seemed to be waiting for his mother to come.（その少年は母親が来…
匿名質問者
3
1
-
不定詞の形容詞的用法らしいんですけど、副詞的用法と書いたら✖️ですか？ I want to buy a book to read …匿名質問者11
-
日向陽葵という○V女優が好きなのですが似ている○V女優はいますか匿名質問者
-
共通テストで使われるプログラミング言語は共通テスト特有の言語と聞いたのですが、受験勉強で身につけたプ…匿名質問者21
-
内定してほしいポケモンはいますか？匿名質問者
それぞれ長所も短所もあるので、
どれが一番早いかは実データがないと判りませんが、
とりあえず使いやすさ優先順にいくつか例をあげておきます
（１）Text-Diff Algorithm-Diffのラッパー
http://search.cpan.org/~ovid/Text-Diff/
ソースコード http://cpansearch.perl.org/src/OVID/Text-Diff-1.41/lib/Text/Diff.pm
（２）String-Diff-0.04
http://search.cpan.org/~yappo/String-Diff-0.04/
ソースコード http://cpansearch.perl.org/src/YAPPO/String-Diff-0.04/lib/String/Diff.pm
（３）Algorithm-Diff
http://search.cpan.org/~nedkonz/Algorithm-Diff-1.15/
ソースコード http://cpansearch.perl.org/src/NEDKONZ/Algorithm-Diff-1.15/lib/Algorithm/Diff.pm
モジュールやcpanの使い方から説明しなければならないとなると時間的に無理かもしれないし、
1ファイルが50GBにもなるテキストファイルでやったことはないので、コメントにしておきます
モジュールについてはいくつか試したことがありますが、よく分からないエラー（多分メモリ問題）が発生してうまくいっていません。容量が大きいですので、明示的にそれが書いてあるような物でないと難しいようです。
単にOldFile.txtがhashに乗り切らないということですから。
hashに乗せるのを1000万行くらいにして一度試されてはいかがですか。
それで結果ファイルが出来たら、
次はOldFile.txtの次の1000万行を、その結果ファイルと比較すればいいので、最初程は時間がかかりませんよね。
結果ファイルはNewFile.txtより小さいですから。
これを100回で10億行と比較できるので、現実的な時間で終わると思います。
私ならpythonでset型を使い上記の手順でやります。
質問をキャンセルして、もう一度動作について見直して、丁度、全く同じ方法を思いつき行っているところでした。とりあえず、目処が立つ所まで来ました。良くありそうな話ですので、簡単に動く物が転がっていればと思ったのですけどね・・・