La forma más rápida y eficiente de obtener el número de registros (líneas) en un archivo comprimido con gzip

16

Estoy tratando de hacer un recuento de registros en un archivo gzip de 7,6 GB. Encontré algunos enfoques usando el zcatcomando.

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

Esto funciona, pero lleva demasiado tiempo (más de 10 minutos para obtener el recuento). Intenté algunos enfoques más como

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

Estos tres comandos se ejecutan bastante rápido pero dan un recuento incorrecto de 28173811.

¿Cómo puedo realizar un recuento de registros en un tiempo mínimo?

Rahul
fuente
55
¿Por qué necesita contar la cantidad de registros? Si está tratando de contarlos antes de procesarlos, eso significa que debe descomprimir el archivo dos veces.
Andrew Henle
3
Más información sobre por qué estás haciendo esto sería útil. Si es algo en curso, es decir, comprime regularmente un montón de archivos y, en algún momento posterior, necesita saber la cantidad de registros, ¿por qué no contarlos a medida que se comprimen e incrustar el número en el nombre del archivo?
jamesqf
3
Leer un archivo de 9.7GB desde un disco mecánico es inherentemente más lento. Almacene el archivo en un SSD y vea qué tan rápido se ejecuta gunzip / zcat. Pero como dice @jamesqf, almacene el recuento de líneas en el nombre del archivo o en un archivo en el tgz, y extraer ese archivo será mucho más rápido.
ChuckCottrill
2
Hay buenas razones teóricas por las que no puedes evitar este trabajo. Un formato de compresión que le permite determinar alguna propiedad útil de los datos "sin descomprimir que" es casi por definición no es tan bueno un formato de compresión, ya que podría ser :)
Hobbs

Respuestas:

28

El sed,perl y los awkcomandos que se pueden mencionar correcta, pero todos ellos leer los comprimidos de datos y los recuentos de caracteres de nueva línea en eso. Estos caracteres de nueva línea no tienen nada que ver con los caracteres de nueva línea en los datos sin comprimir.

Para contar el número de líneas en los datos sin comprimir, no hay forma de descomprimirlos. Tu enfoque conzcat es el enfoque correcto y dado que los datos es tan grande, que va a tomar tiempo para descomprimirlo.

La mayoría de las utilidades que se ocupan de la gzipcompresión y la descompresión probablemente usarán las mismas rutinas de biblioteca compartida para hacerlo. La única forma de acelerarlo sería encontrar una implementación de las zlibrutinas que de alguna manera sean más rápidas que las predeterminadas, y reconstruir, por ejemplo, zcatpara usarlas.

Kusalananda
fuente
11
Sería un ejercicio de programación no trivial, pero factible. El punto es no reconstruir zcat. Una parte importante del trabajo de zcatgenerar el resultado real. Pero si solo estás contando \npersonajes, eso no es necesario. gzipla compresión funciona esencialmente reemplazando cadenas largas comunes por cadenas más cortas. Por lo tanto, solo debe preocuparse por las cadenas largas en el diccionario que contienen a \n, y contar la aparición (ponderada) de esas. Por ejemplo, debido a las reglas inglesas, .\nes una cadena común de 16 bits.
MSalters
19

Use unpigz.

La respuesta de Kusalananda es correcta, deberá descomprimir todo el archivo para escanear su contenido. /bin/gunziphace esto tan rápido como puede, en un solo núcleo. Pigz es una implementación paralela gzipque puede usar múltiples núcleos.

Lamentablemente, la descompresión de archivos en sí gzip normales no se puede paralelizar, pero pigzsí ofrece una versión mejorada gunzip, unpigzque hace el trabajo relacionado, como la lectura, la escritura, y la suma de control en un hilo separado. En algunos puntos de referencia rápidos, unpigzes casi el doble de rápido que gunzipen mi máquina Core i5.

Instale pigzcon su administrador de paquetes favorito y use en unpigzlugar de gunzip, o en unpigz -clugar de zcat. Entonces su comando se convierte en:

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

Todo esto supone que el cuello de botella es la CPU, no el disco, por supuesto.

