Конечно, вы должны сначала измерить накладные расходы, прежде чем приступить к оптимизации, поскольку ваш генетический алгоритм следующего поколения и мутации могут затянуть время оценки.
Как только вы определились, вы хотите оптимизировать ...
очевидный ответ состоит в том, чтобы скомпилировать выражение («как можно больше»). К счастью, есть много способов «скомпилировать».
Если вы реализуете это в Python, вы можете попросить Python (я не эксперт) скомпилировать построенное абстрактное синтаксическое дерево в функцию, и это может быть намного быстрее, особенно если CPython поддерживает это .
Однако, похоже, вы реализуете это на C ++. В этом случае я бы не стал оценивать дерево выражений в том виде, как вы его определили, так как оно требует большого количества обходов деревьев, косвенных вызовов функций и т. Д., Которые довольно дороги.
Один хитрый трюк состоит в том, чтобы выложить фактическое выражение в виде текстовой строки с соответствующим текстом тела функции C ++ вокруг него в файл и запустить на этом компилятор C ++.
Вы можете автоматизировать все spit-compile-relink с достаточным количеством скриптов, так что если
Вы делаете это редко, это будет работать, и вы получите оценку выражения так быстро, как
машина может это сделать.
В предположении, что вы не хотите этого делать, у меня будет искушение пройтись по вашему дереву выражений до того, как вы запустите процесс оценки и "скомпилируете" это дерево в набор сохраненных действий. в линейном массиве под названием «код». Действия будут определены перечислением:
enum actions {
// general actions first
pushx, // action to push x on a stack
push1,
push2, // action to push 2 on a stack
...
pushN,
add,
sub,
mul, // action multiply top two stack elements together
div,
...
// optimized actions
add1,
sub1,
mul1,
div1, // action to divide top stack element by 1
...
addN,
subN,
...
addx,
subX,
...
}
В этом случае я определил действия по реализации оценщика выражений стека с понижением, потому что это легко понять. К счастью, ваш словарный запас выражений довольно ограничен, поэтому ваши действия также могут быть довольно ограниченными (они были бы более сложными, если бы у вас были произвольные переменные или константы).
Выражение ((x * 2.0) + x) -1 будет выполнено серией действий
pushx
mul2
addx
sub1
Наверное, трудно стать намного лучше, чем эта.
Вместо этого можно было бы определить действия для реализации оценщика выражений, ориентированного на регистры, по модели многоканального ЦП; это позволило бы выполнить еще быстрее (я бы предположил, что в два раза, но только если выражение стало действительно сложным).
То, что вам нужно, это действия, которые охватывают самые общие вычисления, которые вам нужно сделать (так что вы всегда можете выбрать допустимую последовательность действий, независимо от вашего исходного выражения) и действия, которые часто происходят в выражениях, с которыми вы сталкиваетесь (add1 довольно типичен для машинный код, не знаю, на что похожа ваша статистика, и ваше замечание о том, что вы занимаетесь генетическим программированием, предполагает, что вы не знаете, какой будет статистика, но вы можете как-то измерить ее или сделать обоснованное предположение).
Ваш внутренний цикл для оценки будет выглядеть так (небрежный синтаксис здесь):
float stack[max_depth];
stack_depth=0;
for (i=1;i<expression_length;i++)
{
switch (code[i]) // one case for each opcode in the enum
{
case pushx: stack[stack_depth++]=x;
break;
case push1: stack[stack_depth++]=1;
break;
...
case add: stack[stack_depth-1]+=stack[stack_depth];
stack_depth--;
break;
...
case subx: stack[stack_depth]-=x;
break;
...
}
}
// stack[1] contains the answer here
В приведенном выше коде реализован очень быстрый «потоковый интерпретатор» для вычислителя выражений стека pushdown.
Теперь «все», что вам нужно сделать, это сгенерировать содержимое массива кода. Вы можете сделать это
используя исходное дерево выражений, выполняя обход исходного дерева рекурсивных выражений, но вместо того, чтобы выполнять оценку выражений, запишите действие, которое будет выполнять ваш текущий оценщик выражений, в массив кода и выполняя специальные действия в случае, когда вы их найдете (это составляет «оптимизация глазка»). Это классическая компиляция из деревьев, и вы можете узнать намного больше о том, как это сделать, практически в любой книге компиляторов.
Да, это все немало. Но затем вы решили запустить генетический алгоритм, который в вычислительном отношении довольно дорогой.