Быстрое вычисление математического выражения (функции) для большого количества входных значений

Поскольку вы спросили об asteval, существует способ использовать его и получить более быстрые результаты:

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()

То есть вы можете сначала проанализировать («предварительно скомпилировать») функцию пользовательского ввода, а затем вставить каждое новое значение x в таблицу символов и использовать Interpreter.run() для оценки скомпилированного выражения для этого значения. В вашем масштабе, я думаю, это приблизит вас к 0,5 секунды.

Если вы хотите использовать numpy, гибридное решение:

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()

должно быть намного быстрее и сравнимо по времени выполнения с использованием numexpr.

В прошлом я с большим успехом использовал библиотеку C ++ ExprTK. Здесь приведен эталонный тест скорости среди других синтаксических анализаторов C ++ (например, Muparser, MathExpr, ATMSP и т. Д.), И ExprTK выходит на первое место.

Для ExprTK есть оболочка Python под названием cexprtk, которую я использовал и нашел ее очень быстрой. Вы можете скомпилировать математическое выражение только один раз, а затем вычислить это сериализованное выражение столько раз, сколько потребуется. Вот простой пример кода с использованием cexprtk с userinput_function:

import cexprtk
import time

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)

time_start = time.time()
x = 1

st = cexprtk.Symbol_Table({"x":x}, add_constants = True) # Setup the symbol table
Expr = cexprtk.Expression(userinput_function, st) # Apply the symbol table to the userinput_function

for x in range(0,demo_len,1):
    st.variables['x'] = x # Update the symbol table with the new x value
    Expr() # evaluate expression
time_end = time.time()

print('1 cexprtk: ' + str(round(time_end - time_start, 4)) + ' seconds')

На моей машине (Linux, двухъядерный, 2,5 ГГц) для демонстрационной длины 20000 это выполняется за 0,0202 секунды.

Для демонстрации длиной 2 000 000 cexprtk завершается за 1,23 секунды.

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, и масштабируется почти так же, как _3 _ + _ 4_ (шаг compile немного медленнее, чем у eval, и eval будет предварительно вычислять все, что может (1+1+x компилируется как 2+x).

Для сравнения, eval завершает тест 20k за 0,0125 секунды, а makefunction завершает за 0,014 секунды. При увеличении количества итераций до 2 000 000, eval завершается за 1,23 секунды, а makefunction - за 1,32 секунды.

Интересное замечание: pypy признает, что eval и makefunction производят, по сути, одну и ту же функцию, поэтому JIT-разминка для первого ускоряет выполнение второго.

Если вы передаете строку в sympy.simplify (что не рекомендуется; рекомендуется использовать sympify явно), это будет использовать sympy.sympify для преобразования ее в выражение SymPy, которое использует eval внутри.

Я не программист на Python, поэтому не могу предоставить код Python. Но я думаю, что могу предоставить простую схему, которая минимизирует ваши зависимости и при этом работает довольно быстро.

Ключевым моментом здесь является создание чего-то, что близко к eval, но не является eval. Итак, что вы хотите сделать, так это «скомпилировать» пользовательское уравнение во что-то, что можно быстро оценить. ОП показал ряд решений.

Вот другой, основанный на оценке уравнения как Обратное полирование.

Для обсуждения предположим, что вы можете преобразовать уравнение в RPN (обратная полировка). Это означает, что операнды предшествуют операторам, например, для пользовательской формулы:

        sqrt(x**2 + y**2)

вы получите эквивалентное чтение RPN слева направо:

          x 2 ** y 2 ** + sqrt

Фактически, мы можем рассматривать «операнды» (например, переменные и константы) как операторы, которые принимают нулевые операнды. Теперь все в РПН - это оператор.

Если мы будем рассматривать каждый элемент оператора как токен (предположим, что уникальное маленькое целое число, записанное ниже как «RPNelement» ниже для каждого), и сохраним их в массиве «RPN», мы можем вычислить такую ​​формулу с помощью раскрывающегося списка складываются довольно быстро:

       stack = {};  // make the stack empty
       do i=1,len(RPN),1
          case RPN[i]:
              "0":  push(stack,0);
              "1": push(stack,1);
              "+":  push(stack,pop(stack)+pop(stack));break;
               "-": push(stack,pop(stack)-pop(stack));break;
               "**": push(stack,power(pop(stack),pop(stack)));break;
               "x": push(stack,x);break;
               "y": push(stack,y);break;
               "K1": push(stack,K1);break;
                ... // as many K1s as you have typical constants in a formula
           endcase
       enddo
       answer=pop(stack);

Вы можете встроить операции для push и pop, чтобы немного ускорить его. Если предоставленный RPN правильно сформирован, этот код совершенно безопасен.

Теперь, как получить РПН? Ответ: создайте небольшой рекурсивный анализатор спуска, действия которого добавляют операторы RPN к массиву RPN. См. мой SO-ответ о том, как легко создать синтаксический анализатор рекурсивного спуска для типичных уравнений.

Вам нужно будет организовать, чтобы константы, встречающиеся при синтаксическом анализе, помещались в K1, K2, ... если они не являются специальными, часто встречающимися значениями (как я показал для "0" и "1"; вы можете добавить больше, если это полезно ).

Это решение должно состоять максимум из нескольких сотен строк и не иметь никаких зависимостей от других пакетов.

(Эксперты по Python: не стесняйтесь редактировать код, чтобы сделать его Pythonesque).