marcelm
fuente
44
Mi pigzpágina de manual dice que la descompresión no se puede paralelizar, al menos no sin flujos de desinflado especialmente preparados para ese propósito. Como resultado, pigz usa un solo subproceso (el subproceso principal) para la descompresión, pero creará otros tres subprocesos para leer, escribir y verificar el cálculo, lo que puede acelerar la descompresión en algunas circunstancias . Aún así, como usted, encuentro que es al menos dos veces más rápido que gzip, si no es por el paralelismo
Stéphane Chazelas
@ StéphaneChazelas Buen punto! Eso explica la aceleración levemente decepcionante para la descompresión. Edité mi publicación para reflejar mejor esta información.
marcelm
5

El problema con todas las tuberías es que esencialmente está duplicando el trabajo. No importa qué tan rápida sea la descompresión, los datos aún deben transferirse a otro proceso.

Perl tiene PerlIO :: gzip que le permite leer secuencias comprimidas directamente. Por lo tanto, podría ofrecer una ventaja incluso si su velocidad de descompresión puede no coincidir con la de 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]': $!";

Lo probé con un archivo comprimido gzip de 13 MB (se descomprime a 1,4 GB) en un viejo MacBook Pro 2010 con 16 GB de RAM y un viejo ThinkPad T400 con 8 GB de RAM con el archivo ya en el caché. En la Mac, el script de Perl fue significativamente más rápido que el uso de tuberías (5 segundos frente a 22 segundos), pero en ArchLinux, perdió debido a la desconexión:

$ time -p ./gzlc.pl spy.gz 
1154737
real 4.49
usuario 4.47
sys 0.01

versus

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

y

$ time -p zcat spy.gz | wc -l
1154737
real 6.41
usuario 6.08
sys 0.86

Claramente, el uso unpigz -c file.gz | wc -les el ganador aquí tanto en términos de velocidad. Y, esa simple línea de comando seguramente es mejor que escribir un programa, por breve que sea.

Sinan Ünür
fuente
1
Creo que está sobreestimando en gran medida los recursos necesarios para mover los datos entre dos procesos, en comparación con los cálculos de descompresión. Intente realizar una evaluación comparativa de los diversos enfoques;)
marcelm
2
@ SinanÜnür En mi sistema x86_64 Linux (también hardware antiguo) gzip | wctiene la misma velocidad que su script perl. Y pigz | wces el doble de rápido. gzipse ejecuta con la misma velocidad, independientemente de si escribo la salida en / dev / null o pipe en wcLo que creo es que la "biblioteca gzip" utilizada por perl es más rápida que la herramienta de línea de comandos gzip. Quizás haya otro problema específico de Mac / Darwin con las tuberías. Todavía es sorprendente que esta versión perl sea competitiva en absoluto.
rudimeier
1
En mi instalación de Linux x86_64, parece funcionar mejor zcaty peor que unpigz. Estoy sorprendido de lo rápido que es la canalización en el sistema Linux en comparación con la Mac. No esperaba eso, aunque debería haberlo hecho, ya que una vez observé que el mismo programa se ejecutó más rápido en una máquina virtual Linux con CPU limitada en esa misma Mac que en el bare metal.
Sinan Ünür
1
Eso es interesante; en mi sistema (Debian 8.8 amd64, quad core i5), el script perl es un poco más lento ... el archivo 109M .gz se descomprime a 1.1G de texto, consistentemente tarda 5.4 segundos zcat | wc -ly 5.5 segundos para su script perl. Honestamente, estoy sorprendido por la variación que la gente informa aquí, ¡especialmente entre Linux y MacOS X!
marcelm
No sé si puedo generalizar lo que estoy viendo en mi Mac, algo extraño está sucediendo. Con el archivo descomprimido de 1.4 GB, wc -ltoma 2.5 segundos. gzcat compressed.gz > /dev/nulltoma 2.7 segundos Sin embargo, la tubería tarda 22 segundos. Si intento GNU wc, solo toma medio segundo en el archivo descomprimido, pero 22 segundos en la tubería. GNU zcattarda el doble de tiempo en ejecutarse zcat compressed.gz > /dev/null. Esto está en Mavericks, antigua CPU Core 2 Duo, 16 GB de RAM, SSD Crucial MX100.
Sinan Ünür
4

La respuesta de Kusalananda es mayormente correcta. Para contar líneas necesita buscar nuevas líneas. Sin embargo, es teóricamente posible buscar nuevas líneas sin descomprimir completamente el archivo.

gzip usa la compresión DEFLATE. DEFLATE es una combinación de codificación LZ77 y Huffman. Puede haber una manera de descubrir solo el nodo del símbolo de Huffman para la nueva línea e ignorar el resto. Es casi seguro que hay una forma de buscar nuevas líneas codificadas con L277, mantener un recuento de bytes e ignorar todo lo demás.

