☰

加速腳本

tag-icon • tag-icon bash awk
加速腳本

哪個 shell 命令是解析數百萬行文字的最快方法。目前我在腳本中使用 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“允許””，“0”是“grep -c“拒絕””）

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的子字串作為第一個key
  • 將 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 等價物快了大約一千倍（請參閱修訂日誌），並為我們提供了多種日誌檔案可供使用。它是未排序的，因此需要整理輸入的兩個基準（下面的 3 和 4）正在使用單獨的排序版本（sort file > file-sorted需要 0m4.253s 才能完成）。

  1. 我的第一個：0m1.544s
  2. 我的重構defaultdict：0m1.413s
  3. Steeldriver 的awk：0m5.168s + 0m4.253s 排序
  4. 我的 Python 重新實作#3：0m1.489s + 0m4.253s 排序

我用 240 萬個不同的日期重複了這一生成（應該將我的前兩個日期推向極限）。這種排序花費了 0m6.999s。我還添加了pypyPython 版本的計時。

  1. 0m11.589s（0m7.080s 中pypy）
  2. 0m11.307s（0m7.087s 中pypy）
  3. 0米8.652秒+0米6.999秒
  4. 0m6.586s + 0m6.999s（0m1.566s 中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

相關內容