PERLで巨大ファイル(10GB程度)の重複行を削除する方法を教えてください。

また、下記のように、一度全てをメモリに読み込んで行う方法ではパソコンが落ちてしまいました。
そのため、これ以外の、非力なパソコンでもできるような、メモリを節約した方法を教えてください。
宜しくお願い致します。

open(FH,"<file");
my @array = <FH>;
close(FH);
my %count;
@array = grep {!$count{$_}++} @array;
open(FH,">file2");
print @array;
close(FH);

__file__
1234
ASDF
1234
A1234
以下続く

__file2__
ASDF
1234
A1234
以下続く

回答の条件
  • 1人5回まで
  • 登録:2008/12/06 09:20:33
  • 終了:2008/12/06 22:04:31

ベストアンサー

id:cicupo No.4

cicupo回答回数13ベストアンサー獲得回数32008/12/06 15:59:50

ポイント140pt

以下のスクリプトでいかがでしょうか。

Windows環境でテストしていませんし、スペックも不明なのでどうか分かりませんが。

  • 入力ファイルは「file」
  • 出力ファイルは「result」
  • 「1000000」のところを適当に調整してください。大きすぎるとメモリの使用量が増えます。小さすぎると中間ファイルの個数が多くなってOS等の制限にひっかかる可能性があります。

でもフリーソフトの windows 版 uniq もたくさんありますねー。

#!/usr/bin/perl
use strict;
use warnings;

open(FH,"<file");
my @tmpfiles;
my %check;
my $count = 0;
while (<FH>) {
    if ($check{$_}) { next; }
    $check{$_} = 1;
    $count++;
    if ($count > 1000000) {
        my $tmpfile = "tmp_$#tmpfiles";
        push (@tmpfiles, $tmpfile);
        print $tmpfile, "\n";
        open(TMP,">$tmpfile");
        print TMP sort(keys(%check));
        close(TMP);
        %check = ();
        $count = 0;
    }
}
close(FH);

open(RESULT,">result");
print RESULT sort(keys(%check));
close(RESULT);
foreach my $tmpfile (@tmpfiles) {
    open(RESULT,"<result");
    open(TMP,"<$tmpfile");
    open(RESULT2,">result2");
    my $s1 = <RESULT>;
    my $s2 = <TMP>;
    while ($s1 && $s2) {
        if ($s1 < $s2) {
            print RESULT2 $s1;
            $s1 = <RESULT>;
        }
        elsif ($s1 > $s2) {
            print RESULT2 $s2;
            $s2 = <TMP>;
        }
        else {
            print RESULT2 $s1;
            $s1 = <RESULT>;
            $s2 = <TMP>;
        }
    }
    while ($s1) {
        print RESULT2 $s1;
        $s1 = <RESULT>;
    }
    while ($s2) {
        print RESULT2 $s2;
        $s2 = <TMP>;
    }
    close(RESULT);
    close(RESULT2);
    close(TMP);
    rename "result2", "result";
    unlink $tmpfile;
}

id:wrash_d

回答いただきありがとうございます。なかなか良い感じなのですが残念ながらエラーが出ます。

エラーは、Argument "189X\n" isn't numeric in numeric it (<) at test.pl line 37, <TMP> line 1.

数字のみで行うと正常に動作するのですが、英字が混じると正常に動作していないようです。

以下は動作確認に使ったファイルです。

テストのため、1000000を2に変更しています。

改良できますでしょうか?

―file―

1890

1890

189X

189X

188X

X789

X678

X789

X789

1890

1890

189X

189X

188X

0000

X789

X678

X789

X789

―――

$count > 2

―――

2008/12/06 17:23:24

その他の回答(4件)

id:m_nagase No.1

nagase回答回数58ベストアンサー獲得回数82008/12/06 11:14:41

ポイント10pt

巨大なファイルをそのまま扱うのは効率が悪いと思うので、行の並びが変わってもいいのとディスクスペースが十分に空いていると言う前提のアイデアですが。

(1) ファイルを走査し各行の先頭文字毎のファイルに分割する。
(2) 分割したファイルがオンメモリで処理可能なサイズでなければ、各行の2番目の文字毎にファイルを分割する
(3) 全ての分割ファイルが適当なサイズになるまで繰り返す
(4) 分割ファイルごとに重複行を削除
(5) 最後に全てのファイルを結合

