Так что в последнее время я размышлял над тем, как подход Mathematica для сопоставления с образцом и переписывания терминов может найти хорошее применение при оптимизации компилятора ... пытаясь высоко оптимизировать короткие блоки кода, которые являются внутренними частями циклов. Два распространенных способа уменьшить объем работы, необходимой для оценки выражения, - это определить подвыражения, которые встречаются более одного раза, и сохранить результат, а затем использовать сохраненный результат в последующих точках для сохранения работы. Другой подход заключается в использовании более дешевых операций, где это возможно. Например, я понимаю, что получение квадратных корней занимает больше тактов, чем сложение и умножение. Чтобы быть ясным, меня интересует стоимость в терминах операций с плавающей запятой, которые потребуются для вычисления выражения, а не то, сколько времени требуется Mathematica для его оценки.
Моя первая мысль была о том, что я буду решать проблему, возникающую при использовании функции Mathematica упрощение . Можно указать функцию сложности, которая сравнивает относительную простоту двух выражений. Я собирался создать один с использованием весов для соответствующих арифметических операций и добавить к этому LeafCount для выражения, чтобы учесть необходимые операции присваивания. Это касается стороны уменьшения силы, но это устраняет общие подвыражения, которые меня смутили.
Я думал добавить общее исключение подвыражений к возможным функциям преобразования, которые упрощают использование. Но для большого выражения может быть много возможных подвыражений, которые можно заменить, и будет невозможно узнать, что они из себя представляют, пока вы не увидите выражение. Я написал функцию, которая дает возможные замены, но похоже, что указанная вами функция преобразования должна просто возвращать одно возможное преобразование, по крайней мере, из примеров в документации. Любые мысли о том, как можно обойти это ограничение? Кто-нибудь имеет лучшее представление о том, как упростить использует функции преобразования, которые могут намекают на направление вперед?
Я полагаю, что за кулисами Simplify выполняет какое-то динамическое программирование, пробуя различные упрощения для разных частей выражений и возвращая ту, которая имеет наименьший показатель сложности. Буду ли я лучше заниматься этим динамическим программированием самостоятельно, используя общие алгебраические упрощения, такие как фактор и сбор?
РЕДАКТИРОВАТЬ: я добавил код, который генерирует возможные подвыражения для удаления
(*traverses entire expression tree storing each node*)
AllSubExpressions[x_, accum_] := Module[{result, i, len},
len = Length[x];
result = Append[accum, x];
If[LeafCount[x] > 1,
For[i = 1, i <= len, i++,
result = ToSubExpressions2[x[[i]], result];
];
];
Return[Sort[result, LeafCount[#1] > LeafCount[#2] &]]
]
CommonSubExpressions[statements_] := Module[{common, subexpressions},
subexpressions = AllSubExpressions[statements, {}];
(*get the unique set of sub expressions*)
common = DeleteDuplicates[subexpressions];
(*remove constants from the list*)
common = Select[common, LeafCount[#] > 1 &];
(*only keep subexpressions that occur more than once*)
common = Select[common, Count[subexpressions, #] > 1 &];
(*output the list of possible subexpressions to replace with the \
number of occurrences*)
Return[common];
]
Как только общее подвыражение выбрано из списка, возвращаемого CommonSubExpressions, функция, выполняющая замену, находится ниже.
eliminateCSE[statements_, expr_] := Module[{temp},
temp = Unique["r"];
Prepend[ReplaceAll[statements, expr -> temp], temp[expr]]
]
С риском, что этот вопрос станет длинным, я приведу небольшой пример кода. Я подумал, что приличным выражением для оптимизации будет классический метод Рунге-Кутты для решения дифференциальных уравнений.
Input:
nextY=statements[y + 1/6 h (f[t, n] + 2 f[0.5 h + t, y + 0.5 h f[t, n]] +
2 f[0.5 h + t, y + 0.5 h f[0.5 h + t, y + 0.5 h f[t, n]]] +
f[h + t,
y + h f[0.5 h + t, y + 0.5 h f[0.5 h + t, y + 0.5 h f[t, n]]]])];
possibleTransformations=CommonSubExpressions[nextY]
transformed=eliminateCSE[nextY, First[possibleTransformations]]
Output:
{f[0.5 h + t, y + 0.5 h f[0.5 h + t, y + 0.5 h f[t, n]]],
y + 0.5 h f[0.5 h + t, y + 0.5 h f[t, n]],
0.5 h f[0.5 h + t, y + 0.5 h f[t, n]],
f[0.5 h + t, y + 0.5 h f[t, n]], y + 0.5 h f[t, n], 0.5 h f[t, n],
0.5 h + t, f[t, n], 0.5 h}
statements[r1[f[0.5 h + t, y + 0.5 h f[0.5 h + t, y + 0.5 h f[t, n]]]],
y + 1/6 h (2 r1 + f[t, n] + 2 f[0.5 h + t, y + 0.5 h f[t, n]] +
f[h + t, h r1 + y])]
Наконец, код для оценки относительной стоимости различных выражений приведен ниже. Веса являются концептуальными на данный момент, так как это все еще область, которую я исследую.
Input:
cost[e_] :=
Total[MapThread[
Count[e, #1, Infinity, Heads -> True]*#2 &, {{Plus, Times, Sqrt,
f}, {1, 2, 5, 10}}]]
cost[transformed]
Output:
100