☰

スクリプトの高速化

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

サンプル出力:

(1 行目の「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の部分文字列（1文字）を2番目のキーのブール結果として取得します。
  • その組み合わせの値は、表示されるたびに増加する整数である必要があります。

私はそのアイデアを以下のように 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])

ベンチマーク

このうちいくつかをテストしてみるため (何よりも私自身の好奇心のため)、2,400 の個別の日付をカバーする 2,400,000 件のレコード ファイルでちょっとしたベンチマークを行うことにしました。

次の 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 の同等のものより約 1000 倍高速で (リビジョン ログを参照)、さまざまなログ ファイルで操作できます。これはソートされていないため、照合された入力を必要とする 2 つのベンチマーク (以下の 3 と 4) では、別のソートされたバージョンが使用されています (sort file > file-sorted完了までに 0 分 4.253 秒かかりました)。

  1. 私の最初の記録: 0分1秒544
  2. 私のリファクタリングdefaultdict: 0分1.413秒
  3. スチールドライバーズawk: 0分5秒168秒 + 0分4秒253秒 ソート
  4. 私の Python による #3 の再実装: 0 分 1.489 秒 + 0 分 4.253 秒のソート

240 万の異なる日付で生成を繰り返しました (最初の 2 つを限界まで押し上げるはずです)。このソートには 0 分 6.999 秒かかりました。Pythonpypyバージョンのタイミングも追加しました。

  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

関連情報