So kürzlich habe ich herumspielen mit, wie Mathematica Mustererkennung und Begriff Neuschreiben in Compiler-Optimierungen verwendet werden kann ... versuchen, kurz zu optimieren Code-Blöcke, die die inneren Teile von Schleifen sind. Zwei gängige Methoden zur Verringerung des Aufwands für die Auswertung eines Ausdrucks bestehen darin, Unterausdrücke, die mehr als einmal vorkommen, zu identifizieren und das Ergebnis zu speichern und das gespeicherte Ergebnis anschließend zu verwenden, um Arbeit zu sparen. Ein anderer Ansatz besteht darin, wo immer möglich billigere Operationen zu verwenden. Zum Beispiel ist mein Verständnis, dass Quadratwurzeln nehmen mehr Taktzyklen als Additionen und Multiplikationen. Um es klar zu sagen, ich interessiere mich für die Kosten in Bezug auf Gleitkommaoperationen, die die Auswertung des Ausdrucks benötigen würde, und nicht, wie lange es dauert, bis Mathematica es bewertet.Mathematica: vereinfachen, um gemeinsame Sub-Ausdruck Eliminierung und Verringerung der Stärke
Mein erster Gedanke war, dass ich das Problem mit der Mathematica simplify Funktion angehen würde. Es ist möglich, eine Komplexitätsfunktion anzugeben, die die relative Einfachheit von zwei Ausdrücken vergleicht. Ich wollte eine mit Gewichten für die relevanten arithmetischen Operationen erstellen und dazu den LeafCount für den Ausdruck hinzufügen, um die erforderlichen Zuweisungsoperationen zu berücksichtigen. Das spricht für die Verringerung der Stärke Seite, aber es ist die Beseitigung der üblichen Teilausdrücke, die mich stolpern.
Ich habe darüber nachgedacht, den möglichen Transformationsfunktionen, die die Verwendung vereinfachen, eine gemeinsame Teilausdruckseliminierung hinzuzufügen. Aber für einen großen Ausdruck könnte es viele mögliche Teilausdrücke geben, die ersetzt werden könnten und es wird nicht möglich sein zu wissen, was sie sind, bis Sie den Ausdruck sehen. Ich habe eine Funktion geschrieben, die die möglichen Ersetzungen liefert, aber es scheint, als ob die Transformationsfunktion, die Sie angeben, nur eine einzige mögliche Transformation zurückgeben muss, zumindest aus den Beispielen in der Dokumentation. Irgendwelche Gedanken darüber, wie man diese Einschränkung umgehen könnte? Hat jemand eine bessere Vorstellung davon, wie einfach die Transformationsfunktionen sind, die auf eine Vorwärtsrichtung hinweisen könnten?
Ich stelle mir vor, dass Simplify hinter den Kulissen eine dynamische Programmierung vornimmt, die verschiedene Vereinfachungen an verschiedenen Teilen der Ausdrücke versucht und die mit dem niedrigsten Komplexitätswert zurückgibt. Wäre es für mich besser, wenn ich versuchen würde, diese dynamische Programmierung selbst vorzunehmen, indem ich übliche algebraische Vereinfachungen wie Faktor und Sammlung verwende?
EDIT: I hinzugefügt, um den Code, die mögliche Unterausdrücke erzeugt
(*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];
]
zu entfernen, sobald ein gemeinsamer Unterausdruck aus der Liste von CommonSubExpressions die Funktion, dass der Ersatz unten tut zurückgegeben gewählt ist.
Auf das Risiko, dass diese Frage lang wird, werde ich ein wenig Beispielcode aufstellen. Ich dachte, ein anständiger Ausdruck zu versuchen zu optimieren wäre die klassische Runge-Kutta Methode zur Lösung von Differentialgleichungen.
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])]
Schließlich ist der Code zur Beurteilung der relativen Kosten verschiedener Ausdrücke unten. Die Gewichte sind an diesem Punkt konzeptionell, da dies immer noch ein Bereich ist, den ich erforsche.
Input:
cost[e_] :=
Total[MapThread[
Count[e, #1, Infinity, Heads -> True]*#2 &, {{Plus, Times, Sqrt,
f}, {1, 2, 5, 10}}]]
cost[transformed]
Output:
100
Hallo! Haben Sie etwas dagegen, Ihre * Funktion zu teilen, die die möglichen Ersetzungen * gibt? –
Tnx! Ich fand "Experimental'OptimizeExpression" ... das scheint wiederholte Kalkungen zu entfernen. Funktioniert aber immer noch nicht für mich. –
BTW, Simplify ist eher heuristische Suche, die verschiedene Transformationsregeln versucht, um den Ausdruck kürzer zu machen. Es ist die Fähigkeit, viele spezielle funktionale Beziehungen zu kennen, aber ich stoße oft auf Ausdrücke mit exp, +, -, /, *, für die Simplify nicht die einfachste Form finden kann, während einige benutzerdefinierte Neuschreibregeln die Aufgabe übernehmen –