大きなテキストファイル（1.5G）があります。
Linux で最も高速で信頼性の高いツールは何かを知りたいです。
私は通常以下を使用します:
awk '!x[$0]++' file.txt
しかし、コマンドを使用すると、htopメモリ使用量が増加していることがわかります。
巨大なファイルに対して最も高速で信頼性の高いものは何かを知りたいです。
uniq?
sort?
sed?
awk?
なぜ？
答え1
それぞれのソリューションがどのように機能するかを考えてみましょう。
uniqこれには、ファイルが既にソートされている必要があります。そうでない場合は、sortまずパイプで処理する必要があります。つまり、 はsortファイル全体をメモリに読み込み、並べ替え (O(n log n))、パイプに書き込むuniq必要があります。 の処理は、入力の隣接する行を比較するだけでよいため、非常に低負荷です。sort -uこれは の作業を組み合わせますsort | uniq。これはスクリプトと同様にすべての一意の入力をメモリに収集する必要がありますawkが、出力を生成する前にそれらをソートする時間も浪費します。これは ですO(n log n)が、この場合は はn一意の項目の数であり、すべての入力ではありません。したがって、パイプよりも優れています。sedsedなぜこれをリストしたのかわかりません。これを行う良い方法がまったく思いつかないからです。おそらく、最初に並べ替えてsedスクリプトにパイプすると、隣接する行を比較する方法があります。したがって、できるsedことを実行するだけuniqで、uniqおそらく可能な限り効率的に実行できます。awkこれはおそらく、必要最小限の作業しか行わないため、最も効果的です。各行を読み込むときに、その行がすでにメモリ内にあるかどうかを確認するために効率的なハッシュ検索を実行し、一意の行のみをハッシュ キーとして、カウンタを値として保存します。(その行が以前に存在していなかった場合、条件は真となり、その行が印刷されます。そうでない場合は印刷されません。) これにはO(n)時間とO(uniq n)メモリが使用されます。
どのメソッドも、入力をソートするため、または重複を削除できるようにどの入力が見られたことを追跡するために、かなりの量のメモリを使用します。
答え2
uniqソートされたリストであっても、gnu はひどく遅いようだということを指摘したかっただけです。
ソートされたファイル名のリストからディレクトリプレフィックスのリストを取得しようとしました:
$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes
36.7GiB 0:07:41 [81.4MiB/s]
$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2
36.7GiB 0:03:14 [ 193MiB/s]
$ pv all_files | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3
36.7GiB 0:02:18 [ 270MiB/s]
sort -u は uniq の 2 倍の速さのようですが、これは sort が stdin から読み取り、stdout に書き込む場合なので、まだ並列化は行われていません。リストをソートする必要がないのに、なぜ uniq が sort よりもずっと遅いのかわかりません...
このコマンドの出力は非常に小さく (重複が多数あります)、わずか 264 KB で、pv が完了するとすぐにソートが終了します。
コマンドの順序を変えても同じ速度が維持されます。私のフローは、ディスク アクセスやキャッシュではなく、CPU 時間によって制限されます (RAM は 8 GB しかなく、スワップは使用されていません)。
私はこれをfedora 31マシンでgnu coreutils sortとuniq、gnu awkを使って実行しています。ロケールはen_US.UTF-8に設定されています。
アップデート、これはかなり興味深かったので、さらにテストを行いました。カット部分を取り除いて、ファイルがきちんと整理されていることを確認しましょう。
cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test
これには8.4分かかります。テストのサイズは7.9GBになりました
これらのツールをパイプではなくファイルで実行してみましょう。これにより、これらのツールは、ソートなどのさらなる最適化をマルチスレッドで実行できるようになります。また、より高速な SSD からも実行できるようになります。
sort も大量のメモリを消費していることに気付かないかもしれません。これは、/tmp 内の一時ファイル (tmpfs である可能性があり、RAM 内にあります) に対して巧妙なトリックを実行するためです (/tmp よりも大きいファイルをソートしようとすると、スペースの問題が発生します。そのため、上記のコマンドで -T . フラグが必要なのです)。
$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps
$ time awk '!x[$0]++' test > /dev/null
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps
$ time uniq test > /dev/null
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps
そうらしい、それっぽいあなたのawkソリューションはこれら3つの中で最も速いです、そして実際にメモリ使用量が最も少ない
アップデート2 そして今ではよりシンプルなロケールで
$ export LC_ALL=c
$ time sort -u test > /dev/null 1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k
$ time awk '!x[$0]++' test > /dev/null 1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps
$ time uniq test > /dev/null
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps
この時ユニークはレースに勝つ... Stéphane Chazelas がコメントで示唆しているように、ロケールを C に設定すると、sort と uniq が大幅に高速化されます。
答え3
ここに示されているように、ソートが最も高速な一意のツールであることがわかりました -->大きな単語リスト内の重複を削除する最も速い方法は何ですか?