17

以下の質問

そして、それぞれの回答により、（多かれ少なかれ信頼されている）ユーザーから与えられた単一の数式（この回答https://stackoverflow.com/a/594294/1672565の行に沿った一般的な用語）を効率的に解析する方法を考えさせられましたデータベースからの 20k から 30k の入力値の場合。さまざまなソリューションを比較できるように、簡単で汚いベンチマークを実装しました。

# Runs with Python 3(.4)
import pprint
import time

# This is what I have
userinput_function = '5*(1-(x*0.1))' # String - numbers should be handled as floats
demo_len = 20000 # Parameter for benchmark (20k to 30k in real life)
print_results = False

# Some database, represented by an array of dicts (simplified for this example)

database_xy = []
for a in range(1, demo_len, 1):
    database_xy.append({
        'x':float(a),
        'y_eval':0,
        'y_sympya':0,
        'y_sympyb':0,
        'y_sympyc':0,
        'y_aevala':0,
        'y_aevalb':0,
        'y_aevalc':0,
        'y_numexpr': 0,
        'y_simpleeval':0
        })

# 解決策 #1: eval [はい、完全に安全ではありません]

time_start = time.time()
func = eval("lambda x: " + userinput_function)
for item in database_xy:
    item['y_eval'] = func(item['x'])
time_end = time.time()
if print_results:
    pprint.pprint(database_xy)
