Linuxで最速の「uniq」ツール

各ソリューションの仕組みを考えてみましょう。

• uniqこれを行うには、ファイルがすでにソートされている必要があります。そうでない場合は、まずパイプを介して接続する必要がありますsort。つまり、sortファイル全体をメモリに読み込み、並べ替え（O(n log n)）してからパイプに書き込む必要があります。uniq入力の隣接する行だけを比較すれば、非常に安価に動作します。

• sort -uこれはタスクを結合しますsort | uniq。これはスクリプトのようにすべての一意の入力をメモリに収集する必要がありますawkが、出力を生成する前にそれらをソートするのに時間も無駄になります。O(n log n)この場合、n入力の総数ではなく、一意の項目数です。だからパイプよりも優れています。

• sed私はこれを行う良い方法を考えることができないので、なぜこれをリストしたのかわかりませんsed。おそらく最初にソートしてsedスクリプトにパイプすると、隣接する行を比較する方法があります。だから私たちは何をすべきかsed、できるだけ効率的に仕事をします。uniquniq

• awkこれは必要な最小限の操作しか実行しないため、おそらく最善です。各行を読み取るときに効率的なハッシュ検索を実行して、行がすでにメモリに存在することを確認し、一意の行のみをハッシュキーとして保存し、カウンタを値として保存します。 （行が以前に存在しなかった場合、条件は真であるため、行が印刷されます。そうでなければ印刷されません。）これはO(n)時間とO(uniq n)メモリを占有します。

各方法は、入力をソートしたり重複した項目を削除したりするために、表示された入力を追跡するために多くのメモリを使用します。

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 は stdin から読み込み、stdout に書き込む操作をソートする uniq よりも 2 倍多くの操作を実行しているように見えるため、並列化を実行するのを見たことはありません。 uniqがリストをソートする必要がないので、なぜソートよりもはるかに遅くするのかわかりません...

このコマンドの出力は非常に小さく（重複項目が多い）、わずか264kbで、pvが完了するとすぐにソートが終了します。

コマンドの順序を変更しても、速度は依然として同じです。ここでは、プロセスはディスクアクセスとキャッシュではなくCPU時間によって制限されます（8 GBのRAMのみがあり、スワップ領域は使用されません）。

私は、gnu coreutils sort、uniq、およびgnu awkを使用するfedora 31システムでロケールをen_US.UTF-8に設定して実行しています。

修正する、これは面白いので、切り取った部分を取り除き、ファイルがうまく整列されていることを確認することで、いくつかのテストをさらに実行しました。

cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test

8.4分かかります。テストは現在7.9GBです。

パイプライン以外のファイルでこれらのツールを実行してみましょう。これにより、これらのツールはより多くの最適化を実行できます。たとえば、ソートはマルチスレッドになります。また、より高速なSSDでも可能です。

sortがおそらくtmpfsであり、RAMにある/ tmpの一時ファイルを操作しているため、多くのメモリを占有していることに気付かなかったでしょう（/ 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ツールのようです -->大きな単語リストから重複項目を削除する最速の方法は何ですか？