Grep gran cantidad de patrones de gran archivo

18

Tengo un archivo que crece aproximadamente 200,000 líneas por día, y todo está formado con bloques de tres líneas como tales:

1358726575123       # key
    Joseph Muller   # name
    carpenter       # job
9973834728345
    Andres Smith
    student
7836472098652
    Mariah Anthony
    dentist

Ahora, tengo otro archivo del que extraigo unos 10,000 patrones clave, como 1358726575123. Luego ejecuto un forciclo con estos patrones y tengo que compararlos con el primer archivo. Si el archivo no contiene dicho patrón, guardo el patrón en un tercer archivo para su posterior procesamiento:

for number in $(grep -o '[0-9]\{12\}' file2); do  # finds about 10.000 keys
     if ! grep -q ^$number$ file1; then           # file1 is a huge file
         printf "$number\n" >>file3               # we'll process file3 later
     fi
done

El código de ejemplo engloba un archivo enorme 10,000 veces, y ejecuto este bucle aproximadamente una vez por minuto, durante todo el día .

Dado que el gran archivo sigue creciendo, ¿qué puedo hacer para acelerar todo esto y ahorrar algo de CPU? Me pregunto si ordenar el archivo de alguna manera por su clave (si es así, ¿cómo?) O usar un db en lugar de texto sin formato ayudaría ...

Teresa e Junior
fuente

Respuestas:

11

Esta respuesta se basa en la awkrespuesta publicada por potong .
Es el doble de rápido que el commmétodo (en mi sistema), para los mismos 6 millones de líneas en el archivo principal y 10 mil claves ... (ahora actualizado para usar FNR, NR)

Aunque awkes más rápido que su sistema actual y le dará a usted y a su computadora algo de espacio para respirar, tenga en cuenta que cuando el procesamiento de datos es tan intenso como lo ha descrito, obtendrá los mejores resultados generales al cambiar a una base de datos dedicada; p.ej. SQlite, MySQL ...


awk '{ if (/^[^0-9]/) { next }              # Skip lines which do not hold key values
       if (FNR==NR) { main[$0]=1 }          # Process keys from file "mainfile"
       else if (main[$0]==0) { keys[$0]=1 } # Process keys from file "keys"
     } END { for(key in keys) print key }' \
       "mainfile" "keys" >"keys.not-in-main"

# For 6 million lines in "mainfile" and 10 thousand keys in "keys"

# The awk  method
# time:
#   real    0m14.495s
#   user    0m14.457s
#   sys     0m0.044s

# The comm  method
# time:
#   real    0m27.976s
#   user    0m28.046s
#   sys     0m0.104s

