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)メモリを占有します。

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