Últimamente he estado discutiendo cómo la coincidencia de patrones y la reescritura de términos de Mathematica podrían ser utilizadas en optimizaciones de compiladores ... tratando de optimizar al máximo bloques de código que son las partes internas de los bucles. Dos formas comunes de reducir la cantidad de trabajo que se necesita para evaluar una expresión es identificar las subexpresiones que ocurren más de una vez y almacenar el resultado y luego usar el resultado almacenado en los puntos posteriores para guardar el trabajo. Otro enfoque es usar operaciones más baratas cuando sea posible. Por ejemplo, entiendo que tomar raíces cuadradas requiere más ciclos de reloj que adiciones y multiplicaciones. Para ser claro, me interesa el costo en términos de operaciones de punto flotante que la evaluación tomaría, no cuánto tiempo le tomará a Mathematica evaluarlo.Mathematica: usando simplify para hacer eliminación de sub-expresiones comunes y reducción de fuerza
Mi primer pensamiento fue que abordaría el problema de desarrollo utilizando la función simplify de Mathematica. Es posible especificar una función de complejidad que compare la simplicidad relativa de dos expresiones. Iba a crear uno usando pesos para las operaciones aritméticas relevantes y agregarle a esto el conteo de hojas para que la expresión contabilice las operaciones de asignación que se requieren. Eso aborda la reducción en el lado de la fuerza, pero es la eliminación de las subexpresiones comunes lo que me ha hecho tropezar.
Estaba pensando en agregar la eliminación de subexpresiones común a las posibles funciones de transformación que simplifican los usos. Pero para una expresión grande podría haber muchas subexpresiones posibles que podrían reemplazarse y no será posible saber cuáles son hasta que vea la expresión. He escrito una función que da las posibles sustituciones, pero parece que la función de transformación que especifica necesita simplemente devolver una única transformación posible, al menos de los ejemplos en la documentación. ¿Alguna idea de cómo se puede superar esta limitación? ¿Alguien tiene una mejor idea de cómo la simplificación utiliza funciones de transformación que podrían indicar una dirección hacia adelante?
Imagino que detrás de escena Simplifica está realizando una programación dinámica probando diferentes simplificaciones en diferentes partes de las expresiones y devolviendo la que tiene el puntaje de complejidad más bajo. ¿Sería mejor tratar de hacer esta programación dinámica por mi cuenta usando simplificaciones algebraicas comunes como factor y collect?
EDIT: He añadido el código que genera posibles sub-expresiones para eliminar
(*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];
]
Una vez que un sub-expresión común se elige de la lista devuelta por CommonSubExpressions la función que hace la sustitución es a continuación.
eliminateCSE[statements_, expr_] := Module[{temp},
temp = Unique["r"];
Prepend[ReplaceAll[statements, expr -> temp], temp[expr]]
]
A riesgo de que esta pregunta sea larga, pondré un pequeño código de ejemplo. Pensé que una expresión decente para intentar optimizar sería el método clásico Runge-Kutta para resolver ecuaciones diferenciales.
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])]
Finalmente, a continuación se muestra el código para determinar el costo relativo de las diferentes expresiones. Las ponderaciones son conceptuales en este punto, ya que todavía es un área que estoy investigando.
Input:
cost[e_] :=
Total[MapThread[
Count[e, #1, Infinity, Heads -> True]*#2 &, {{Plus, Times, Sqrt,
f}, {1, 2, 5, 10}}]]
cost[transformed]
Output:
100
Hola! ¿Te importa compartir tu * función que da las posibles sustituciones *? –
Tnx! Encontré "Experimental'OptimizeExpression" ... que parece eliminar cálculos repetidos. Sin embargo, todavía no funciona para mí. –
BTW, Simplify es más parecido a la búsqueda heurística que intenta diferentes reglas de transformación para acortar la expresión. Su poder reside en conocer muchas relaciones funcionales especiales, pero a menudo encuentro expresiones con solo exp, +, -, /, * para las cuales Simplify no puede encontrar la forma más simple, mientras que algunas reglas de reescritura personalizadas a-> b hacen el trabajo –