Cara tercepat dan paling efisien untuk mendapatkan jumlah catatan (baris) dalam file yang dikompresi gzip

16

Saya mencoba melakukan hitungan catatan pada file gzip 7,6 GB. Saya menemukan beberapa pendekatan menggunakan zcatperintah.

$ zcat T.csv.gz | wc -l
423668947

Ini berfungsi tetapi butuh terlalu banyak waktu (lebih dari 10 menit untuk menghitungnya). Saya mencoba beberapa pendekatan seperti

$ sed -n '$=' T.csv.gz
28173811
$ perl -lne 'END { print $. }' < T.csv.gz
28173811
$ awk 'END {print NR}' T.csv.gz
28173811

Ketiga perintah ini menjalankan cukup cepat tetapi memberikan hitungan yang salah dari 28173811.

Bagaimana saya bisa melakukan penghitungan catatan dalam jumlah waktu minimal?

Rahul
sumber
5
Mengapa Anda perlu menghitung jumlah catatan? Jika Anda mencoba menghitungnya sebelum memprosesnya, itu berarti Anda harus mengompres file dua kali.
Andrew Henle
3
Info lebih lanjut tentang mengapa Anda melakukan ini akan sangat membantu. Jika ini sesuatu yang sedang berlangsung - yaitu, Anda secara teratur memampatkan banyak file, dan di beberapa waktu kemudian perlu mengetahui jumlah catatan - mengapa tidak menghitungnya saat dikompresi, dan menyematkan nomor dalam nama file?
jamesqf
3
Membaca file 9,7GB dari disk mekanis secara inheren lebih lambat. Simpan file di SSD, dan lihat seberapa cepat gunzip / zcat berjalan. Tetapi seperti yang dikatakan @jamesqf, simpan linecount di namafile, atau dalam file di tgz, dan mengekstrak file itu akan jauh lebih cepat.
ChuckCottrill
2
Ada alasan teoritis yang bagus mengapa Anda tidak bisa menghindari pekerjaan ini. Format kompresi yang memungkinkan Anda menentukan beberapa properti yang berguna dari data "tanpa mendekompresinya" secara definisi tidak terlalu baik untuk format kompresi :)
hobbs

Jawaban:

28

Perintah sed, perldan awkyang Anda sebutkan mungkin benar, tetapi mereka semua membaca data yang dikompresi dan menghitung karakter baris baru di dalamnya. Karakter baris baru ini tidak ada hubungannya dengan karakter baris baru dalam data yang tidak terkompresi.

Untuk menghitung jumlah baris dalam data yang tidak dikompresi, tidak ada jalan lain untuk mengompresnya. Pendekatan Anda dengan zcatadalah pendekatan yang benar dan karena datanya sangat besar, akan membutuhkan waktu untuk mengompresnya.

Sebagian besar utilitas yang berhubungan dengan gzipkompresi dan dekompresi kemungkinan besar akan menggunakan rutinitas shared library yang sama untuk melakukannya. Satu-satunya cara untuk mempercepatnya adalah dengan menemukan implementasi dari zlibrutinitas yang entah bagaimana lebih cepat daripada yang default, dan membangun kembali mis zcatuntuk menggunakannya.

Kusalananda
sumber
11
Ini akan menjadi latihan pemrograman non-sepele, tetapi bisa dilakukan. Intinya adalah untuk tidak membangun kembali zcat. Bagian penting dari pekerjaan zcatmenghasilkan keluaran aktual. Tetapi jika Anda hanya menghitung \nkarakter, itu tidak perlu. gzipkompresi pada dasarnya bekerja dengan mengganti string panjang umum dengan string lebih pendek. Jadi, Anda hanya perlu peduli dengan string panjang dalam kamus yang berisi \n, dan menghitung kemunculan (terbobot) dari mereka. Misalnya karena aturan bahasa Inggris, .\nadalah string 16 bit yang umum.
MSalters
19

Gunakan unpigz.

