Schnellste und effizienteste Methode zum Abrufen der Anzahl der Datensätze (Zeilen) in einer mit gzip komprimierten Datei

16

Ich versuche, eine Rekordzählung für eine 7,6-GB-gzip-Datei durchzuführen. Ich habe mit dem zcatBefehl nur wenige Ansätze gefunden .

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

Dies funktioniert, aber es dauert zu lange (mehr als 10 Minuten, um die Zählung durchzuführen). Ich habe noch ein paar Ansätze ausprobiert wie

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

Alle drei Befehle werden ziemlich schnell ausgeführt, geben jedoch eine falsche Anzahl von 28173811 an.

Wie kann ich in kürzester Zeit eine Datensatzzählung durchführen?

Rahul
quelle
5
Warum müssen Sie die Anzahl der Datensätze zählen? Wenn Sie versuchen, sie zu zählen, bevor Sie sie verarbeiten, müssen Sie die Datei zweimal dekomprimieren.
Andrew Henle
3
Weitere Informationen dazu, warum Sie dies tun, sind hilfreich. Wenn es sich um einen laufenden Vorgang handelt, das heißt, Sie komprimieren regelmäßig eine Reihe von Dateien und müssen zu einem späteren Zeitpunkt die Anzahl der Datensätze kennen. Zählen Sie sie dann als komprimiert, und betten Sie die Anzahl in den Dateinamen ein.
Jamesqf
3
Das Lesen einer 9,7-GB-Datei von einer mechanischen Festplatte ist von Natur aus langsamer. Speichern Sie die Datei auf einer SSD und sehen Sie, wie viel schneller gunzip / zcat ausgeführt wird. Aber wie @jamesqf sagt, speichern Sie die Zeilenanzahl im Dateinamen oder in einer Datei im TGZ, und das Extrahieren dieser Datei ist viel schneller.
ChuckCottrill
2
Es gibt gute theoretische Gründe, warum Sie diese Arbeit nicht vermeiden können. Ein Komprimierungsformat, mit dem Sie einige nützliche Eigenschaften der Daten "ohne sie zu dekomprimieren" bestimmen können, ist per Definition nicht so gut wie es sein könnte :)
hobbs

Antworten:

28

Die sed, perlund awkBefehle, die Sie erwähnen, mögen korrekt sein, aber alle lesen die komprimierten Daten und zählen darin die Zeilenumbrüche. Diese Zeilenumbruchzeichen haben nichts mit den Zeilenumbruchzeichen in den unkomprimierten Daten zu tun.

Um die Anzahl der Zeilen in den unkomprimierten Daten zu zählen, führt kein Weg daran vorbei, sie zu dekomprimieren. Ihr Ansatz mit zcatist der richtige Ansatz , und da die Daten so groß ist, es wird einige Zeit dauern , um es zu dekomprimieren.

Die meisten Dienstprogramme, die sich mit gzipKomprimierung und Dekomprimierung befassen, verwenden dazu wahrscheinlich dieselben Routinen für gemeinsam genutzte Bibliotheken. Die einzige Möglichkeit, dies zu beschleunigen, besteht darin, eine Implementierung der zlibRoutinen zu finden, die irgendwie schneller als die Standardroutinen sind, und diese beispielsweise neu zcatzu erstellen, um sie zu verwenden.

Kusalananda
quelle
11
Es wäre eine nicht triviale Programmierübung, aber machbar. Der springende Punkt ist, nicht wieder aufzubauen zcat. Ein wesentlicher Teil der Arbeit von zcatist die Erzeugung der tatsächlichen Leistung. Wenn Sie jedoch nur \nZeichen zählen, ist dies nicht erforderlich. gzipDie Komprimierung funktioniert im Wesentlichen, indem herkömmliche lange Zeichenfolgen durch kürzere Zeichenfolgen ersetzt werden. Sie müssen sich also nur um die langen Zeichenfolgen im Wörterbuch kümmern, die ein enthalten \n, und das (gewichtete) Vorkommen dieser zählen. ZB ist aufgrund englischer Regeln .\neine übliche 16-Bit-Zeichenfolge.
MSalters
19

Verwenden Sie Unpigz.