Entonces, en mi humilde opinión, es teóricamente posible encontrar una solución más eficiente que unpigz o zgrep. Dicho esto, ciertamente no es práctico (a menos que alguien ya lo haya hecho).

IAmBarry
fuente
77
Un problema importante con esta idea es que los símbolos Huffman utilizados por DEFLATE corresponden a secuencias de bits después de la compresión LZ77, por lo que puede no haber una relación simple entre ellos y los caracteres U + 000A en el archivo sin comprimir. Por ejemplo, tal vez un símbolo de Huffman significa los últimos cinco bits de "." seguido de los primeros tres bits de "\ n", y otro símbolo significa los últimos cinco bits de "\ n" seguido de los ocho bits de "T".
zwol
@zwol No, la porción LZ77 del algoritmo Deflate comprime secuencias de bytes, no secuencias de bits. en.wikipedia.org/wiki/DEFLATE#Duplicate_string_elimination
Ross Ridge
1
@RossRidge Huh, no lo sabía, pero no creo que invalide lo que dije. Los símbolos de Huffman pueden, me parece basado en el siguiente párrafo de esa referencia, cada uno se expande a un número variable de bits, no tienen que producir un número entero de bytes.
zwol
1
@zwol Claro, debe buscar secuencias de bits de código Huffman coincidentes en la secuencia de bits, pero esta respuesta no sugiere lo contrario. El problema con esta respuesta es que determinar qué códigos de Huffman generan en última instancia o más caracteres de nueva línea no es simple. Los códigos LZ77 que generan nuevas líneas cambian constantemente a medida que se mueve la ventana deslizante, lo que significa que los códigos Huffman también están cambiando. Tendría que implementar todo el algoritmo de descompresión, excepto la parte de salida, y tal vez alguna parte de la ventana deslizante, ya que solo le interesan las nuevas líneas.
Ross Ridge
1

Se puede hacer usando zgrepcon -cbandera y $parámetro.

En este caso, -c indica al comando que muestre el número de líneas coincidentes y la expresión regular $ coincide con el final de línea para que coincida con cada línea o el archivo.

zgrep -c $ T.csv.gz 

Como se ha comentado por @ StéphaneChazelas - zgrepes solamente un guión alrededor zcaty grepy debe proporcionar un rendimiento similar a la sugerencia original dezcat | wc -l

Yaron
fuente
2
Hola Yaron, gracias por la respuesta, incluso el zgrep está tomando tanto tiempo como el zcat. Necesito encontrar otro enfoque, creo
Rahul
8
zgrepgeneralmente es un script que invoca zcat(igual que gzip -dcq) para descomprimir los datos y alimentarlos grep, por lo que no va a ayudar.
Stéphane Chazelas
1
@ StéphaneChazelas: gracias por el comentario, actualice mi respuesta para reflejarlo.
Yaron
0

Como puede ver, la mayoría de las respuestas intentan optimizar lo que puede: el número de cambios de contexto y la E / S entre procesos. La razón es que esto es lo único que puede optimizar aquí fácilmente.

Ahora el problema es que su necesidad de recursos es casi insignificante para la necesidad de recursos de la descompresión. Es por eso que las optimizaciones realmente no harán nada más rápido.

Donde realmente podría acelerarse, sería un algoritmo modificado de descompresión (es decir, descompresión), que excluye la producción real del flujo de datos descomprimido; más bien solo calcula el número de las nuevas líneas en el flujo descomprimido del comprimido . Sería difícil, requeriría un conocimiento profundo del algoritmo de gzip (alguna combinación de los algoritmos de compresión LZW y Huffman ). Es bastante probable que el algoritmo no permita optimizar significativamente el tiempo de descompresión con el rayo, que solo necesitamos saber los recuentos de nueva línea. Incluso si fuera posible, esencialmente se debería haber desarrollado una nueva biblioteca de descompresión gzip (no existe hasta que se sepa).

La respuesta realista a su pregunta es que no, no puede hacerlo significativamente más rápido.

Tal vez podría usar alguna descompresión paralela de gzip, si existe. Podría usar múltiples núcleos de CPU para la descompresión. Si no existe, podría desarrollarse con relativa facilidad.

Para el xz , existe un compresor paralelo (pxz).

peterh - Restablece a Monica
fuente