0

最大 2 億行 (通常は約 2000 万行) と 2 つの列を持つ巨大なタブ区切りファイルがあります。最初の列には最大 40 文字の ASCII 単語が含まれ、2 番目の列には整数が含まれます。

次の手順を実行したいと思います。

  1. 最初の列で並べ替え
  2. 重複する行を削除して、すべての行を一意にします
  3. 最初の列の指定されたエントリのすべての行を読み取る

3 GB のメモリ制限があり (すべてのデータをハッシュに読み込むことはできません)、無制限のハード ディスク領域があり、単一のコアでスクリプトを実行したいと考えています。いくつかのスクリプトを並行して実行するつもりなので、ハード ディスクの読み取りおよび書き込み操作が高すぎないようにする必要があります。

ファイルのサイズを考慮して、(Perl で) 私のスクリプトの実装をどのように進める必要がありますか?

ファイルのサイズを考慮して、最初のステップにどのアルゴリズムをお勧めしますか?

ステップ 3 は、私が考える最も複雑な部分です。これをどのように処理すればよいですか？索引付けアルゴリズムに精通していません。問題に最適なものを提案していただけますか？使用できる Perl モジュールはありますか?

最初にファイルをバイナリ ファイルに変換することは理にかなっていますか (SAM を BAM に変換するなど)。はいの場合、そのようなファイルを変換および処理するための指示またはアルゴリズムはありますか?

4

2 に答える 2

1

システムソートを使用してファイルをソートします。最新のGNUSortには並列オプションがあります。uniqを実行してから、ソートされたファイルを一度に1行ずつ読み取り、最初の列がいつ変更されるかを確認するのは簡単です。並べ替えでは、ファイルを小さなチャンクに分割して並べ替えてからマージする並べ替え/マージアルゴリズムを使用するため、ディスクが十分にある限り、速度以外のメモリは問題になりません。

于 2012-04-08T15:27:26.963 に答える
1

ファイル全体をSQLiteデータベースに読み込むのは、私の最初の試みです。

次のようにテーブルを定義します。

create table mytuples (
    mykey varchar(40),
    myval integer,
    constraint tuple_pk primary key(mykey, myval) on conflict ignore
);

挿入エラーを無視するDBIを使用した単純なスクリプトで実行できます。

未テスト、エラーチェック省略

#!/usr/bin/env perl

use strict; use warnings;
use autodie;

use DBI;

my ($infile) = (@ARGV);

open my $in, '<', $infile;

my $dbh = DBI->connect('dbi:SQLite:some.db', undef, undef, {
        AutoCommit => 0,
        RaiseError => 0,
    },
);

while (my $line = <$in>) {
    my ($key, $val) = split ' ', $line;
    $dbh->do(q{INSERT INTO mytuples VALUES(?, ?)}, undef, $key, $val);
}

$dbh->commit;
$dbh->disconnect;

これは、初期処理のコマンド ラインよりも遅くなる可能性がありますが、SQL を自由に使用できるという柔軟性を評価することができsortます。grep

于 2012-04-08T14:14:33.917 に答える