Kusalananda Antwort ist richtig, Sie werden zu dekomprimieren müssen , dass gesamte Datei seinen Inhalt zu scannen. /bin/gunziperledigt dies so schnell wie möglich auf einem einzigen Kern. Pigz ist eine parallele Implementierung gzip, die mehrere Kerne verwenden kann.

Leider kann die Dekomprimierung normaler gzip-Dateien nicht parallelisiert werden, pigzbietet jedoch eine verbesserte Version von gunzip, unpigzdie verwandte Arbeiten wie Lesen, Schreiben und Prüfsummen in einem separaten Thread ausführt. In einigen schnellen Benchmarks unpigzist es fast doppelt so schnell wie gunzipauf meinem Core-i5-Rechner.

Installieren Sie pigzmit Ihrem bevorzugten Paket-Manager und verwenden Sie unpigzanstelle von gunzipoder unpigz -canstelle von zcat. So wird Ihr Befehl:

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

Das alles setzt voraus, dass der Engpass die CPU ist und nicht die Festplatte.

marcelm
quelle
4
Auf meiner pigzManpage steht, dass die Dekomprimierung nicht parallelisiert werden kann, zumindest nicht ohne speziell dafür vorbereitete Deflate-Streams. Folglich verwendet pigz einen einzelnen Thread (den Haupt-Thread) für die Dekomprimierung, erstellt jedoch drei weitere Threads zum Lesen, Schreiben und Überprüfen der Berechnung, wodurch die Dekomprimierung unter bestimmten Umständen beschleunigt werden kann . Dennoch, wie Sie finde ich, ist es mindestens doppelt so schnell wie gzip, wenn nicht wegen der Parallelität
Stéphane Chazelas
@ StéphaneChazelas Guter Punkt! Das erklärt die leicht enttäuschende Beschleunigung der Dekompression. Ich habe meinen Beitrag bearbeitet, um diese Informationen besser wiederzugeben.
März
5

Das Problem bei allen Pipelines ist, dass Sie die Arbeit im Wesentlichen verdoppeln. Egal wie schnell die Dekomprimierung ist, die Daten müssen immer noch zu einem anderen Prozess verschoben werden.

Perl hat PerlIO :: gzip , mit dem Sie gzippte Streams direkt lesen können. Daher könnte es einen Vorteil bieten, selbst wenn seine Dekomprimierungsgeschwindigkeit nicht mit der folgenden übereinstimmt 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]': $!";

Ich habe es mit einer komprimierten 13-MB-GZIP-Datei (dekomprimiert auf 1,4 GB) auf einem alten 2010 MacBook Pro mit 16 GB RAM und einem alten ThinkPad T400 mit 8 GB RAM versucht, wobei sich die Datei bereits im Cache befindet. Auf dem Mac war das Perl-Skript deutlich schneller als die Verwendung von Pipelines (5 Sekunden gegenüber 22 Sekunden).

$ time -p ./gzlc.pl spy.gz 
1154737
echte 4,49
Benutzer 4.47
sys 0.01

gegen

$ time -p unpigz -c spy.gz | wc -l
1154737
real 3,68
Benutzer 4.10
sys 1.46

und

$ time -p zcat spy.gz | wc -l
1154737
echte 6,41
Benutzer 6.08
sys 0.86

Die Verwendung von unpigz -c file.gz | wc -list hier eindeutig der Gewinner, sowohl in Bezug auf die Geschwindigkeit. Und diese einfache Befehlszeile ist mit Sicherheit besser als ein Programm zu schreiben, wie kurz es auch sein mag.

