☰

Windows で非常に大きな (800 GB) テキスト ファイルの内容を並べ替える

tag-icon • tag-icon windows sorting
Windows で非常に大きな (800 GB) テキスト ファイルの内容を並べ替える

私は文章各行に単語が 1 つずつ入ったファイルで、ファイルのサイズは 800 GB です。単語をアルファベット順に並べ替える必要があります。

私はウィンドウズ 選別使用するプログラム:

sort.exe input.txt /o output.txt

次のエラーが発生します:ソートを完了するためのメインメモリが不足しています。

私は32GBのラムそこで、次のようにしてソートに 10GB のメモリを指定してみることにします。

sort.exe input.txt /o output.txt /M 10000000

次のような結果になります:

警告: 指定されたメモリ サイズは、使用可能なページング メモリまで削減されています。

入力レコードが最大長を超えています。さらに大きい最大値を指定してください。

どのような選択肢がありますか?

答え1

どのような選択肢がありますか?

試すフリーウェアのコマンドラインソートユーティリティ CMSort。

複数の一時ファイルを使用し、最後にそれらを結合します。

CMsort は、調整されたメモリに達するまで入力ファイルのレコードを読み取ります。次に、レコードはソートされ、一時ファイルに書き込まれます。これは、すべてのレコードが処理されるまで繰り返されます。最後に、すべての一時ファイルが出力ファイルにマージされます。使用可能なメモリが十分であれば、一時ファイルは書き込まれず、マージも必要ありません。

あるユーザーは、130,000,000 バイトのファイルをソートしたと報告しています。

自分でコードを微調整したい場合は、巨大なテキスト ファイルの並べ替え - CodeProject- 「使用可能なメモリを超えるサイズのテキスト ファイル内の行をソートするアルゴリズム」

答え2

もう 1 つのオプションは、ファイルをデータベースにロードすることです。たとえば、MySQL や MySQL Workbench などです。
データベースは、大きなファイルを扱うのに最適です。

入力ファイルに改行で区切られた単語だけが含まれている場合、これはそれほど難しくありません。

データベースと MySQL Workbench をインストールしたら、次の操作を行う必要があります。

まず、スキーマを作成します (単語の長さが 255 文字を超えないことを前提としていますが、引数の値を増やすことでこれを変更できます)。

最初の列「idwords」は主キーです。

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

次に、データをインポートします。
たとえば、すべての単語がテーブルにインポートされます。この手順は完了するまでに時間がかかる場合があります。最初に小さいファイルでテストを実行し、形式が大きなファイルと同じであることを確認したら (テーブルを切り捨てる、つまりテーブルをクリアして完全なデータ セットをロードする) ことをお勧めします。

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);

このリンクは、ロードに適した形式を取得するのに役立つ場合があります。 ロードデータ

たとえば、最初の行をスキップする必要がある場合は、次のようにします。

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

最後に、ソートされたファイルを保存します。PC によっては、これにも時間がかかる場合があります。

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

必要に応じて自由にデータを検索することもできます。
たとえば、最初の 50 語が昇順 (ゼロの位置または最初の単語から開始) で表示されます。

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

答え3

sort

順序付けられたファイルと順序付けられていないファイルをソートするために使用されるアルゴリズムは多数あります[1これらのアルゴリズムはすべてすでに実装さ
れているため、すでにテスト済みのプログラムを選択します。

でコアユーティリティ （Linux用ですが、Windows用も利用可能です[2] ) 、sortマルチコアプロセッサで並列実行できるコマンドが存在します。通常はそれで十分です。

ファイルがとても大きい処理を分割（split -l）し、ファイルをいくつかのチャンクに分割し、並列オプション（--parallel）を使用して、結果を並べ替えることもできます。順序付けられたチャンクオプション-m（マージソート）。
その方法の一つが説明されている。ここ(ファイルの分割、単一チャンクの順序付け、順序付けされたチャンクの結合、一時ファイルの削除)。

ノート：

  • Windows 10には、いわゆるLinux 用 Windows サブシステムすべての Linux の例がより自然に見えます。
  • 異なるアルゴリズムによるソートでは、ソートするデータエントリの数に応じて実行時間が異なります (O(n m )、O(nlogn)...)。
  • アルゴリズムの効率は、元のファイルにすでに存在する順序に依存します。
    （たとえば、バブルソートすでに順序付けされたファイル（正確には N 個）に対しては最も高速なアルゴリズムですが、他の場合には効率的ではありません。

答え4

各行の単語が限られた語彙（英語など）からのものである場合は、TreeMap を使用してカウントを記録し、リストを O(n + m log m) 時間で並べ替えることができます（ここで、m は一意の値の数です）。

それ以外の場合はJavaライブラリを使用できますビッグソーター入力をソートされた中間ファイルに分割し、効率的にマージします (全体で O(nlogn))。ファイルをソートするには、次のようになります。

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

私はランダムに生成された 16 文字の単語を含む 1.7 GB のファイル (1 億行) を作成し、上記のように 142 秒でソートしました。私が使用している方法の計算複雑度 O(n log n) に基づくと、SSD を搭載した i5 2.3GHz ラップトップでシングルスレッドで 800 GB の 16 文字の単語をソートするには約 24 時間かかると見積もっています。

関連情報