☰

스크립트 속도 향상

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

벤치마킹

이 중 일부를 테스트하기 위해(다른 무엇보다도 내 호기심을 위해) 2400개의 개별 날짜를 포함하는 2,400,000개의 레코드 파일에 대해 약간의 벤치마킹을 수행하기로 결정했습니다.

다음 Python 스크립트를 사용하여 무작위로 허용/거부로 끝나는 큰 파일을 생성했습니다.

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에 상응하는 것보다 약 1000배 빠르며(개정 로그 참조) 우리에게 다양한 로그 파일을 제공합니다. 정렬되지 않았기 때문에 대조 입력이 필요한 두 벤치마크(아래 3과 4)는 별도의 정렬 버전을 사용하고 있습니다( sort file > file-sorted완료하는 데 0m4.253초 소요).

  1. 내 첫 번째: 0m1.544s
  2. 내 리팩토링 defaultdict: 0m1.413s
  3. Steeldriver's awk: 0m5.168s + 0m4.253s 정렬
  4. #3의 내 Python 재구현: 0m1.489s + 0m4.253s 정렬

나는 240만 개의 서로 다른 날짜로 생성을 반복했습니다(처음 두 개는 한계까지 밀어붙여야 합니다). 이 정렬에는 0m6.999s가 걸렸습니다. 또한 pypyPython 버전에 대한 타이밍 도 추가했습니다 .

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

분석 및 결과

  • 작은 키 세트에서는 1과 2가 모두 가장 좋은 성능을 발휘합니다. pypy더 큰 키 세트에 도움이 됩니다.
  • awk4는 정규식을 사용하지 않기 때문에 3보다 빠릅니다.
  • 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

관련 정보