☰

加速脚本

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 "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++（有点麻烦，这就是我使用 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.253 秒完成）。

  1. 我的第一个：0分1.544秒
  2. 我的重构时间defaultdict：0m1.413s
  3. Steeldriver 的awk: 0m5.168s + 0m4.253s 排序
  4. 我对 #3 的 Python 重新实现：0m1.489s + 0m4.253s 排序

我重复了 240 万个不同日期的生成过程（应该会将我的前两个日期推到极限）。此排序耗时 0 分 6.999 秒。我还添加了pypyPython 版本的计时。

  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

相关内容