Saya perlu menduplikat daftar kata yang besar. Saya mencoba beberapa perintah dan melakukan penelitian di sini dan di sini di mana mereka menjelaskan bahwa cara tercepat untuk mendeduplikasi daftar kata tampaknya menggunakan awk.

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

Namun saya menemukan bahwa ini sepertinya tidak benar. Inilah hasil pengujian saya:

sort -u input.txt -o output.txt 

pengguna 0m12.446 s nyata 0m11.347
sys 0m0.906s

awk '!x[$0]++' input.txt > output.txt

nyata 0m47.221s
0m45.419s pengguna
sys 0m1.260s

Jadi menggunakan sort -u adalah 3,7 kali lebih cepat. Kenapa ini? apakah ada metode yang lebih cepat untuk melakukan deduplikasi?

*********** Pembaruan ********

Seperti yang ditunjukkan oleh seseorang di komentar, bisa jadi daftar kata saya sudah diurutkan sampai batas tertentu. Untuk mengecualikan kemungkinan ini, saya membuat dua daftar kata menggunakan skrip python ini .

List1 = 7 Mb
List2 = 690 Mb

Hasil AWK:
List1
real 0m1.643s
pengguna 0m1.565s
sys 0m0.062s

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

Hasil SORT:
List1
nyata 0m0.724s
pengguna 0m0.666s
sys 0m0.048s

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

Anda mengajukan pertanyaan yang salah, atau mengajukan pertanyaan dengan salah dan di tumpukan yang salah, ini adalah pertanyaan yang lebih baik untuk ditanyakan dalam pemrograman / stack-overflow bagi orang-orang untuk memberi Anda jawaban berdasarkan algoritma yang digunakan dalam awk dan sortir.

PS: lakukan juga yang diperlukan dengan nawk, mawk, dan gawk untuk memberi kita lebih banyak detail ke "zona menjadi";) dan lakukan berlari seperti masing-masing 100 kali dengan min, maks, rata-rata, dan standar deviasi.

Setiap kasus kembali ke pertanyaan yang ada, dari CompSci 210, ini tentang algoritma yang digunakan. Sortir menggunakan beberapa, tergantung pada ukuran, dan batasan memori yang dihadapinya untuk menyimpan file ke disk dalam file sementara untuk digabung setelah kehabisan memori, dan Anda harus melihat ke dalam kode sumber untuk melihat apa perintah sort (1) spesifik digunakan pada OS spesifik tempat Anda menjalankannya, tetapi dari pengalaman memuat sebanyak mungkin, lakukan semacam sortir cepat, tulis ke disk, bilas ulangi, dan pada saat akhir itu akan melakukan semacam penggabungan file kecil yang diurutkan. Jadi di sini Anda akan memiliki O (n * log2 (N)) untuk bagian-bagian, dan kemudian perkiraan O (n * log (n)) operasi penggabungan

awk: Mekanisme x [$ 0] ++ adalah "kira" untuk menggunakan hashing. TETAPI masalah dengan hashing, seharusnya operasi "lookup" O (1), adalah tabrakan, dan penanganan tabrakan. Ini dapat menyebabkan masalah ketika data tidak menyebar dengan baik, atau mengisi ember dll. Dan dalam daftar besar, hashing mungkin menjadi masalah memori besar jika penanganan tabrakan tidak dilakukan dengan benar (dan Anda mungkin perlu tune algoritma hashing untuk data yang diharapkan), dan kemudian Anda perlu melihat kinerja fungsi hashing aktual dan kemudian O (1) mungkin lebih dekat ke O (log (n)) untuk menyisipkan (Ie. O (1) untuk pencarian pertama, dan jika TIDAK ada Anda menambahkannya yang bisa menjadi O (log (n))), dan kemudian n * O (1) menjadi * O (log (n)) = > O (n * log (n)), belum lagi Anda juga melakukan hal-hal dengan cara "ditafsirkan" :)

Perbedaan kecepatan adalah karena 'sort' adalah perintah ( tautan ), sedangkan 'awk' adalah bahasa pemrograman ( tautan ).

Perintah 'sort' adalah mengambil input dan mengembalikan output. Sedangkan 'awk' adalah bahasa pemrograman, yang pertama menginterpretasikan kode (perintah terminal) kemudian mulai memprosesnya. Sederhana seperti itu.