こんな感じの処理でどうでしょうか。

もっと上手い方法があるかもしれませんが。

後はDBにまるごとファイルを突っ込んで、クエリー発行するとか。

id:wrash_d

ディスクスペースは十分あります。

また、1行の文字数は、10文字(A-Z0-9)+改行(2バイト)です。

ただ、行数が膨大で困っています。

この場合、実際にperlで動くプログラムはどのようになりますか?

2008/12/06 12:16:42
id:pahoo No.2

pahoo回答回数5960ベストアンサー獲得回数6332008/12/06 11:19:10

ポイント10pt

各行のハッシュ値を計算し配列に入れていき、それを比較するという方法はどうでしょうか。

ハッシュ値には SHA1, MD5 など、幾つかの種類があります。SHA1のハッシュ長は20バイトなので、各行がそれより長ければ、メモリの節約になります。

ただし、ハッシュ値の計算には少し時間がかかります。


id:wrash_d

ディスクスペースは十分あります。

また、1行の文字数は、10文字(A-Z0-9)+改行(2バイト)です。

ただ、行数が膨大で困っています。

この場合、実際にperlで動くプログラムはどのようになりますか?

2008/12/06 12:16:36
id:zzz_1980 No.3

zzz_1980回答回数492ベストアンサー獲得回数642008/12/06 11:26:36

ポイント10pt

まさに sort <file1 |uniq >file2

でできますが、/tmp に 10Gbyte以上のあきが必要です。

(メモリのかわりにファイルシステム上に中間ファイルをつくりますので…)

id:wrash_d

ディスクスペースは十分あります。

また、1行の文字数は、10文字(A-Z0-9)+改行(2バイト)です。

ただ、行数が膨大で困っています。

この場合、実際にperl「特にwindows環境」で動くプログラムはどのようになりますかね?

2008/12/06 12:20:41
id:cicupo No.4

cicupo回答回数13ベストアンサー獲得回数32008/12/06 15:59:50ここでベストアンサー

ポイント140pt

以下のスクリプトでいかがでしょうか。

Windows環境でテストしていませんし、スペックも不明なのでどうか分かりませんが。

  • 入力ファイルは「file」
  • 出力ファイルは「result」
  • 「1000000」のところを適当に調整してください。大きすぎるとメモリの使用量が増えます。小さすぎると中間ファイルの個数が多くなってOS等の制限にひっかかる可能性があります。

でもフリーソフトの windows 版 uniq もたくさんありますねー。

#!/usr/bin/perl
use strict;
use warnings;

open(FH,"<file");
my @tmpfiles;
my %check;
my $count = 0;
while (<FH>) {
    if ($check{$_}) { next; }
    $check{$_} = 1;
    $count++;
    if ($count > 1000000) {
        my $tmpfile = "tmp_$#tmpfiles";
        push (@tmpfiles, $tmpfile);
        print $tmpfile, "\n";
        open(TMP,">$tmpfile");
        print TMP sort(keys(%check));
        close(TMP);
        %check = ();
        $count = 0;
    }
}
close(FH);

open(RESULT,">result");
print RESULT sort(keys(%check));
close(RESULT);
foreach my $tmpfile (@tmpfiles) {
    open(RESULT,"<result");
    open(TMP,"<$tmpfile");
    open(RESULT2,">result2");
    my $s1 = <RESULT>;
    my $s2 = <TMP>;
    while ($s1 && $s2) {
        if ($s1 < $s2) {
            print RESULT2 $s1;
            $s1 = <RESULT>;
        }
        elsif ($s1 > $s2) {
            print RESULT2 $s2;
            $s2 = <TMP>;
        }
        else {
            print RESULT2 $s1;
            $s1 = <RESULT>;
            $s2 = <TMP>;
        }
    }
    while ($s1) {
        print RESULT2 $s1;
        $s1 = <RESULT>;
    }
    while ($s2) {
        print RESULT2 $s2;
        $s2 = <TMP>;
    }
    close(RESULT);
    close(RESULT2);
    close(TMP);
    rename "result2", "result";
    unlink $tmpfile;
}

id:wrash_d

