Mathematica: используя упрощение, чтобы сделать общее устранение и снижение прочности

Question

Так что в последнее время я играю, как сопоставление шаблона математики и переписывание и термин с термином может быть привлечено к хорошему использованию в оптимизации компилятора ... пытаясь высоко оптимизировать короткие блоки кода, которые являются внутренними частями петель. Два распространенных способа уменьшить объем работы, требуется для оценки выражения, заключается в определении выражений, которые происходят более одного раза и хранят результат, а затем используйте хранимую результат в последующих точках, чтобы сохранить работу. Другой подход - использовать более дешевые операции, где это возможно. Например, мое понимание состоит в том, что привлечение квадратных корней принимают больше тактов циклов, чем дополнения и мультипликации. Чтобы быть ясно, я заинтересован в стоимости с точки зрения операций с плавающей запятой, которые оценивают выражение, не так долго требуют математики для его оценки.

Моя первая мысль заключалась в том, что я решил проблему, развивающую с помощью Mathematica упрощать функция. Можно указать функцию сложности, которая сравнивает относительную простоту двух выражений. Я собирался создать один с использованием весов для соответствующих арифметических операций и добавить к этому LeafCount для выражения для учета операций назначения, которые необходимы. Это касается сокращения стороны силы, но это устранение общих под воздействий, которые меня побудили.

Я думал о добавлении общего выведения под воздействия на возможные функции преобразования, которые упрощают использование. Но для большого выражения может быть заменено много возможных под воздействий, которые могут быть заменены, и нельзя узнать, что они, пока вы не увидите выражение. Я написал функцию, которая дает возможные замены, но кажется, что функция трансформации, которую вы указываете, необходимо просто вернуть одно возможное преобразование, по крайней мере, из примеров в документации. Любые мысли о том, как можно обойти это ограничение? У кого-нибудь есть лучшая идея о том, как упростить использование функций трансформации, которые могут подсказать на направлении вперед?

Я представляю, что за кулисами, которые упрощают, выполняет некоторое динамическое программирование, стараясь разными упрощениями на разных частях выражений и возвращение одной с самым низким показателем сложности. Буду лучше пытаться сделать это динамическое программирование самостоятельно, используя общие алгебраические упрощения, такие как фактор и собирают?

Редактировать: я добавил код, который генерирует возможные подписи для удаления

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

Answer 1

Чтобы определить повторяющиеся подключения, вы можете использовать что-то вроде этого

(*helper functions to add Dictionary-like functionality*)

index[downvalue_, 
   dict_] := (downvalue[[1]] /. HoldPattern[dict[x_]] -> x) // 
   ReleaseHold;
value[downvalue_] := downvalue[[-1]];
indices[dict_] := 
  Map[#[[1]] /. {HoldPattern[dict[x_]] -> x} &, DownValues[dict]] // 
   ReleaseHold;
values[dict_] := Map[#[[-1]] &, DownValues[dict]];
items[dict_] := Map[{index[#, dict], value[#]} &, DownValues[dict]];
indexQ[dict_, index_] := 
  If[MatchQ[dict[index], HoldPattern[dict[index]]], False, True];


(*count number of times each sub-expressions occurs *)
expr = Cos[x + Cos[Cos[x] + Sin[x]]] + Cos[Cos[x] + Sin[x]];
Map[(counts[#] = If[indexQ[counts, #], counts[#] + 1, 1]; #) &, expr, 
  Infinity];
items[counts] // Column

Answer 2

Здесь также есть некоторые процедуры, которые здесь реализованы здесь: http://stoney.sb.org/wordpress/2009/06/Converting-symbolic-mathematica-expressions-to-c-code/

Я упаковал его в файл * .m и исправил ошибку (если выражение не имеет повторных подключаемых, то он умирает), и я пытаюсь найти контактную информацию автора, чтобы увидеть, смогу ли я загрузить свой модифицированный код в Pastrbin или везде Отказ

Редактировать: Я получил разрешение от автора для его загрузки и вставил его здесь: http://pastebin.com/fjyir0b3.