☰

Acelerar el guión

tag-icon • tag-icon bash awk
Acelerar el guión

¿Qué comando de shell es la forma más rápida de analizar millones de líneas de texto? Actualmente estoy usando GREP en mi script, pero me lleva horas terminarlo.

Entrada de muestra:

May  1 2014 00:00:00 Allow
May  1 2014 00:00:00 Allow
May  1 2014 01:00:00 Deny
May  1 2014 01:00:00 Deny
May  1 2014 02:00:00 Allow
May  1 2014 02:00:00 Deny

Salida de muestra:

(donde "2" en la línea uno es 'grep -c "permitir" ' y "0" es 'grep -c "denegar" ')

May 1 2014 00:00:00,2,0
May 1 2014 01:00:00,0,2
May 1 2014 02:00:00,1,1

Respuesta1

Aléjate de las expresiones regulares. Son lentos (en todos los idiomas) y son mucho más de lo que necesitamos aquí para lo que equivale a simples comparaciones de subcadenas.

  • Tome una subcadena de 0:20 como primera clave
  • Tome la subcadena de 21:22 (un solo carácter) como resultado booleano para la segunda clave.
  • El valor de esa combinación debe ser un número entero que simplemente incrementas cada vez que lo ves.

He implementado esa idea a continuación en Python:

data = {}
with open("file", "r") as f:
    for line in f:
        key = line[0:20]
        allowed = int(line[21:22] != "A")

        if not key in data:
            data[key] = [0,0]
        data[key][allowed] += 1

for key, val in data.items():
    print('%s,%d,%d' % (key, val[0], val[1]))

No tengo idea de cómo funciona, pero inténtalo. Si es más lento, conviértalo a C++ (un poco más PITA, ¡por eso estoy usando Python!) y eso debería eliminar sus datos. No es una programación difícil, pero es lo que se requiere para una velocidad óptima.

Un poco de refactorización, más difícil de portar a menos que tengas un equivalente a defaultdict:

from collections import defaultdict

data = defaultdict(lambda: [0,0])
with open("file", "r") as f:
    for line in f:
        key = line[0:20]
        allowed = int(line[21:22] != "A")
        data[key][allowed] += 1

for key, val in data.items():
    print('%s,%d,%d' % (key, val[0], val[1]))

Y una implementación en Python de un híbrido de las ideas de Steeldriver y las mías. Esta es probablemente la memoria más eficiente que obtendrá y utiliza una comparación de subcadenas en lugar de una extracción de expresiones regulares, por lo que debería ser ágil.Sin embargo, requirió una entrada ordenada.

last = ""
score = [0,0]

with open("file", "r") as f:
    for line in f:
        key = line[0:20]
        allowed = int(line[21:22] != "A")

        if key and key != last:
            print '%s,%d,%d' % (last, score[0], score[1])
            score = [0,0]
            last = key

        score[allowed] += 1

print '%s,%d,%d' % (last, score[0], score[1])

Evaluación comparativa

Con el fin de probar algo de esto (por mi propia curiosidad, más que por cualquier otra cosa), decidí hacer una pequeña evaluación comparativa en un archivo de 2.400.000 registros que cubre 2400 fechas distintas.

Utilicé el siguiente script de Python para generar un archivo grande con terminaciones aleatorias de Permitir/Denegar:

import itertools, datetime, random

CHOICES = ['Allow', 'Deny']

with open("file", "w") as f:
    for _ in itertools.repeat(None, 2400):
        epoch = random.randint(1, 1404226041)
        d = datetime.datetime.fromtimestamp(epoch)
        print d
        dstr = d.strftime('%b %d %Y %X')

        for _ in itertools.repeat(None, 1000):
            f.write('%s %s\n' % (dstr, CHOICES[random.randint(0,1)]))

Esto fue aproximadamente mil veces más rápido que el equivalente de Bash (consulte el registro de revisión) y nos brinda un archivo de registro diverso para jugar. No está ordenado, por lo que los dos puntos de referencia que necesitan datos intercalados (3 y 4 a continuación) utilizan una versión ordenada separada ( sort file > file-sortedque tardó 0m4,253s en completarse).

  1. Mi primero: 0m1.544s
  2. Mi refactor con defaultdict: 0m1.413s
  3. Steeldriver awk: 0m5.168s + 0m4.253s clasificación
  4. Mi reimplementación de Python del n.° 3: clasificación 0m1.489s + 0m4.253s

Repetí la generación con 2,4 millones de fechas distintas (debería llevar mis dos primeras al límite). Este tipo tomó 0m6.999s. También agregué pypytiempos para las versiones de Python.

  1. 0m11.589s (0m7.080s en pypy)
  2. 0m11.307s (0m7.087s en pypy)
  3. 0m8.652s + 0m6.999s
  4. 0m6.586s + 0m6.999s (0m1.566s en pypy)

Análisis y resultados

  • En conjuntos de claves pequeños, 1 y 2 funcionan mejor. pypyayuda en conjuntos de claves más grandes.
  • 4 es más rápido que 3 awken gran parte porque no estamos regexionando
  • 4 es más rápido y ocupa menos espacio, pero solo si los datos vienen preclasificados
  • 2 es más rápido si tenemos datos mezclados
  • La clasificación externa esrealmente lento.

Respuesta2

Es difícil adivinar si podría ser más eficiente ya que no has publicado suficientes detalles sobre lo que estás haciendo ahora, perosi los datos están ordenados en orden de marca de tiempoYo sugeriría un algoritmo algo así como

  • acumular Allowy Denycuenta hasta que cambie la marca de tiempo (o lleguemos al final de la entrada)
  • imprimir el resultado y (si no hemos llegado al final de la entrada) restablecer los recuentos

En awk, podrías hacer eso como algo como

awk '

FNR==1 {t = $1FS$2FS$3FS$4}

$1FS$2FS$3FS$4 == t {
  a += $5=="Allow" ? 1 : 0
  d += $5=="Deny" ? 1 : 0
}

$1FS$2FS$3FS$4 != t {
  printf "%s,%d,%d\n",t,a,d
  a = $5=="Allow" ? 1 : 0
  d = $5=="Deny" ? 1 : 0
  t = $1FS$2FS$3FS$4
}

END {printf "%s,%d,%d\n",t,a,d}

' input

información relacionada