Sinan Ünür
quelle
1
Ich denke, Sie überschätzen die Ressourcen, die zum Verschieben der Daten zwischen zwei Prozessen erforderlich sind, im Vergleich zu den Dekomprimierungsberechnungen erheblich. Versuchen Sie, die verschiedenen Ansätze zu vergleichen;)
März,
2
@ SinanÜnür Auf meinem x86_64 Linux System (auch alte Hardware) gzip | wchat das die selbe Geschwindigkeit wie dein Perl Skript. Und pigz | wcist doppelt so schnell. gzipLäuft mit der gleichen Geschwindigkeit, unabhängig davon, ob ich die Ausgabe in / dev / null oder pipe in schreibe. wcIch glaube, dass die von Perl verwendete "gzip-Bibliothek" schneller ist als das gzip-Befehlszeilentool. Vielleicht gibt es ein anderes Mac / Darwin-spezifisches Problem mit Pipes. Es ist immer noch erstaunlich, dass diese Perl-Version überhaupt wettbewerbsfähig ist.
Rudimeier
1
Bei meiner x86_64-Linux-Installation scheint es besser als zcatund schlechter als zu sein unpigz. Ich bin erstaunt, wie viel schneller die Pipeline auf dem Linux-System ist als auf dem Mac. Ich hatte nicht damit gerechnet, obwohl ich, wie ich einst beobachtete, dasselbe Programm auf einer Linux-VM mit begrenzter CPU auf demselben Mac schneller laufen sollte als auf Bare Metal.
Sinan Ünür
1
Das ist interessant; Auf meinem System (Debian 8.8 amd64, Quad Core i5) ist das Perl-Skript etwas langsamer ... 109M .gz-Datei, die auf 1,1G Text dekomprimiert wird, dauert konsistent 5,4 Sekunden zcat | wc -lund 5,5 Sekunden für Ihr Perl-Skript. Ehrlich gesagt bin ich erstaunt über die Variationen, über die hier berichtet wird, insbesondere zwischen Linux und MacOS X!
marcelm
Ich weiß nicht, ob ich verallgemeinern kann, was ich auf meinem Mac sehe, etwas Merkwürdiges ist los. Mit der dekomprimierten 1,4-GB-Datei wc -ldauert dies 2,5 Sekunden. gzcat compressed.gz > /dev/nulldauert 2,7 Sekunden. Die Pipeline dauert jedoch 22 Sekunden. Wenn ich GNU versuche wc, dauert es nur eine halbe Sekunde für die dekomprimierte Datei, aber 22 Sekunden in der Pipeline. Die zcatAusführung von GNU dauert doppelt so lange zcat compressed.gz > /dev/null. Dies ist auf Mavericks, alten Core 2 Duo-CPU, 16 GB RAM, Crucial MX100 SSD.
Sinan Ünür
4

Kusalanandas Antwort ist größtenteils richtig. Um Zeilen zu zählen, müssen Sie nach neuen Zeilen suchen. Theoretisch ist es jedoch möglich, nach Zeilenumbrüchen zu suchen, ohne die Datei vollständig zu dekomprimieren.

gzip verwendet die DEFLATE-Komprimierung. DEFLATE ist eine Kombination aus LZ77- und Huffman-Codierung. Es kann eine Möglichkeit geben, nur den Huffman-Symbolknoten für Zeilenumbruch herauszufinden und den Rest zu ignorieren. Es gibt mit ziemlicher Sicherheit eine Möglichkeit, nach mit L277 codierten Zeilenumbrüchen zu suchen, die Anzahl der Bytes beizubehalten und alles andere zu ignorieren.

Meiner Meinung nach ist es theoretisch möglich, eine effizientere Lösung als unpigz oder zgrep zu finden. Davon abgesehen ist es sicherlich nicht praktikabel (es sei denn, jemand hat es bereits getan).

IAmBarry
quelle
7
Ein Hauptproblem bei dieser Idee besteht darin, dass die von DEFLATE verwendeten Huffman-Symbole nach der LZ77-Komprimierung Bitsequenzen entsprechen , sodass möglicherweise keine einfache Beziehung zwischen ihnen und U + 000A-Zeichen in der unkomprimierten Datei besteht. Beispielsweise bedeutet ein Huffman-Symbol möglicherweise die letzten fünf Bits von "." gefolgt von den ersten drei Bits von "\ n", und ein anderes Symbol bedeutet die letzten fünf Bits von "\ n", gefolgt von allen acht Bits von "T".
zwol
@zwol Nein, der LZ77-Teil des Deflate-Algorithmus komprimiert Byte-Sequenzen, nicht Bit-Sequenzen. en.wikipedia.org/wiki/DEFLATE#Duplicate_string_elimination
Ross Ridge
1
@ RossRidge Huh, ich wusste das nicht, aber ich glaube nicht, dass es das, was ich gesagt habe, ungültig macht. Die Huffman- Symbole können, so scheint es mir, basierend auf dem nächsten Absatz dieser Referenz, jeweils auf eine variable Anzahl von Bits erweitert werden, sie müssen nicht eine ganze Anzahl von Bytes erzeugen.
zwol
1
@zwol Sicher, Sie müssen nach passenden Huffman-Codebitsequenzen im Bitstrom suchen, aber diese Antwort schlägt nichts anderes vor. Das Problem bei dieser Antwort ist, dass es nicht einfach ist, festzustellen, welche Huffman-Codes letztendlich oder mehr Zeilenumbrüche erzeugen. Die LZ77-Codes, die Zeilenumbrüche erzeugen, ändern sich ständig, wenn sich das Schiebefenster bewegt, was bedeutet, dass sich auch die Huffman-Codes ändern. Sie müssten den gesamten Dekomprimierungsalgorithmus mit Ausnahme des Ausgabeteils und möglicherweise eines Teils des Schiebefensters implementieren, da Sie nur an den Zeilenumbrüchen interessiert sind.
Ross Ridge
1

