☰

Ускорить скрипт

tag-icon • tag-icon bash awk
Ускорить скрипт

Какая команда оболочки является самым быстрым способом разбора миллионов строк текста. В настоящее время я использую GREP в своем скрипте, но на его завершение уходят часы и часы.

Пример ввода:

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

Пример вывода:

(где «2» в первой строке — это «grep -c «allow»», а «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

решение1

Откажитесь от регулярных выражений. Они медленные (на любом языке) и их гораздо больше, чем нам нужно для простых сравнений подстрок.

  • Возьмите подстроку 0:20 в качестве первого ключа.
  • Возьмите подстроку 21:22 (один символ) в качестве логического результата для второго ключа.
  • Значение этой комбинации должно быть целым числом, которое вы просто увеличиваете каждый раз, когда видите его.

Ниже я реализовал эту идею на 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]))

Не знаю, как это работает, но попробуйте. Если это медленнее, преобразуйте его в C++ (немного больше PITA, поэтому я использую Python!), и это должно прорвать ваши данные. Это не сложное программирование, но это то, что нужно для оптимальной скорости.

Небольшой рефакторинг, сложнее портировать, если у вас нет эквивалента 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]))

И реализация гибрида идей steeldriver и моих на Python. Это, вероятно, наиболее эффективное использование памяти, которое вы получите, и оно использует сравнение подстрок, а не извлечение регулярных выражений, так что должно быть быстро.Однако для этого требовались отсортированные входные данные.

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

Бенчмаркинг

В целях проверки некоторых из этих данных (в том числе и из любопытства) я решил провести небольшой сравнительный анализ файла из 2 400 000 записей, охватывающих 2400 отдельных дат.

Я использовал следующий скрипт Python для создания большого файла со случайными окончаниями Allow/Deny:

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

Это было примерно в тысячу раз быстрее, чем эквивалент Bash (см. журнал ревизий) и дает нам разнообразный файл журнала для игры. Он не отсортирован, поэтому два бенчмарка, которым требуется объединенный ввод (3 и 4 ниже), используют отдельную отсортированную версию ( sort file > file-sortedна выполнение которой ушло 0m4.253s).

  1. Мой первый: 0м1.544с
  2. Мой рефакторинг с defaultdict: 0m1.413s
  3. Steeldriver's awk: 0м5.168с + 0м4.253с сортировка
  4. Моя переделка #3 на Python: сортировка 0m1.489s + 0m4.253s

Я повторил генерацию с 2,4 млн различных дат (должен был довести свои первые две до предела). Эта сортировка заняла 0м6.999с. Я также добавил pypyтайминги для версий Python.

  1. 0м11.589с (0м7.080с в pypy)
  2. 0м11.307с (0м7.087с в pypy)
  3. 0м8.652с + 0м6.999с
  4. 0м6.586с + 0м6.999с (0м1.566с в pypy)

Анализ и результаты

  • На небольших наборах клавиш лучше всего работают варианты 1 и 2. pypyПомогает на больших наборах клавиш.
  • 4 быстрее, чем 3, awkво многом потому, что мы не используем регулярные выражения
  • 4 — самый быстрый и наименее затратный, но только если данные поступают предварительно отсортированными
  • 2 — самый быстрый вариант, если у нас перемешанные данные
  • Внешняя сортировкаочень медленно.

решение2

Трудно предположить, будет ли это более эффективно, поскольку вы не опубликовали достаточно подробностей о том, чем вы сейчас занимаетесь, ноесли данные отсортированы в порядке временных метокЯ бы предложил алгоритм вроде

  • накапливает Allowи Denyсчитает до тех пор, пока не изменится временная метка (или мы не достигнем конца ввода)
  • вывести результат и (если мы не достигли конца ввода) сбросить счетчики

В awk это можно сделать как-то так:

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

Связанный контент