☰

Skript beschleunigen

tag-icon • tag-icon bash awk
Skript beschleunigen

Welcher Shell-Befehl ist der schnellste Weg, um Millionen von Textzeilen zu analysieren? Momentan verwende ich GREP in meinem Skript, aber es dauert stundenlang, bis es fertig ist.

Beispieleingabe:

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

Beispielausgabe:

(wobei „2“ in Zeile eins „grep -c „allow““ bedeutet und „0“ „grep -c „deny““ bedeutet)

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

Antwort1

Verabschieden Sie sich von regulären Ausdrücken. Sie sind langsam (in jeder Sprache) und weit mehr, als wir hier für einfache Teilstringvergleiche benötigen.

  • Nehmen Sie eine Teilzeichenfolge von 0:20 als ersten Schlüssel
  • Nehmen Sie die Teilzeichenfolge von 21:22 (einzelnes Zeichen) als Boolean-Ergebnis für den zweiten Schlüssel
  • Der Wert dieser Kombination sollte eine Ganzzahl sein, die Sie jedes Mal erhöhen, wenn Sie sie sehen.

Ich habe diese Idee unten in Python implementiert:

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

Keine Ahnung, wie das funktioniert, aber probieren Sie es aus. Wenn das langsamer ist, konvertieren Sie es in C++ (etwas mühsamer, deshalb verwende ich Python!) und das sollte Ihre Daten durcharbeiten. Es ist keine schwierige Programmierung, aber es ist das, was für optimale Geschwindigkeit erforderlich ist.

Ein wenig Refactoring, schwieriger zu portieren, sofern Sie nicht über ein Äquivalent zu 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]))

Und eine Python-Implementierung eines Hybrids aus Steeldrivers und meinen Ideen. Dies ist wahrscheinlich die speichereffizienteste, die Sie bekommen werden, und es verwendet einen Teilstringvergleich statt einer Regex-Extraktion, sollte also schnell sein.Es war jedoch eine sortierte Eingabe erforderlich.

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

Benchmarking

Um einiges davon zu testen (mehr aus Neugier als aus anderen Gründen) habe ich mich dazu entschlossen, ein kleines Benchmarking anhand einer Datei mit 2.400.000 Datensätzen durchzuführen, die 2.400 einzelne Daten abdeckt.

Ich habe das folgende Python-Skript verwendet, um eine große Datei mit zufälligen Allow/Deny-Endungen zu generieren:

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

Dies war etwa tausendmal schneller als das Bash-Äquivalent (siehe Revisionsprotokoll) und bietet uns eine abwechslungsreiche Protokolldatei zum Spielen. Sie ist unsortiert, sodass die beiden Benchmarks, die sortierte Eingaben benötigen (3 und 4 unten), eine separate sortierte Version verwenden ( sort file > file-sorteddie 0m4.253s dauerte).

  1. Mein erstes: 0m1.544s
  2. Mein Refactoring mit defaultdict: 0m1.413s
  3. Steeldriver awk: 0 m 5,168 s + 0 m 4,253 s Sortieren
  4. Meine Python-Neuimplementierung von #3: 0m1.489s + 0m4.253s Sortierung

Ich habe die Generierung mit 2,4 Millionen unterschiedlichen Daten wiederholt (das sollte meine ersten beiden an ihre Grenzen bringen). Diese Sortierung dauerte 0m6.999s. Ich habe auch pypyZeitangaben für die Python-Versionen hinzugefügt.

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

Analyse und Ergebnisse

  • Bei kleinen Keysets funktionieren 1 und 2 beide am besten. pypyhilft bei größeren Keysets.
  • 4 ist schneller als 3, awkvor allem, weil wir keine regulären Ausdrücke verwenden.
  • 4 ist am schnellsten und hat den geringsten Platzbedarf, aber nur, wenn die Daten vorsortiert sind
  • 2 ist am schnellsten, wenn wir durcheinander geratene Daten haben
  • Externe Sortierung istwirklich langsam.

Antwort2

Es ist schwer zu erraten, ob es effizienter wäre, da Sie nicht genügend Details darüber gepostet haben, was Sie jetzt tun, aberwenn die Daten in der Reihenfolge des Zeitstempels sortiert sindIch würde einen Algorithmus vorschlagen, der ungefähr so ​​aussieht:

  • akkumuliere die Allowund DenyZählungen, bis sich der Zeitstempel ändert (oder wir das Ende der Eingabe erreichen)
  • Drucken Sie das Ergebnis aus und setzen Sie die Zählwerte zurück (falls wir das Ende der Eingabe noch nicht erreicht haben).

In awk könnten Sie das etwa so machen:

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

verwandte Informationen