多くの単語リストから重複した単語を削除する必要があります。いくつかのコマンドを試して調査しました。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)) になります。 、あなたが「説明された」方法で仕事をしていることは言うまでもありません:)
答え2
いくつかの深刻なスクリプト言語（Python / Perl / Raku、おそらくそのようなものである可能性が高い）を始める前に、使用方法を理解しようとしますsort -u（おそらく追加のスイッチがあります！）。他の選択肢は考慮しません。私が必要になるまで。