Jawabannya Kusalananda adalah benar, Anda akan perlu untuk uncompress bahwa seluruh file untuk memindai isinya. /bin/gunzipmelakukan ini secepat mungkin, pada satu inti. Pigz adalah implementasi paralel gzipyang dapat menggunakan banyak core.

Sayangnya, dekompresi itu sendiri dari file gzip normal tidak bisa diparalelkan, tapi pigzmemang menawarkan versi perbaikan dari gunzip, unpigz, yang melakukan pekerjaan terkait seperti membaca, menulis, dan menghitung checksum di thread terpisah. Dalam beberapa tolok ukur cepat, unpigzhampir dua kali lebih cepat gunzipdari pada mesin i5 inti saya.

Instal pigzdengan pengelola paket favorit Anda, dan gunakan unpigzsebagai ganti gunzip, atau unpigz -calih-alih zcat. Jadi perintah Anda menjadi:

$ unpigz -c T.csv.gz | wc -l

Semua ini mengasumsikan bottleneck adalah CPU, bukan disk, tentu saja.

marcelm
sumber
4
pigzHalaman manual saya menyatakan bahwa Dekompresi tidak dapat diparalelkan, setidaknya tidak tanpa aliran deflate yang disiapkan khusus untuk tujuan itu. Akibatnya, pigz menggunakan utas tunggal (utas utama) untuk dekompresi, tetapi akan membuat tiga utas lainnya untuk membaca, menulis, dan memeriksa perhitungan, yang dapat mempercepat dekompresi dalam beberapa keadaan . Namun, seperti Anda, saya menemukan itu setidaknya dua kali lebih cepat daripada gzip, jika bukan karena paralelisme
Stéphane Chazelas
@ StéphaneChazelas Poin bagus! Itu menjelaskan percepatan yang agak mengecewakan untuk dekompresi. Saya mengedit posting saya untuk mencerminkan informasi ini dengan lebih baik.
marcelm
5

Masalah dengan semua pipa adalah bahwa Anda pada dasarnya menggandakan pekerjaan. Tidak peduli seberapa cepat dekompresi itu, data masih harus di-shuttled ke proses lain.

Perl memiliki PerlIO :: gzip yang memungkinkan Anda untuk membaca stream gzip secara langsung. Oleh karena itu, itu mungkin menawarkan keuntungan bahkan jika kecepatan dekompresi mungkin tidak cocok dengan unpigz:

#!/usr/bin/env perl

use strict;
use warnings;

use autouse Carp => 'croak';
use PerlIO::gzip;

@ARGV or croak "Need filename\n";

open my $in, '<:gzip', $ARGV[0]
    or croak "Failed to open '$ARGV[0]': $!";

1 while <$in>;

print "$.\n";

close $in or croak "Failed to close '$ARGV[0]': $!";

Saya mencobanya dengan file terkompresi 13 MB gzip (didekompresi menjadi 1,4 GB) pada 2010 MacBook Pro lama dengan 16 GB RAM dan ThinkPad T400 lama dengan 8 GB RAM dengan file yang sudah ada dalam cache. Di Mac, skrip Perl secara signifikan lebih cepat daripada menggunakan saluran pipa (5 detik vs 22 detik), tetapi pada ArchLinux, ia kalah karena unpigz:

$ time -p ./gzlc.pl spy.gz 
1154737
nyata 4.49
pengguna 4.47
sys 0,01

melawan

$ time -p unpigz -c spy.gz | wc -l
1154737
nyata 3.68
pengguna 4.10
sys 1.46

dan

$ time -p zcat spy.gz | wc -l
1154737
nyata 6.41
pengguna 6.08
sys 0,86

Jelas, menggunakan unpigz -c file.gz | wc -ladalah pemenang di sini baik dari segi kecepatan. Dan, baris perintah sederhana itu pasti mengalahkan penulisan program, betapapun pendeknya.

