小町算(3)

evalする代わりに自分でパーサを書いた。

# komachi_parser.py
# -*- coding: utf-8 -*-

def e(L):
    '+, -を処理'
    v1 = t(L)
    while True:
        if L and (L[0] == '+' or L[0] == '-'):
            op = L.pop(0)
            v2 = t(L)
            if op == '+':
                val = v1 + v2
            elif op == '-':
                val = v1 - v2
            v1 = val
        else:
            break
    return v1

def t(L):
    '*, /を処理'
    v1 = f(L)
    while True:
        if L and (L[0] == '*' or L[0] == '/'):
            op = L.pop(0)
            v2 = f(L)
            if op == '*':
                val = v1 * v2
            elif op == '/':
                val = v1 / v2
            v1 = val
        else:
            break
    return v1

def f(L):
    '数値を処理'
    if L and L[0].isdigit():
        return int(L.pop(0))
    else:
        raise ValueError

if __name__ == '__main__':
    print e( ['1234', '-', '5', '*', '6', '/', '7', '-', '8', '*', '9'] )

自分のパーサとevalによるパースとで時間を比較してみた。

import komachi_parser
import re, time

a = ['1']
for n in map(str, range(2, 10)):
    b = []
    for s in a:
        for o in ['+', '-', '*', '/', '']:
            b += [s+o+n]
    a = b

t = time.time()
cnt=0
p = re.compile(r'([^\d])')
for exp in a:
    exp2 = re.split(p, exp)
    if komachi_parser.e(exp2) == 100:
        cnt += 1
print '%d pattern(s), %g sec' % (cnt, time.time() - t)

t = time.time()
cnt=0
for e in a:
    if eval(e) == 100:
        cnt += 1
print '%d pattern(s), %g sec' % (cnt, time.time() - t)

# 303 pattern(s), 16.091 sec
# 303 pattern(s), 14.311 sec

timeモジュールなので時間計測の精度は悪いかもしれないが、約2秒近く違う。evalはビルトインなのでCで書かれていると思うが、自分のパーサはPythonで書いてあるので決め打ちの単純な処理しかしていないのに遅い。exp2を作るのに、一度文字列を作ってsplitするのではなく、直接生成すれば若干早くなる可能性はある。

しかし、特殊なアルゴリズムでも考えない限り、k.inabaさんのような「リスト作成 + 式評価」を同時に行う方法が一番早いと思われる。