Kann mit getan werden zgrep mit -cflag und $parameter durchgeführt werden.

In diesem Fall weist -c den Befehl an, die Anzahl der übereinstimmenden Zeilen auszugeben, und der reguläre Ausdruck $ stimmt mit dem Zeilenende überein, sodass er mit jeder Zeile oder Datei übereinstimmt.

zgrep -c $ T.csv.gz 

Wie kommentiert von @ StéphaneChazelas - zgrepist nur ein Skript um zcatund grepes soll eine ähnliche Leistung auf den ursprünglichen Vorschlag liefernzcat | wc -l

Yaron
quelle
2
Hallo Yaron danke für die Antwort auch die zgrep wird so viel Zeit wie zcat Einnahme ich brauche etwas andere Ansatz finde ich denke
Rahul
8
zgrepist im Allgemeinen ein Skript, das zcat(dasselbe wie gzip -dcq) aufruft, um die Daten zu dekomprimieren und zu füttern. Es grepwird also nicht helfen.
Stéphane Chazelas
1
@ StéphaneChazelas - danke für den Kommentar, aktualisiere meine Antwort, um sie wiederzugeben.
Yaron
0

Wie Sie sehen, versuchen die meisten Antworten zu optimieren, was möglich ist: die Anzahl der Kontextwechsel und der prozessübergreifenden E / A. Dies ist der einzige Grund, warum Sie hier einfach optimieren können.

Das Problem ist nun, dass sein Ressourcenbedarf gegenüber dem Ressourcenbedarf der Dekomprimierung nahezu vernachlässigbar ist. Aus diesem Grund werden die Optimierungen nichts wirklich schneller machen.

Wo es wirklich beschleunigt werden könnte, wäre es ein modifizierter Un-Gzip-Algorithmus (dh Dekomprimierungsalgorithmus), der die tatsächliche Erzeugung des dekomprimierten Datenstroms ausschließt. Stattdessen wird nur die Anzahl der Zeilenumbrüche im dekomprimierten Stream aus dem komprimierten berechnet . Es wäre schwierig, es würde tiefe Kenntnisse des gzip-Algorithmus erfordern (eine Kombination der LZW- und Huffman- Komprimierungsalgorithmen). Es ist sehr wahrscheinlich, dass der Algorithmus es nicht möglich macht, die Dekomprimierungszeit mit dem Blitz signifikant zu optimieren. Wir müssen nur die Zeilenumbrüche kennen. Selbst wenn es möglich wäre, hätte im Wesentlichen eine neue gzip-Dekomprimierungsbibliothek entwickelt werden müssen (diese existiert erst, wenn man es weiß).

Die realistische Antwort auf Ihre Frage lautet: Nein, Sie können es nicht wesentlich schneller machen.

Möglicherweise könnten Sie eine parallelisierte gzip-Dekomprimierung verwenden, falls vorhanden. Es könnten mehrere CPU-Kerne für die Dekomprimierung verwendet werden. Wenn es nicht existiert, könnte es relativ leicht entwickelt werden.

Für das xz gibt es einen Parallelkompressor (pxz).

Peterh: Setzen Sie Monica wieder ein
quelle