Sinan Ünür
sumber
1
Saya pikir Anda sangat melebih-lebihkan sumber daya yang diperlukan untuk memindahkan data antara dua proses, dibandingkan dengan perhitungan dekompresi. Coba lakukan tolok ukur berbagai pendekatan;)
marcelm
2
@ SinanÜnür Pada sistem Linux x86_64 saya (juga perangkat keras lama) gzip | wcmemiliki kecepatan yang sama dari skrip perl Anda. Dan pigz | wcdua kali lipat lebih cepat. gzipberjalan dengan kecepatan yang sama, terlepas dari apakah saya menulis output ke / dev / null atau pipa ke wcApa yang saya yakini adalah "pustaka gzip" yang digunakan oleh perl lebih cepat daripada alat baris perintah gzip. Mungkin ada masalah khusus Mac / Darwin lainnya dengan pipa. Masih luar biasa bahwa versi perl ini kompetitif sama sekali.
rudimeier
1
Di instal x86_64 Linux saya, sepertinya lebih baik zcatdan lebih buruk daripada unpigz. Saya kagum pada seberapa cepat pipeline pada sistem Linux dibandingkan dengan Mac. Saya tidak mengharapkan itu, meskipun saya seharusnya seperti yang pernah saya amati program yang sama berjalan lebih cepat pada CPU Linux VM terbatas pada Mac yang sama daripada pada bare metal.
Sinan Ünür
1
Itu menarik; pada sistem saya (Debian 8.8 amd64, quad core i5), skrip perl sedikit lebih lambat ... File 109M .gz didekompresi menjadi 1.1G teks, secara konsisten membutuhkan 5,4 detik untuk zcat | wc -l, dan 5,5 detik untuk skrip perl Anda. Jujur, saya kagum dengan variasi yang dilaporkan orang di sini, terutama antara Linux dan MacOS X!
marcelm
Saya tidak tahu apakah saya bisa menggeneralisasi apa yang saya lihat di Mac saya, sesuatu yang aneh sedang terjadi. Dengan file 1,4 GB yang didekompresi, wc -ldibutuhkan 2,5 detik. gzcat compressed.gz > /dev/nullmembutuhkan 2,7 detik. Namun, pipa membutuhkan 22 detik. Jika saya mencoba GNU wc, hanya membutuhkan setengah detik pada file yang didekompresi, tetapi 22 detik dalam pipa. GNU zcatmembutuhkan waktu dua kali lebih lama untuk dieksekusi zcat compressed.gz > /dev/null. Ini ada di Mavericks, CPU Core 2 Duo lama, 16 GB RAM, SSD MX100 Krusial.
Sinan Ünür
4

Jawaban Kusalananda sebagian besar benar. Untuk menghitung garis, Anda perlu mencari baris baru. Namun secara teori dimungkinkan untuk mencari baris baru tanpa sepenuhnya mengompres file.

gzip menggunakan kompresi DEFLATE. DEFLATE adalah kombinasi dari pengkodean LZ77 dan Huffman. Mungkin ada cara untuk mencari tahu hanya simbol simbol Huffman untuk baris baru dan mengabaikan sisanya. Hampir pasti ada cara untuk mencari baris baru yang dikodekan menggunakan L277, menyimpan jumlah byte dan mengabaikan yang lainnya.

Jadi IMHO secara teoritis dimungkinkan untuk menghasilkan solusi yang lebih efisien daripada unpigz atau zgrep. Itu dikatakan tidak praktis (kecuali seseorang telah melakukannya).

