20

Linux で数百万行の文字列を含む大きなファイルをシャッフルしたいと考えています。「sort -R」を試してみましたが、非常に遅いです (16M の大きなファイルで 50 分ほどかかります)。代わりに使用できるより高速なユーティリティはありますか?

4

3 に答える 3

3

あなたの説明に基づいて、50分はソートの実際のメカニズムによって引き起こされたものではありません. /dev/random十分なエントロピーが生成されるまでの待機に時間が費やされる可能性があります。

1 つの方法は、ランダム データの外部ソース (たとえば、 http://random.org ) をSchwartzian Transformのバリエーションと共に使用することです。Schwartzian Transform は、並べ替え対象のデータを、並べ替えキーが埋め込まれた「強化された」データに変換します。データはキーを使用してソートされ、キーは破棄されます。

これを問題に適用するには：

  • ソートするファイルと同じ行数で、1 行に 1 つずつ乱数を含むテキスト ファイルを生成します。これはいつでも実行でき、バックグラウンドで実行したり、別のサーバーで実行したり、random.org からダウンロードしたりできます。ポイントは、ソートしようとしている間はこのランダム性が生成されないことです。

  • 次を使用して、ファイルの強化されたバージョンを作成しますpaste。

    paste random_number_file.txt string_data.txt > tmp_string_data.txt

  • このファイルを並べ替えます:

    sort tmp_string_data.txt > sorted_tmp_string_data.txt

  • ランダム データを削除します。

    cut -f2- sorted_tmp_string_data.txt > random_string_data.txt

これが基本的な考え方です。試してみたところうまくいきましたが、1,600 万行のテキストや 1,600 万行の乱数がありません。すべてをディスクに保存するのではなく、これらのステップの一部をパイプライン処理したい場合があります。

于 2013-02-07T06:06:16.820 に答える
0

私のツールを試すことができます: HugeFileProcessor。妥当な時間内に数百 GB のファイルをシャッフルできます。

シャッフルの実装の詳細は次のとおりです。出力への書き込み時に RAM に保持する行数 - batchSizeを指定する必要があります。合計シャッフル時間は(sourceFile の行数) / batchSize * (sourceFile を完全に読み取る時間) になるため、(RAM が不足していない限り) 多いほど良いです。プログラムは、バッチごとではなく、ファイル全体をシャッフルすることに注意してください。

アルゴリズムは次のとおりです。

  1. sourceFileの行数を数えます。これは、ファイル全体を 1 行ずつ読み取るだけで実行できます。(ここでいくつかの比較を参照してください。)これは、ファイル全体を 1 回読み取るのにかかる時間の測定値も示します。したがって、 Ceil(linesCount / batchSize)の完全なファイル読み取りが必要になるため、完全なシャッフルを行うには何回かかるかを見積もることができます。

  2. 合計linesCountがわかったので、linesCountサイズのインデックス配列を作成し、Fisher-Yates (コードではorderArrayと呼ばれます) を使用してそれをシャッフルできます。これにより、シャッフルされたファイルに行を入れたい順序が得られます。これは、バッチやチャンクなどごとではなく、ファイル全体にわたるグローバルな順序であることに注意してください。

  3. では実際のコードです。計算したばかりの順序でsourceFileからすべての行を取得する必要がありますが、メモリ内のファイル全体を読み取ることはできません。したがって、タスクを分割するだけです。

    • sourceFileを調べてすべての行を読み取り、orderArrayの最初のbatchSizeにある行だけをメモリに格納します。これらすべての行を取得したら、必要な順序でそれらをoutFileに書き込むことができます。これは、完了した作業のbatchSize / linesCountです。
    • 次に、orderArray の次の部分を取得し、各部分の最初から最後まで sourceFile を読み取るプロセス全体を何度も繰り返します。最終的にorderArray全体が処理され、完了です。

なぜそれが機能するのですか？

ソースファイルを最初から最後まで読むだけだからです。前方/後方へのシークはありません。それが HDD の好みです。ファイルは、内部 HDD バッファー、FS ブロック、CPU キャッシュなどに従ってチャンクで読み取られ、すべてが順次読み取られます。

いくつかの数字

私のマシン (Core i5、16GB RAM、Win8.1、HDD Toshiba DT01ACA200 2TB、NTFS) では、3 500 000 のbatchSizeを使用して、約 5 時間で 132 GB (84 000 000 行) のファイルをシャッフルすることができました。 2 000 000 の約 8 時間かかりました。読み取り速度は、毎秒約 118000 行でした。

于 2016-08-07T10:28:13.477 に答える