Alat `uniq` tercepat di linux

Saya punya file teks besar (1,5 G),

Saya ingin tahu apa alat tercepat dan lebih dapat diandalkan di Linux.

Saya biasanya menggunakan:

awk '!x[$0]++' file.txt

Tetapi ketika saya menggunakan htopperintah saya melihat penggunaan memori saya meningkat.

Saya ingin tahu apa yang tercepat dan lebih dapat diandalkan untuk file besar.

uniq?
sort?
sed?
awk?

Mengapa?

Mari kita perhatikan bagaimana setiap solusi bekerja.

• uniqIni mengharuskan file sudah diurutkan. Jika tidak, Anda harus mem-pipe sortdulu, artinya sortharus membaca seluruh file ke dalam memori, menyusun ulang ( O(n log n)), dan kemudian menulisnya ke dalam pipa. Pekerjaannya uniqsangat murah, karena hanya perlu membandingkan jalur input yang berdekatan.

• sort -uIni menggabungkan karya sort | uniq. Ini harus mengumpulkan semua input unik ke dalam memori seperti yang dilakukan awkskrip, tetapi juga membuang waktu untuk menyortirnya sebelum menghasilkan output. Ini O(n log n), meskipun dalam hal ini nadalah jumlah item unik, tidak semua input. Jadi itu lebih baik daripada pipa.

• sedSaya tidak yakin mengapa Anda mendaftar ini, karena saya tidak bisa memikirkan cara yang baik untuk melakukan ini sedsama sekali. Mungkin jika Anda pertama kali mengurutkannya dan menyalurkannya ke sedskrip, ada cara untuk membandingkan garis yang berdekatan. Jadi sedhanya akan melakukan apa yang uniqdilakukan, dan uniqmungkin melakukannya seefisien mungkin.

• awkIni mungkin yang terbaik karena hanya melakukan sedikit pekerjaan yang diperlukan. Saat membaca setiap baris, ia melakukan pencarian hash yang efisien untuk melihat apakah garis tersebut sudah ada di memorinya, dan hanya menyimpan garis-garis unik sebagai kunci hash, dan penghitung sebagai nilainya. (Jika garis itu sebelumnya tidak ada, kondisinya akan benar, sehingga garis itu akan dicetak. Kalau tidak, garis itu tidak akan ada.) Ini menggunakan O(n)waktu dan O(uniq n)memori.

Setiap metode akan menggunakan sejumlah besar memori, baik untuk menyortir input atau melacak input yang telah dilihat sehingga mereka dapat menghapus duplikat.

Saya telah menemukan bahwa semacam itu tampaknya menjadi alat uniq tercepat seperti yang ditunjukkan di sini -> Cara tercepat untuk menghapus duplikat dalam daftar kata yang besar?

Saya hanya ingin menunjukkan bahwa gnu uniqtampaknya sangat lambat, bahkan pada daftar yang diurutkan.

Saya baru saja mencoba mendapatkan daftar awalan direktori dari daftar nama file yang diurutkan:

$ 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 tampaknya dua kali lebih cepat dari uniq, dan ini dengan sorting membaca dari stdin dan menulis ke stdout, jadi saya belum melihatnya melakukan paralelisasi. Saya tidak tahu mengapa uniq harus jauh lebih lambat daripada mengurutkan, karena tidak harus mengurutkan daftar ...

Outpuf dari perintah ini sangat kecil (ada banyak duplikat), hanya 264kb dan urutkan berakhir langsung setelah pv selesai.

Kecepatan yang sama tetap jika Anda memutar urutan perintah, aliran saya dibatasi oleh waktu cpu di sini, bukan akses disk dan cache (saya hanya memiliki 8GB RAM dan swap saya tidak digunakan)

Saya menjalankan ini pada mesin fedora 31 dengan semacam gnu coreutils dan uniq dan gnu awk; lokal diatur ke en_US.UTF-8

PEMBARUAN , karena ini sedikit menggelitik saya, saya melakukan beberapa tes lagi, mari kita potong bagian dari jalan, dan pastikan file diurutkan dengan baik

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

Ini membutuhkan 8,4 menit. Tes sekarang 7.9GB besar

mari kita jalankan alat-alat ini pada file daripada di dalam pipa, ini akan memungkinkan alat-alat ini untuk melakukan beberapa optimasi, seperti sort akan multi-thread. dan juga dari SSD yang lebih cepat.

Anda mungkin tidak memperhatikan bahwa pengurutan juga mengambil banyak memori, karena ia melakukan trik cerdas dengan file temp di / tmp yang mungkin tmpfs dan akan ada di ram Anda (Coba mengurutkan file yang lebih besar daripada / tmp, Anda akan lari ke ruang angkasa masalah, itu sebabnya saya perlu flag -T pada perintah di atas)

$ 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

Jadi sepertinya solusi awk Anda adalah yang tercepat dari 3 ini , dan sebenarnya menggunakan memori paling sedikit

pembaruan2 dan sekarang dengan lokal yang lebih sederhana

$ 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

Kali ini uniq memenangkan perlombaan ... sebagaimana Stéphane Chazelas mengisyaratkan dalam komentar, mengatur lokal Anda ke C membuat mengurutkan dan menyatukan sejumlah besar lebih cepat!