2億行の10GBファイルがあります。このファイルの一意の行を取得する必要があります。
私のコード:
while(<>) {
chomp;
$tmp{$_}=1;
}
#print...
私は2GBのメモリしか持っていません。どうすればこの問題を解決できますか?
質問する
2445 次
8 に答える
5
Davidの答えについてコメントしたように、データベースは道のりですが、DBM::Deep純粋なPerlであり、インストールと使用が簡単なため、データベースが良いかもしれません。基本的に、ファイルに関連付けられたPerlハッシュです。
use DBM::Deep;
tie my %lines, 'DBM::Deep', 'data.db';
while(<>) {
chomp;
$lines{$_}=1;
}
これは基本的にはすでに持っているものですが、ハッシュはメモリに保持されるのではなく、ファイル（ここではdata.db）に関連付けられたデータベースになりました。
于 2012-04-05T04:13:10.170 に答える
5
ほとんどの場合、行をキーとしてハッシュに格納できます。ただし、これだけ大きくなると、これは実際にはあまり効率的ではありません。この場合、データベースを使用する方がよいでしょう。
試してみるべきことの 1 つは、かつてUnix (BDB) に含まれていた Berkeley Databaseです。現在、オラクルが所有しているようです。
Perl は、BerkeleyDBモジュールを使用して BDB データベースと対話できます。実際、Perl ハッシュを BDB データベースに関連付けることもできます。これが完了すると、通常の Perl ハッシュを使用してデータベースにアクセスして変更できます。
BDB はかなり堅牢です。Bitcoins や SpamAssassin もこれを使用しているため、重複行を見つけるために作成しなければならないタイプのデータベースを処理できる可能性が非常に高くなります。DBD が既にインストールされている場合は、タスクを処理するプログラムを作成するのにそれほど時間はかかりません。それがうまくいかなくても、これで多くの時間を無駄にすることはありません。
私が考えることができる唯一の他のことは、より遅く、はるかに複雑な SQL データベースを使用することです。
補遺
たぶん私はこれを考え過ぎています...
単純なハッシュを試すことにしました。これが私のプログラムです：
#! /usr/bin/env perl
use strict;
use warnings;
use feature qw(say);
use autodie;
use constant DIR => "/usr/share/dict";
use constant WORD_LIST => qw(words web2a propernames connectives);
my %word_hash;
for my $count (1..100) {
for my $file (WORD_LIST) {
open my $file_fh, "<", DIR . "/$file";
while (my $word = <$file_fh>) {
chomp $word;
$word_hash{"$file-$word-$count"} = $word;
}
}
}
読み込まれたファイルには、合計で約 313,000 行が含まれています。これを 100 回実行して、31,300,000 個のキーを含むハッシュを取得します。それは可能な限り非効率的です。すべてのキーは一意になります。メモリの量は膨大になります。まだ...
出来た。プログラムが非常に非効率的であるにもかかわらず、実行に約 10 分かかり、約 6 ギガバイトに達しました。ただし、そのほとんどは仮想メモリにありました。奇妙なことに、それが実行され、メモリをむさぼり食い、CPU の 98% を占有していたにもかかわらず、私のシステムは実際にはそれほど遅くなりませんでした。問題は、実際にどのようなパフォーマンスを期待しているのかということだと思います。実行に約 10 分かかることがそれほど問題ではなく、このプログラムがそれほど頻繁に使用されるとは思わない場合は、単純にするために単純なハッシュを使用してください。
現在、Oracle から DBD をダウンロードし、コンパイルしてインストールしています。DBD を使用して同じプログラムを試し、何が起こるか見てみます。
BDB データベースの使用
作業を行った後、MySQL がインストールされていれば、Perl DBI を使用する方が簡単だと思います。そうしなければならなかった：
- Oracle から Berkeley DB をダウンロードするには、Oracle アカウントが必要です。パスワードを思い出せなかったので、メールで教えてくれました。メールを受け取ったことはありません。メールアドレスを思い出すのに10分かかりました。
- ダウンロードしたら、コンパイルする必要があります。Mac用にコンパイルするための指示を見つけましたが、それはかなり簡単に思えました。
- 実行中の CPAN がクラッシュしました。CPANが探している
/usr/local/BerkeleyDBことになり、としてインストールされまし/usr/local/BerkeleyDB.5.3た。リンクを作成すると、問題が修正されました。
全体として、BerkeleyDB をインストールするのに 1 時間に約 1/2 かかります。インストールしたら、私のプログラムを変更するのはかなり簡単でした。
#! /usr/bin/env perl
use strict;
use warnings;
use feature qw(say);
use autodie;
use BerkeleyDB;
use constant {
DIR => "/usr/share/dict",
BDB_FILE => "bdb_file",
};
use constant WORD_LIST => qw(words web2a propernames connectives);
unlink BDB_FILE if -f BDB_FILE;
our %word_hash;
tie %word_hash, "BerkeleyDB::Hash",
-Filename => BDB_FILE,
-Flags => DB_CREATE
or die qq(Cannot create DBD_Database file ") . BDB_FILE . qq("\n);
for my $count (1..10) {
for my $file (WORD_LIST) {
open my $file_fh, "<", DIR . "/$file";
while (my $word = <$file_fh>) {
chomp $word;
$word_hash{"$file-$word-$count"} = $word;
}
}
}
私がしなければならなかったのは、数行を追加することだけでした。
プログラムの実行はがっかりしました。速くはありませんでしたが、はるかに遅くなりました。純粋なハッシュを使用するとわずか 13 秒かかりましたが、2 分以上かかりました。
ただし、使用するメモリははるかに少なくなりました。古いプログラムは数ギガバイトを消費しましたが、BDB バージョンはわずか 1 メガバイトしか使用しませんでした。代わりに、20MB のデータベース ファイルを作成しました。
しかし、VM と安価なメモリの時代に、それは何かを成し遂げたのでしょうか? 仮想メモリと適切なメモリ処理がなかった昔は、プログラムがすべてのメモリを使用するとコンピュータがクラッシュしていました (メモリはギガバイトではなくメガバイトで測定されていました)。現在、プログラムが利用可能なメモリよりも多くのメモリを必要とする場合、単純に仮想メモリが与えられます。
したがって、結局、Berkeley データベースを使用することは良い解決策ではありません。を使用してプログラミング時間を節約したものtieはすべて、インストール プロセスで無駄になりました。そして、それは遅かった。
BDB を使用すると、メモリの代わりに DBD ファイルが使用されます。最新の OS は同じことを行い、より高速です。OS が処理するのに、なぜ作業を行うのでしょうか。
データベースを使用する唯一の理由は、システムに必要なリソースが実際にない場合です。2 億行は大きなファイルですが、最新の OS ではおそらく問題ないでしょう。システムに実際にリソースがない場合は、DBD データベースではなく、別のシステムの SQL データベースを使用してください。
于 2012-04-05T03:36:14.267 に答える
5
順序を維持することを気にしない場合は、以前に投稿されたソリューション (DBM::Deep など) よりも次の方法の方が速いと思います。
sort -u file
于 2012-04-05T04:47:32.790 に答える
4
各行のハッシュ コードを計算し、(ハッシュ、位置) マッピングを追跡することを検討してください。これには複雑なハッシュ関数 (または大きなハッシュ) は必要ありません。実際、主な関心事がメモリ使用量である場合は、「小さい」方が「よりユニーク」よりも優れています。CRC、または文字のコードの合計でさえ、そうかもしれません。要点は、この段階で一意性を保証することではありません。一致する候補を 2 億から数十に絞り込むだけです。
行ごとにハッシュを計算し、すでにマッピングがあるかどうかを確認します。その場合、そのハッシュに対応する位置ごとに、その位置の行を読み取り、行が一致するかどうかを確認します。それらのいずれかがある場合は、その行をスキップしてください。何もしない場合、またはそのハッシュのマッピングがない場合は、(ハッシュ、位置) を覚えてから行を出力してください。
「行番号」ではなく「位置」と言っていることに注意してください。これを 1 年以内に機能させるには、ほぼ確実に、#1392499 の行にたどり着くのではなく、正しい行を探す必要があります。
于 2012-04-05T03:09:42.273 に答える
3
時間/IO の制約もディスクの制約も気にしない場合 (たとえば、10 GB の空き容量がある場合)、次のダム アルゴリズムを実行できます。
1) ファイルを読み取ります (50 文字の行があるように聞こえます)。それをスキャンしながら、最長の行の長さを覚えておいて$Lください。
2) 最初の 3 文字を分析します (文字 #1 が同一であることがわかっている場合、たとえば"["、より多様な文字を持つ可能性が高い位置 N の 3 文字を分析します)。
3) $XYZ という 3 文字の行ごとに、その行をファイル 3char.$XYZ に追加し、そのファイルの行数をハッシュで保持します。
4) ファイル全体がこのように分割される場合、ファイル全体 (ファイルが AZ のみの場合は 26^3) の小さいファイルと、それぞれが 2GB を超える最大 4 つのファイルが必要です。
5) 元のファイルを「Processed」ディレクトリに移動します。
6) 大きなファイル (>2GB) ごとに、次の 3 文字の位置を選択し、ステップ #1 から #5 を繰り返します。新しいファイルは 6 文字です。$XYZABC
7) 泡立て、すすぎ、繰り返します。最終的には、次の 2 つのオプションのいずれかになります。
8a) それぞれが 2GB 未満で、すべてが相互に異なる文字列を持ち、それぞれ (そのサイズのために) 質問の標準的な「ハッシュへのスタッシュ」ソリューションによって個別に処理できる小さなファイルの束。
8b) または、ほとんどのファイルは小さくなっていますが、$L2 GB を超えるファイルに対して手順 7 を繰り返している間にすべての文字が使い果たされ、まだ 1 ～ 4 個の大きなファイルが残っています。何を推測してください-これらの最大4つの大きなファイルはファイル内の位置1..$Lに同一の文字を持っているため、質問の「ハッシュにスタッシュ」メソッドを使用して処理することもできます。そのサイズにもかかわらず、いくつかの異なる行が含まれています!
これには、最悪のディストリビューションでも10GB * L / 3ディスク容量が必要になる場合がありますが、手順 5 を「移動」から「削除」に変更した場合は、20GB のディスク容量しか必要ないことに注意してください。
出来上がり。終わり。
別のアプローチとして、行をハッシュすることを検討してください。私はハッシュの専門家ではありませんが、行を行サイズの IMHO の 5 倍未満のハッシュに圧縮できるはずです。
これにこだわりたい場合は、最初のパスで文字シーケンスの頻度分析を行い、次にこの方法で圧縮/エンコードを行います。
于 2012-04-05T02:59:27.110 に答える
1
より多くのプロセッサがあり、少なくとも 15 GB の空き容量があり、ストレージが十分に高速な場合は、これを試すことができます。これにより、並列で処理されます。
split --lines=100000 -d 4 -d input.file
find . -name "x*" -print|xargs -n 1 -P10 -I SPLITTED_FILE sort -u SPLITTED_FILE>unique.SPLITTED_FILE
cat unique.*>output.file
rm unique.* x*
于 2012-04-05T08:50:48.943 に答える
0
ファイルを 10 個の 1 Gbyte ファイルに分割し、一度に 1 つのファイルを読み取り、そのファイルから行をソートし、ソート後に書き戻すことができます。10 個のファイルすべてを開き、それらを 1 つのファイルにマージします (正しい順序でマージしていることを確認してください)。出力ファイルを開いて、一意の行を保存します。次に、マージ ファイルを一度に 1 行ずつ読み取り、最後の行を比較用に保持します。最後の行と現在の行が一致しない場合は、最後の行を書き出して、比較のために現在の行を最後の行として保存します。それ以外の場合は、マージされたファイルから次の行を取得します。これにより、すべての一意の行を含むファイルが得られます。
これを行うには時間がかかる場合がありますが、メモリが限られている場合は、ファイルを分割してその一部を処理することでうまくいきます。
ファイルを書き出すときに比較を行うことは可能かもしれませんが、それはもう少し複雑です。
于 2012-04-05T04:49:58.113 に答える
0
なぜこれに perl を使うのでしょうか? posix シェル:
sort | uniq
よし、ビールを飲みに行こう。
于 2012-04-05T04:50:14.867 に答える