Alat `uniq` tercepat di linux

8

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?

MLSC
sumber
Sudahkah Anda mencoba menjalankannya, mungkin dengan time?
choroba
waktu adalah penting dan juga penggunaan dan keandalan memori (maksud saya mana yang melakukan pekerjaannya dengan akurat)
MLSC
Belum ... Tapi saya melakukan beberapa tes sebelumnya ... dan bertanya di suatu tempat, beberapa orang mengatakan kepada saya bahwa awk adalah yang terbaik..tapi di htop ... Saya melihat penggunaan memori meningkat
MLSC
3
@MortezaLSC: Ini adalah trade off. Semakin cepat programnya, semakin banyak memori yang digunakan.
cuonglm

Jawaban:

16

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.

Barmar
sumber
1
+1 Penjelasan mengenai awkjuga menjelaskan mengapa menggunakan jumlah memori yang meningkat. Apa pun yang melakukan pengurutan akan berakhir dengan melakukan ini juga, hanya 1) itu mungkin akan menggunakannya sekaligus, 2) itu mungkin menggunakan sedikit lebih banyak, tergantung pada jumlah kunci yang unik vs digandakan.
goldilocks
@Barmar Maaf, Tetapi ketika saya memiliki file besar (16 G) dengan kapasitas memori 8G, Jadi apa yang akan terjadi dengan memori saya?
MLSC
8
@goldilocks, menggunakan sortfile-file sementara (dengan cara yang cerdas) untuk menghindari pengisian memori. Penggunaan memorinya terikat. Batas dibatasi dengan beberapa implementasi semacam. Lebih efisien jika membiarkan sistem menukar memori secara acak ke disk (yang juga memengaruhi aplikasi pada sistem).
Stéphane Chazelas
Itu benar. Jadi jika Anda mengalami kasus di mana awkkehabisan memori, sortmungkin satu-satunya solusi karena telah dirancang untuk menangani ini. Di sisi lain, semua disk membaca dan menulis akan memperlambatnya, sehingga mungkin akan memakan waktu lama untuk menyelesaikannya. Jika Anda berurusan dengan data dalam jumlah besar, Anda mungkin harus menggunakan DBMS daripada file teks.
Barmar
@Barmar Bagaimana Anda menyimpulkan bahwa waktu pemesanan ulang meningkat O(n log n)? Atau Anda tahu dari mana saja?
jimmij
0

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!

Jens Timmerman
sumber
Apa implementasi dari sortdan uniq? Lokal apa?
Stéphane Chazelas