だから最近、私はMathematicaのパターンマッチングと項の書き換えがコンパイラの最適化にどのように役立つかをいじくり回しています...ループの内部であるコードの短いブロックを高度に最適化しようとしています。式の評価にかかる作業量を減らす2つの一般的な方法は、複数回発生する部分式を識別して結果を保存し、保存された結果を後続のポイントで使用して作業を節約することです。もう1つのアプローチは、可能な場合はより安価な操作を使用することです。たとえば、私の理解では、平方根を取ると、加算や乗算よりも多くのクロックサイクルが必要になります。明確にするために、私は式を評価するのにかかる時間ではなく、式を評価するのにかかる浮動小数点演算の観点からのコストに興味があります。
私の最初の考えは、Mathematicaの単純化関数を使用して開発する問題に取り組むことでした。2つの式の相対的な単純さを比較する複雑さ関数を指定することができます。関連する算術演算に重みを使用して作成し、これに、必要な割り当て演算を説明する式の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