IAmBarry
sumber
7
Masalah utama dengan ide ini adalah, simbol Huffman yang digunakan oleh DEFLATE berhubungan dengan urutan bit setelah kompresi LZ77, jadi mungkin tidak ada hubungan sederhana antara mereka dan karakter U + 000A dalam file yang tidak dikompresi. Misalnya, mungkin satu simbol Huffman berarti lima bit terakhir dari "." diikuti oleh tiga bit pertama "\ n", dan simbol lain berarti lima bit terakhir dari "\ n" diikuti oleh delapan bit "T".
zwol
@ zwol Tidak, bagian LZ77 dari algoritma Deflate memampatkan urutan byte, bukan urutan bit. en.wikipedia.org/wiki/DEFLATE#Duplicate_string_elimination
Ross Ridge
1
@RossRidge Huh, saya tidak tahu itu, tapi saya pikir itu tidak membatalkan apa yang saya katakan. The Huffman simbol bisa, tampaknya saya berdasarkan ayat berikutnya dari referensi yang, masing-masing memperluas ke sejumlah variabel bit, mereka tidak memiliki untuk menghasilkan sejumlah seluruh byte.
zwol
1
@ zwol Tentu, Anda harus mencari pencocokan urutan bit kode Huffman dalam aliran bit tetapi jawaban ini tidak menyarankan sebaliknya. Masalah dengan jawaban ini adalah bahwa menentukan kode Huffman yang akhirnya menghasilkan atau lebih banyak karakter baris baru tidak sederhana. Kode LZ77 yang menghasilkan baris baru terus berubah ketika jendela geser bergerak, yang berarti bahwa kode Huffman juga berubah. Anda harus menerapkan seluruh algoritma dekompresi kecuali bagian output, dan mungkin beberapa bagian dari jendela geser karena Anda hanya tertarik pada baris baru.
Ross Ridge
1

Dapat dilakukan zgrepdengan menggunakan -cflag, dan $parameter.

Dalam hal ini -c menginstruksikan perintah untuk menampilkan jumlah baris yang cocok dan $ regex cocok dengan akhir baris sehingga cocok dengan setiap baris atau file.

zgrep -c $ T.csv.gz 

Seperti yang dikomentari oleh @ StéphaneChazelas - zgrephanya sebuah skrip di sekitar zcatdan grepdan itu harus memberikan kinerja yang mirip dengan saran asli darizcat | wc -l

Yaron
sumber
2
Hai Yaron terima kasih atas jawabannya bahkan zgrep mengambil banyak waktu sebanyak zcat saya perlu menemukan beberapa pendekatan lain yang saya pikir
Rahul
8
zgrepumumnya skrip yang memanggil zcat(sama dengan gzip -dcq) untuk mengompres data dan memberinya makan grep, jadi tidak akan membantu.
Stéphane Chazelas
1
@ StéphaneChazelas - terima kasih atas komentarnya, perbarui jawaban saya untuk mencerminkannya.
Yaron
0

Seperti yang Anda lihat, sebagian besar jawaban mencoba untuk mengoptimalkan apa yang dapat dilakukan: jumlah konteks beralih dan IO antar-proses. Alasannya, ini adalah satu-satunya yang dapat Anda optimalkan dengan mudah di sini.

Sekarang masalahnya adalah bahwa kebutuhan sumber dayanya hampir dapat diabaikan untuk kebutuhan sumber daya dekompresi. Inilah sebabnya mengapa optimasi tidak akan benar-benar membuat sesuatu lebih cepat.

Di mana itu bisa benar-benar dipercepat, itu akan menjadi algoritma un-gzip (yaitu dekompresi) yang dimodifikasi, yang meninggalkan produksi aktual dari aliran data yang terkompresi; melainkan hanya menghitung jumlah baris baru dalam aliran yang dikompresi dari yang terkompresi . Akan sulit, itu akan membutuhkan pengetahuan yang mendalam tentang algoritma gzip (beberapa kombinasi dari algoritma kompresi LZW dan Huffman ). Sangat mungkin, bahwa algoritma tidak memungkinkan untuk secara signifikan mengoptimalkan waktu dekompresi dengan keringanan, bahwa kita hanya perlu mengetahui jumlah baris baru. Bahkan jika itu mungkin, pada dasarnya pustaka dekompresi gzip baru seharusnya dikembangkan (tidak ada sebelum diketahui).

Jawaban realistis untuk pertanyaan Anda adalah, tidak, Anda tidak dapat membuatnya lebih cepat secara signifikan.

Mungkin Anda dapat menggunakan beberapa dekompresi gzip paralel, jika ada. Itu bisa menggunakan beberapa core CPU untuk dekompresi. Jika tidak ada, itu bisa relatif mudah dikembangkan.

Untuk xz , ada kompresor paralel (pxz).

peterh - Pasang kembali Monica
sumber