回答いただきありがとうございます。なかなか良い感じなのですが残念ながらエラーが出ます。

エラーは、Argument "189X\n" isn't numeric in numeric it (<) at test.pl line 37, <TMP> line 1.

数字のみで行うと正常に動作するのですが、英字が混じると正常に動作していないようです。

以下は動作確認に使ったファイルです。

テストのため、1000000を2に変更しています。

改良できますでしょうか?

―file―

1890

1890

189X

189X

188X

X789

X678

X789

X789

1890

1890

189X

189X

188X

0000

X789

X678

X789

X789

―――

$count > 2

―――

2008/12/06 17:23:24
id:tombe No.5

tombe回答回数38ベストアンサー獲得回数72008/12/06 19:23:27

ポイント10pt

tieを使うやる方です。

速度とのトレードオフはキャッシュサイズで調整してください。

use strict;
use Fcntl 'O_RDONLY';
use Tie::File;
my $INPUT_FILE = 'file';
my $OUTPUT_FILE = 'file2';
my $CACHE_SIZE = 2000000; # キャッシュ = 2M(デフォルト?)

open(OUT,">$OUTPUT_FILE");
tie  my @farry,
     'Tie::File',
     $INPUT_FILE,
     mode => O_RDONLY,
     memory => $CACHE_SIZE
     or die "Cant't open input file\n";;
for (my $linep = 0;$linep < ($#farry + 1);$linep++)
{
        my $searchp = 0;
        for (;$searchp < $linep;$searchp++)
        {
                last if $farry[$searchp] eq $farry[$linep];
        }
        print OUT $farry[$linep],"\n" if $searchp == $linep;
}
close(OUT);
id:wrash_d

回答いただきありがとうございます。

残念ながら、キャッシュサイズを500KBなど小さくしても、メモリの使用量がどんどん増え、エラーで終了します。

なお、当方の環境は、windows xp sp3,MEM 3GBです。

2008/12/06 19:37:37
  • id:zzz_1980
    sort して uniq ではまずいですかね。行の並びが変わりますけど。
  • id:wrash_d
    コメントありがとうございます。
    順番が変わることについては全く問題ありません。
    perl(windows,linux両環境)上で、膨大なメモリを食わずする方法があれば助かります。
    良い方法がありましたら、是非回答いただければ幸いです。
  • id:Mook
    Perl ではないので参考までにですが、下記のような記事もあります。
    http://codezine.jp/article/detail/2886?p=1

    できるのであれば Perl でもかまいませんが、一度ソートしたファイルを
    作成して、その上で処理をする方が良いような気がします。


    それから、質問の意図が今一つわからないのですが、file1 と file2 の関係は
    どのようなものでしょうか。
    それぞれのファイルの中身は重複なく、file2 から file1にあるものを削除
    したいということでしょうか?
  • id:wrash_d
    コメントありがとうございます。
    こんな記事もあるんですね。
    参考にさせていただきます。

    実は、今までは、フリーソフトでソートしていたのですが、外部ソフトがどんな動きをするのか予期できず、処理に若干の時間がかかっても、できれば、全てPERLで作りたいと思っています。

    なお、fileとfile2の関係については、
    fileで文字列の入力を行い、重複行のない出力をfile2へ行っています。
  • id:cicupo
    回答4です。バグがありました。
    「if ($s1 < $s2)」を「if ($s1 lt $s2)」に
    「if ($s1 > $s2)」を「if ($s1 gt $s2)」に
    それぞれ変更すると、問題なく動くかと思います。

    あとで気づきましたが質問内容に出力ファイル名は「file2」と書いてありましたね。
    「result」も「file2」にしていただければ問題ないと思います。
  • id:cicupo
    たびたびすみません。
    「my $tmpfile = "tmp_$#tmpfiles";」も
    「my $tmpfile = "tmp_" . @tmpfiles;」に
    変更してくださいませ。。
  • id:wrash_d
    cicupo 様
    ありがとうございました。
    無事解決しました。

この質問への反応(ブックマークコメント)

トラックバック

  • ymkoの日記 - [memo] 2011-11-26 15:19:16
    [memo] -PERLで巨大ファイル(10GB程度)の重複行を削除する方法を教えてく.. - 人力検索はてな
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません