☰

Acelerar roteiro

tag-icon • tag-icon bash awk
Acelerar roteiro

Qual comando shell é a maneira mais rápida de analisar milhões de linhas de texto. Atualmente estou usando o GREP no meu script, mas leva horas e horas para terminar.

Entrada de amostra:

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

Saída de amostra:

(onde "2" na linha um é 'grep -c "allow" ' e "0" é 'grep -c "deny" ')

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

Responder1

Afaste-se das expressões regulares. Eles são lentos (em todos os idiomas) e são muito mais do que precisamos aqui para o que equivale a simples comparações de substrings.

  • Pegue uma substring de 0:20 como a primeira chave
  • Pegue a substring de 21:22 (caractere único) como resultado booleano para a segunda chave
  • O valor dessa combinação deve ser um número inteiro que você incrementa cada vez que o vê.

Implementei essa ideia abaixo em 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]))

Não tenho ideia de como isso funciona, mas experimente. Se for mais lento, converta-o para C++ (um pouco mais PITA, e é por isso que estou usando Python!) E isso deve destruir seus dados. Não é uma programação difícil, mas é o que é necessário para uma velocidade ideal.

Um pouco de refatoração, mais difícil de portar, a menos que você tenha um 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]))

E uma implementação em Python de um híbrido de ideias do steeldriver e minhas. Este é provavelmente o uso mais eficiente de memória que você obterá e está usando comparação de substring em vez de extração de regex, portanto, deve ser rápido.Porém, era necessária uma entrada classificada.

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])

avaliação comparativa

No interesse de testar um pouco disso (para minha própria curiosidade, tanto quanto para qualquer outra coisa), decidi fazer um pequeno benchmarking em um arquivo de 2.400.000 registros que cobre 2.400 datas separadas.

Usei o seguinte script Python para gerar um arquivo grande com finais aleatórios de Permitir/Negar:

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)]))

Isso foi cerca de mil vezes mais rápido que o equivalente do Bash (veja o log de revisão) e nos dá um arquivo de log diversificado para brincar. Não está classificado, portanto, os dois benchmarks que precisam de entrada agrupada (3 e 4 abaixo) estão usando uma versão classificada separada ( sort file > file-sortedque levou 0m4.253s para ser concluída).

  1. Meu primeiro: 0m1.544s
  2. Meu refatorador com defaultdict: 0m1.413s
  3. Steeldriver's awk: classificação 0m5.168s + 0m4.253s
  4. Minha reimplementação Python do nº 3: classificação 0m1.489s + 0m4.253s

Repeti a geração com 2,4 milhões de datas distintas (deveria levar as minhas duas primeiras ao limite). Essa classificação levou 0m6.999s. Também adicionei pypytempos para as versões Python.

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

Análise e resultados

  • Em conjuntos de chaves pequenos, 1 e 2 apresentam melhor desempenho. pypyajuda em conjuntos de chaves maiores.
  • 4 é mais rápido que 3 awkem grande parte porque não estamos fazendo regex
  • 4 é mais rápido e tem o menor espaço ocupado, mas somente se os dados vierem pré-classificados
  • 2 é mais rápido se tivermos dados confusos
  • A classificação externa émuito devagar.

Responder2

É difícil adivinhar se seria mais eficiente, já que você não postou detalhes suficientes sobre o que está fazendo agora, masse os dados forem classificados em ordem de carimbo de data/horaEu sugeriria um algoritmo algo como

  • acumulamos Allowe Denycontamos até que o carimbo de data/hora mude (ou cheguemos ao final da entrada)
  • imprima o resultado e (se não chegarmos ao final da entrada) reinicie as contagens

No awk, você poderia fazer isso 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

informação relacionada