☰

***********更新********

tag-icon • tag-icon bash awk performance sort
***********更新********

多くの単語リストから重複した単語を削除する必要があります。いくつかのコマンドを試して調査しました。Linuxで最速の「uniq」ツールそして大容量GBテキストファイルから重複行を削除するには？重複した単語のリストを削除する最速の方法はを使用しているようですawk。

awk  --> O(n) ?
sort --> O(n log n) ?

しかし、私はこれが本当ではないようだと思った。私のテスト結果は次のとおりです。

time sort -u input.txt -o output.txt 
real    0m12.446s  
user    0m11.347s  
sys 0m0.906s**


time awk '!x[$0]++' input.txt > output.txt
real    0m47.221s  
user    0m45.419s  
sys 0m1.260s

そのため、使用sort -u速度が3.7倍速くなりました。なぜこれですか？重複排除を実行するより高速な方法はありますか？

***********更新********

誰かがコメントで指摘したように、おそらく私の単語リストはすでに何らかの方法でソートされているかもしれません。これらの可能性を排除するために、以下を使用して2つの単語のリストを作成しました。乱数語彙ジェネレータ.py。

List1 = 7 Mb  
List2 = 690 Mb

**Results AWK:**  
***List1***  
real    0m1.643s  
user    0m1.565s  
sys     0m0.062s

***List2***  
real    2m6.918s  
user    2m4.499s  
sys     0m1.345s

**Results SORT:**  
***List1***  
real    0m0.724s  
user    0m0.666s  
sys     0m0.048s

***List2***  
real    1m27.254s  
user    1m25.013s  
sys     0m1.251s

ベストアンサー1

間違った質問をしたり、間違ったスタックにいる場合は、awkとソートに使用されるアルゴリズムに基づいて回答を提供できるように、プログラミング/スタックオーバーフローで質問することをお勧めします。

PS：nawk、mawk、およびgawkを使用して必要な操作を実行して、より多くの「ゾーン指定」詳細を提供し、最小、最大、平均、および標準偏差を使用してそれぞれ100回実行することもできます。

とにかくCompSci 210の現在の質問に戻ると、使用されているアルゴリズムに関連しています。 Sortは、メモリが不足しているときにマージソートを可能にするために、サイズとメモリの制限に応じてさまざまな方法を使用してファイルをディスク上の一時ファイルに保存します。します。実行中の特定のOSで使用されていますが、経験的にできるだけメモリにロードし、クイックソートを実行し、ディスクに書き込んで重複エントリをフラッシュして、最後に実行します。小さなソートファイルのマージソート。したがって、ここでは個々の部品に対してO（n * log2（N））を取得し、おおよそのO（n * log（n））マージ操作を実行します。

awk:x[$0]++ メカニズムはハッシュ使用を「仮定」します。しかし、ハッシング（O（1）「照会」操作と仮定）の問題は、競合とその処理です。これにより、データがうまく分散されず、バケットがいっぱいにならない場合に問題が発生する可能性があり、大きなリストで競合が正しく処理されない場合、ハッシュが大きなメモリの問題になる可能性があります（予想されるターゲットを指定する必要があるかもしれません）。データ調整ハッシュアルゴリズム）、実際のハッシュ関数のパフォーマンスを見てください。その後、O（1）はおそらく挿入のためにO（log（n））に近づくでしょう（つまり、最初の検索の場合はO（1）の場合）、存在しない場合はO（log（n）））追加すると、n*O(1) は *O(log(n))=> O(n*log(n)) になります。 、あなたが「説明された」方法で仕事をしていることは言うまでもありません:)

おすすめ記事