Peter.O
fuente
Esto es rápido, pero no entiendo mucho de awk: ¿cómo deberían ser los nombres de los archivos? Lo intenté file1 -> mainfiley file2 -> keyscon gawk y mawk, y produce claves incorrectas.
Teresa e Junior
file1 tiene claves, nombres y trabajos.
Teresa e Junior
'mainfile' es el archivo grande (con claves, nombres y trabajos). Lo llamé "archivo principal 'porque seguía confundiéndome qué archivo era cuál (archivo1 frente a archivo2) ...' claves 'contiene solo las 10 mil, o cuantas, claves. Para su situación NO redirija nada. .. solo use file1 EOF file2 Son los nombres de sus archivos .. "EOF" es un archivo de 1 línea creado por el script para indicar el final del primer archivo (archivo de datos principal) y el inicio del segundo archivo ( teclas). le awkpermiten leer en una serie de archivos ... En este caso, esa serie tiene 3 archivos. La salida va astdout
Peter.O
Este script imprimirá cualquier clave que esté presente mainfile, Y también imprimirá cualquier clave del keysarchivo que NO esté en mainfile... Eso es probablemente lo que está sucediendo ... (Lo investigaré un poco más ...
Peter.O
¡Gracias, @ Peter.O! Como los archivos son confidenciales, estoy tratando de crear archivos de muestra $RANDOMpara cargar.
Teresa e Junior
16

El problema, por supuesto, es que ejecuta grep en el archivo grande 10,000 veces. Debería leer ambos archivos solo una vez. Si desea permanecer fuera de los lenguajes de secuencias de comandos, puede hacerlo de esta manera:

  1. Extraiga todos los números del archivo 1 y ordénelos
  2. Extraiga todos los números del archivo 2 y ordénelos
  3. Ejecutar commen las listas ordenadas para obtener lo que solo está en la segunda lista

Algo como esto:

$ grep -o '^[0-9]\{12\}$' file1 | sort -u -o file1.sorted
$ grep -o  '[0-9]\{12\}'  file2 | sort -u -o file2.sorted
$ comm -13 file1.sorted file2.sorted > file3

Ver man comm.

Si pudiera truncar el archivo grande todos los días (como un archivo de registro), podría mantener un caché de números ordenados y no necesitaría analizarlo todo el tiempo.

angus
fuente
1
¡Ordenado! 2 segundos (en unidades no particularmente rápidas) con 200,000 entradas de líneas aleatorias en el archivo principal (es decir, 600,000 líneas) y 143,000 claves aleatorias (así es como terminaron mis datos de prueba) ... probado, y funciona (pero sabía que: ) ... Me pregunto si el {12}... OP ha usado 12, pero las claves de ejemplo son 13 largas ...
Peter.O
2
Solo una pequeña nota, puede hacerlo sin tratar con archivos temporales usando <(grep...sort)dónde están los nombres de los archivos.
Kevin
Gracias, pero tomar y ordenar los archivos lleva mucho más tiempo que mi ciclo anterior (+ 2min.).
Teresa e Junior
@Teresa e Junior. ¿Qué tan grande es tu archivo principal? ... Usted ha mencionado que crece a 200,000 líneas por día, pero no lo grande que es ... Para reducir la cantidad de datos que necesita procesar, puede leer solo las 200,000 líneas de los días actuales tomando nota de el último número de línea procesado (ayer) y utilizado tail -n +$linenumpara generar solo los últimos datos. De esta forma, solo procesará aproximadamente 200,000 líneas por día. Lo probé con 6 millones de líneas en el archivo principal y 10 mil claves ... tiempo : 0m0.016s reales, usuario 0m0.008s, sys 0m0.008s
Peter.O
Realmente estoy bastante perplejo / curioso acerca de cómo puede manipular su archivo principal 10,000 veces y encontrarlo más rápido que este método que solo lo greps una vez (y una vez para el archivo mucho más pequeño1 ) ... Incluso si su clasificación lleva más tiempo que mi prueba, simplemente no puedo entender la idea de que leer un archivo grande que muchas veces no supera un solo tipo (en el tiempo)
Peter
8

Sí, definitivamente use una base de datos. Están hechos exactamente para tareas como esta.

Mika Fischer
fuente
¡Gracias! No tengo mucha experiencia con bases de datos. ¿Qué base de datos me recomiendan? Tengo MySQL y el comando sqlite3 instalado.
Teresa e Junior
1
Ambos están bien para esto, sqlite es más simple porque básicamente es solo un archivo y una API SQL para acceder a él. Con MySQL necesita configurar un servidor MySQL para poder usarlo. Si bien eso tampoco es muy difícil, sqlite podría ser mejor para comenzar.
Mika Fischer
3

Esto podría funcionar para usted:

 awk '/^[0-9]/{a[$0]++}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3

EDITAR:

La secuencia de comandos modificada para permitir duplicados y claves desconocidas en ambos archivos, aún produce claves del primer archivo que no está presente en el segundo:

 awk '/^[0-9]/{if(FNR==NR){a[$0]=1;next};if($0 in a){a[$0]=2}}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3
potong
fuente
Esto echará de menos las nuevas claves que se producen más de una vez en el archivo principal (y para el caso, que se producen más de una vez en el archivo de claves) Parece que es necesario que el incremento del recuento de la matriz del archivo principal no se permita más de 1, o alguna solución alternativa equivalente (+1 porque está bastante cerca de la marca)
Peter.O
1
Lo intenté con gawk y mawk, y produce claves incorrectas ...
Teresa e Junior
@ Peter.O Supuse que el archivo principal tenía claves únicas y que el archivo 2 era un subconjunto del archivo principal.
potong
@potong ¡El segundo funciona bien y muy rápido! ¡Gracias!
Teresa e Junior
@Teresa e Junior ¿Está seguro de que todavía funciona correctamente? ... Usando los datos de prueba que proporcionó , que deberían generar 5000 claves, cuando lo ejecuto, produce 136703 claves, tal como lo obtuve hasta que finalmente entendí cuáles eran sus requisitos ... @potong ¡ Por supuesto! FNR == NR (nunca lo he usado antes :)
Peter.O
2

Con esa cantidad de datos, realmente debería cambiar a una base de datos. Mientras tanto, una cosa que debe hacer para acercarse al rendimiento decente es no buscar file1cada clave por separado. Ejecute una sola greppara extraer todas las claves no excluidas a la vez. Dado que eso greptambién devuelve líneas que no contienen una clave, filtrelas.

grep -o '[0-9]\{12\}' file2 |
grep -Fxv -f - file1 |
grep -vx '[0-9]\{12\}' >file3

( -Fxsignifica buscar líneas enteras, literalmente. -f -significa leer una lista de patrones de la entrada estándar).

Gilles 'SO- deja de ser malvado'
fuente
A menos que me equivoque, esto no resuelve el problema de almacenar claves que no están en el archivo grande, almacenará las claves que están en él.
Kevin
@Kevin exactamente, y esto me ha obligado a usar el bucle.
Teresa e Junior
@TeresaeJunior: agregar -v( -Fxv) puede encargarse de eso.
Pausado hasta nuevo aviso.
@DennisWilliamson Eso sería recoger todas las líneas en el archivo grande que no coinciden con ninguna en el archivo de clave, incluyendo nombres, puestos de trabajo, etc.
Kevin
@ Kevin Gracias, leí mal la pregunta. He añadido un filtro para las líneas que no son clave, aunque mi preferencia ahora va a usarcomm .
Gilles 'SO- deja de ser malvado'
2

Permítame reforzar lo que otros han dicho: "¡Llévelo a una base de datos!"

Hay binarios de MySQL disponibles gratuitamente para la mayoría de las plataformas.

¿Por qué no SQLite? Está basado en la memoria, carga un archivo plano cuando lo inicia y luego lo cierra cuando haya terminado. Esto significa que si su computadora falla o el proceso de SQLite desaparece, también lo hacen todos los datos.

¡Su problema se parece a un par de líneas de SQL y se ejecutará en milisegundos!

Después de instalar MySQL (que recomiendo sobre otras opciones), pagaría $ 40 por el Libro de cocina SQL de O'Reilly de Anthony Molinaro, que tiene muchos patrones de problemas, comenzando con SELECT * FROM tableconsultas simples y pasando por agregados y múltiples combinaciones.

Jan Steinman
fuente
Sí, comenzaré a migrar mis datos a SQL en unos días, ¡gracias! ¡Sin embargo, los guiones awk me han estado ayudando mucho hasta que lo hago todo!
Teresa e Junior
1

No estoy seguro de si este es el resultado exacto que está buscando, pero probablemente la forma más fácil es:

grep -o '[0-9]\{12\}' file2 | sed 's/.*/^&$/' > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

También puedes usar:

sed -ne '/.*\([0-9]\{12\}.*/^\1$/p' file2 > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Cada uno de estos crea un archivo de patrón temporal que se utiliza para obtener los números del archivo grande ( file1).

Arcege
fuente
Creo que esto también encuentra números que están en el archivo grande, no aquellos que no lo están.
Kevin
Correcto, no vi el '!' en el OP. Solo necesito usar en grep -vflugar de grep -f.
Arcege
2
No @arcege, grep -vf no mostrará las claves no coincidentes, mostrará todo, incluidos los nombres y los trabajos.
Teresa e Junior
1

Estoy totalmente de acuerdo con que obtenga una base de datos (MySQL es bastante fácil de usar). Hasta que lo ejecute, me gusta la commsolución de Angus , pero hay tantas personas que lo intentan grepy se equivocan que pensé en mostrarle la forma correcta (o al menos una) de hacerlo grep.

grep -o '[0-9]\{12\}' keyfile | grep -v -f <(grep -o '^[0-9]\{12\}' bigfile) 

El primero greprecibe las llaves. El tercero grep(en el <(...)) toma todas las claves utilizadas en el archivo grande, y lo <(...)pasa como un archivo como argumento -fen el segundo grep. Eso hace que el segundo lo grepuse como una lista de líneas para que coincida. Luego usa esto para hacer coincidir su entrada (la lista de claves) de la tubería (primero grep) e imprime cualquier clave extraída del archivo de clave y no (-v ) el archivo grande.

Por supuesto, puede hacer esto con archivos temporales que debe controlar y recordar eliminar:

grep -o '[0-9]\{12\}'  keyfile >allkeys
grep -o '^[0-9]\{12\}' bigfile >usedkeys
grep -v -f usedkeys allkeys

Esto imprime todas las líneas allkeysque no aparecen en usedkeys.

Kevin
fuente
Desafortunadamente es lento , y recibo un error de memoria después de 40 segundos:grep: Memory exhausted
Peter.O
@ Peter.O Pero es correcto. De todos modos, por eso sugeriría una base de datos o comm, en ese orden.
Kevin
Sí, eso funciona, pero es mucho más lento que el bucle.
Teresa e Junior
1

El archivo de claves no cambia? Entonces debe evitar buscar las entradas antiguas una y otra vez.

Con tail -fusted puede obtener la salida de un archivo en crecimiento.

tail -f growingfile | grep -f keyfile 

grep -f lee los patrones de un archivo, una línea como patrón.

usuario desconocido
fuente
Eso sería bueno, pero el archivo de clave siempre es diferente.
Teresa e Junior
1

No iba a publicar mi respuesta porque pensé que esa cantidad de datos no debería procesarse con un script de shell, y ya se había dado la respuesta correcta para usar una base de datos. Pero desde ahora hay otros 7 enfoques ...

Lee el primer archivo en la memoria, luego toma el segundo archivo para buscar números y verifica si los valores están almacenados en la memoria. Debería ser más rápido que varios greps, si tiene suficiente memoria para cargar todo el archivo, eso es.

declare -a record
while read key
do
    read name
    read job
    record[$key]="$name:$job"
done < file1

for number in $(grep -o '[0-9]\{12\}' file2)
do
    [[ -n ${mylist[$number]} ]] || echo $number >> file3
done
forcefsck
fuente
Tengo suficiente memoria, pero esta me pareció aún más lenta. Gracias sin embargo!
Teresa e Junior
1

Estoy de acuerdo con @ jan-steinman que debe usar una base de datos para este tipo de tarea. Hay muchas maneras de hackear una solución con un script de shell como muestran las otras respuestas, pero hacerlo de esa manera conducirá a mucha miseria si vas a usar y mantener el código por un período de tiempo más largo que solo un proyecto descartable de un día.

Suponiendo que esté en una caja de Linux, lo más probable es que tenga Python instalado de forma predeterminada, que incluye la biblioteca sqlite3 a partir de Python v2.5. Puede verificar su versión de Python con:

% python -V
Python 2.7.2+

Recomiendo usar la biblioteca sqlite3 porque es una solución simple basada en archivos que existe para todas las plataformas (¡incluso dentro de su navegador web!) Y no requiere la instalación de un servidor. Esencialmente configuración cero y mantenimiento cero.

A continuación se muestra una secuencia de comandos de Python simple que analizará el formato de archivo que proporcionó como ejemplo y luego realiza una consulta simple de "seleccionar todo" y genera todo lo que almacena en la base de datos.

#!/usr/bin/env python

import sqlite3
import sys

dbname = '/tmp/simple.db'
filename = '/tmp/input.txt'
with sqlite3.connect(dbname) as conn:
    conn.execute('''create table if not exists people (key integer primary key, name text, job text)''')
    with open(filename) as f:
        for key in f:
            key = key.strip()
            name = f.next().strip()
            job = f.next().strip()
            try:
                conn.execute('''insert into people values (?,?,?)''', (key, name, job))
            except sqlite3.IntegrityError:
                sys.stderr.write('record already exists: %s, %s, %s\n' % (key, name, job))
    cur = conn.cursor()

    # get all people
    cur.execute('''select * from people''')
    for row in cur:
        print row

    # get just two specific people
    person_list = [1358726575123, 9973834728345]
    cur.execute('''select * from people where key in (?,?)''', person_list)
    for row in cur:
        print row

    # a more general way to get however many people are in the list
    person_list = [1358726575123, 9973834728345]
    template = ','.join(['?'] * len(person_list))
    cur.execute('''select * from people where key in (%s)''' % (template), person_list)
    for row in cur:
        print row

Sí, esto significa que necesitará aprender algo de SQL , pero a la larga valdrá la pena. Además, en lugar de analizar sus archivos de registro, tal vez podría escribir datos directamente en su base de datos sqlite.

aculich
fuente
¡Gracias por el script de Python! Creo que /usr/bin/sqlite3funciona de la misma manera para los scripts de shell ( packages.debian.org/squeeze/sqlite3 ), aunque nunca lo he usado.
Teresa e Junior
Sí, puede usar /usr/bin/sqlite3con scripts de shell, sin embargo, le recomiendo evitar los scripts de shell, excepto para los programas de descarte simples y en su lugar use un lenguaje como python que tenga un mejor manejo de errores y sea más fácil de mantener y crecer.
aculich