print('1 eval: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #2a: sympy - evalf ( http://www.sympy.org )

import sympy
time_start = time.time()
x = sympy.symbols('x')
sympy_function = sympy.sympify(userinput_function)
for item in database_xy:
    item['y_sympya'] = float(sympy_function.evalf(subs={x:item['x']}))
time_end = time.time()
if print_results:
    pprint.pprint(database_xy)
print('2a sympy: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #2b: sympy - lambdify ( http://www.sympy.org )

from sympy.utilities.lambdify import lambdify
import sympy
import numpy
time_start = time.time()
sympy_functionb = sympy.sympify(userinput_function)
func = lambdify(x, sympy_functionb, 'numpy') # returns a numpy-ready function
xx = numpy.zeros(len(database_xy))
for index, item in enumerate(database_xy):
    xx[index] = item['x']
yy = func(xx)
for index, item in enumerate(database_xy):
    item['y_sympyb'] = yy[index]
time_end = time.time()
if print_results:
    pprint.pprint(database_xy)
print('2b sympy: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #2c: sympy - numexpr [および numpy] を使用した lambdify ( http://www.sympy.org )

from sympy.utilities.lambdify import lambdify
import sympy
import numpy
import numexpr
time_start = time.time()
sympy_functionb = sympy.sympify(userinput_function)
func = lambdify(x, sympy_functionb, 'numexpr') # returns a numpy-ready function
xx = numpy.zeros(len(database_xy))
for index, item in enumerate(database_xy):
    xx[index] = item['x']
yy = func(xx)
for index, item in enumerate(database_xy):
    item['y_sympyc'] = yy[index]
time_end = time.time()
if print_results:
    pprint.pprint(database_xy)
print('2c sympy: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #3a: [ast に基づく] asteval - 文字列マジックを使用 ( http://newville.github.io/asteval/index.html )

from asteval import Interpreter
aevala = Interpreter()
time_start = time.time()
aevala('def func(x):\n\treturn ' + userinput_function)
for item in database_xy:
    item['y_aevala'] = aevala('func(' + str(item['x']) + ')')
time_end = time.time()
if print_results:
    pprint.pprint(database_xy)
print('3a aeval: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #3b (M Newville): asteval [ast に基づく] - 解析して実行 ( http://newville.github.io/asteval/index.html )

from asteval import Interpreter
aevalb = Interpreter()
time_start = time.time()
exprb = aevalb.parse(userinput_function)
for item in database_xy:
    aevalb.symtable['x'] = item['x']
    item['y_aevalb'] = aevalb.run(exprb)
time_end = time.time()
print('3b aeval: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #3c (M Newville): asteval [ast に基づく] - 解析して numpy で実行 ( http://newville.github.io/asteval/index.html )

from asteval import Interpreter
import numpy
aevalc = Interpreter()
time_start = time.time()
exprc = aevalc.parse(userinput_function)
x = numpy.array([item['x'] for item in database_xy])
aevalc.symtable['x'] = x
y = aevalc.run(exprc)
for index, item in enumerate(database_xy):
    item['y_aevalc'] = y[index]
time_end = time.time()
print('3c aeval: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #4: simpleeval [ast に基づく] ( https://github.com/danthedeckie/simpleeval )

from simpleeval import simple_eval
time_start = time.time()
for item in database_xy:
    item['y_simpleeval'] = simple_eval(userinput_function, names={'x': item['x']})
time_end = time.time()
if print_results:
    pprint.pprint(database_xy)
print('4 simpleeval: ' + str(round(time_end - time_start, 4)) + ' seconds')

# 解決策 #5 numexpr [および numpy] ( https://github.com/pydata/numexpr )

import numpy
import numexpr
time_start = time.time()
x = numpy.zeros(len(database_xy))
for index, item in enumerate(database_xy):
    x[index] = item['x']
y = numexpr.evaluate(userinput_function)
for index, item in enumerate(database_xy):
    item['y_numexpr'] = y[index]
time_end = time.time()
if print_results:
    pprint.pprint(database_xy)
print('5 numexpr: ' + str(round(time_end - time_start, 4)) + ' seconds')

私の古いテスト マシン (Python 3.4、Linux 3.11 x86_64、2 コア、1.8GHz) では、次の結果が得られます。

1 eval: 0.0185 seconds
2a sympy: 10.671 seconds
2b sympy: 0.0315 seconds
2c sympy: 0.0348 seconds
3a aeval: 2.8368 seconds
3b aeval: 0.5827 seconds
3c aeval: 0.0246 seconds
4 simpleeval: 1.2363 seconds
5 numexpr: 0.0312 seconds

際立っているのはevalの信じられないほどの速度ですが、これを実際に使用したくはありません。2 番目に最適な解決策は、 numpyに依存するnumexprのようです。これは避けたい依存関係ですが、これは難しい要件ではありません。次善の策は、 astを中心に構築されたsimpleevalです。別のastベースのソリューションであるaevalは、最初にすべてのfloat入力値を文字列に変換する必要があるという事実に苦しんでおり、その周りで方法を見つけることができませんでした。sympyは、最も柔軟で明らかに最も安全なソリューションを提供するため、最初は私のお気に入りでしたが、最後から 2 番目のソリューションまでの印象的な距離で最後になりました。

更新 1 : sympyを使用したはるかに高速なアプローチがあります。解決策 2b を参照してください。sympyが実際に内部で使用しているかどうかはわかりませんが、numexprとほぼ同じです。

更新 2 : sympyの実装は、simplify の代わりに sympify を使用するようになりました (主任開発者 asmeurer の推奨による - 感謝)。明示的に要求されない限り、 numexprを使用していません (解決策 2c を参照)。また、 astevalに基づく 2 つの大幅に高速なソリューションを追加しました (M Newville に感謝)。

比較的安全なソリューションをさらに高速化するには、どのようなオプションが必要ですか? たとえば、 ast を直接使用する他の安全な(-ish)アプローチはありますか?

4

5 に答える 5

2

Since you asked about asteval, there is a way to use it and get faster results:

aeval = Interpreter()
time_start = time.time()
expr = aeval.parse(userinput_function)
for item in database_xy:
    aeval.symtable['x'] = item['x']
    item['y_aeval'] = aeval.run(expr)
time_end = time.time()

That is, you can first parse ("pre-compile") the user input function, and then insert each new value of x into the symbol table and the use Interpreter.run() to evaluate the compiled expression for that value. On your scale, I think this will get you close to 0.5 seconds.

If you are willing to use numpy, a hybrid solution:

aeval = Interpreter()
time_start = time.time()
expr = aeval.parse(userinput_function)
x = numpy.array([item['x'] for item in database_xy])
aeval.symtable['x'] = x
y = aeval.run(expr)
time_end = time.time()

should be much faster, and comparable in run time to using numexpr.

于 2015-12-10T04:12:16.257 に答える
2

CPython (および pypy) は、関数の実行に非常に単純なスタック言語を使用します。また、ast モジュールを使用してバイトコードを自分で作成するのはかなり簡単です。

import sys
PY3 = sys.version_info.major > 2
import ast
from ast import parse
import types
from dis import opmap

ops = {
    ast.Mult: opmap['BINARY_MULTIPLY'],
    ast.Add: opmap['BINARY_ADD'],
    ast.Sub: opmap['BINARY_SUBTRACT'],
    ast.Div: opmap['BINARY_TRUE_DIVIDE'],
    ast.Pow: opmap['BINARY_POWER'],
}
LOAD_CONST = opmap['LOAD_CONST']
RETURN_VALUE = opmap['RETURN_VALUE']
LOAD_FAST = opmap['LOAD_FAST']
def process(consts, bytecode, p, stackSize=0):
    if isinstance(p, ast.Expr):
        return process(consts, bytecode, p.value, stackSize)
    if isinstance(p, ast.BinOp):
        szl = process(consts, bytecode, p.left, stackSize)
        szr = process(consts, bytecode, p.right, stackSize)
        if type(p.op) in ops:
            bytecode.append(ops[type(p.op)])
        else:
            print(p.op)
            raise Exception("unspported opcode")
        return max(szl, szr) + stackSize + 1
    if isinstance(p, ast.Num):
        if p.n not in consts:
            consts.append(p.n)
        idx = consts.index(p.n)
        bytecode.append(LOAD_CONST)
        bytecode.append(idx % 256)
        bytecode.append(idx // 256)
        return stackSize + 1
    if isinstance(p, ast.Name):
        bytecode.append(LOAD_FAST)
        bytecode.append(0)
        bytecode.append(0)
        return stackSize + 1
    raise Exception("unsupported token")

def makefunction(inp):
    def f(x):
        pass

    if PY3:
        oldcode = f.__code__
        kwonly = oldcode.co_kwonlyargcount
    else:
        oldcode = f.func_code
    stack_size = 0
    consts = [None]
    bytecode = []
    p = ast.parse(inp).body[0]
    stack_size = process(consts, bytecode, p, stack_size)
    bytecode.append(RETURN_VALUE)
    bytecode = bytes(bytearray(bytecode))
    consts = tuple(consts)
    if PY3:
        code = types.CodeType(oldcode.co_argcount, oldcode.co_kwonlyargcount, oldcode.co_nlocals, stack_size, oldcode.co_flags, bytecode, consts, oldcode.co_names, oldcode.co_varnames, oldcode.co_filename, 'f', oldcode.co_firstlineno, b'')
        f.__code__ = code
    else:
        code = types.CodeType(oldcode.co_argcount, oldcode.co_nlocals, stack_size, oldcode.co_flags, bytecode, consts, oldcode.co_names, oldcode.co_varnames, oldcode.co_filename, 'f', oldcode.co_firstlineno, '')
        f.func_code = code
    return f

これには、基本的に と同じ関数を生成するという明確な利点があり、 +evalとほぼ同じようにスケーリングします(ステップはのものよりもわずかに遅く、可能なものはすべて事前計算します (としてコンパイルされます)。compileevalcompileevaleval1+1+x2+x

比較のために、eval20k テストを 0.0125 秒でmakefunction終了し、0.014 秒で終了します。反復回数を 2,000,000 に増やすとeval、1.23 秒でmakefunction終了し、1.32 秒で終了します。

興味深いことに、pypy はそれを認識し、本質的に同じ関数evalをmakefunction生成するため、最初の JIT ウォームアップは 2 番目のウォームアップを加速します。

于 2016-07-29T19:44:30.183 に答える