Quindi ultimamente mi sono divertito a capire come l'abbinamento e la riscrittura dei termini di Mathematica potrebbero essere utilizzati con ottimizzazioni del compilatore ... cercando di ottimizzare in modo ottimale blocchi di codice che sono le parti interne dei loop. Due modi comuni per ridurre la quantità di lavoro necessaria per valutare un'espressione è identificare le sotto-espressioni che si verificano più di una volta e memorizzare il risultato e quindi utilizzare il risultato memorizzato nei punti successivi per salvare il lavoro. Un altro approccio è quello di utilizzare le operazioni più economiche, ove possibile. Per esempio, la mia comprensione è che prendere radici quadrate richiede più cicli di clock di aggiunte e moltiplicazioni. Per essere chiari, sono interessato al costo in termini di operazioni in virgola mobile che la valutazione dell'espressione richiederebbe, non a quanto tempo impiegherà Mathematica a valutarlo.Mathematica: usare la semplificazione per eliminare e ridurre le resistenze in comune
Il mio primo pensiero è stato che avrei affrontato il problema dello sviluppo utilizzando la funzione simplify di Mathematica. È possibile specificare una funzione di complessità che confronta la semplicità relativa di due espressioni. Stavo per crearne uno usando i pesi per le operazioni aritmetiche pertinenti e aggiungere a questo il LeafCount per l'espressione per tenere conto delle operazioni di assegnazione che sono richieste. Ciò riguarda la riduzione del lato della forza, ma è l'eliminazione delle sottoespressioni comuni che mi ha fatto inciampare.
Stavo pensando di aggiungere l'eliminazione di sottoespressione comune alle possibili funzioni di trasformazione che semplificano gli usi. Ma per una grande espressione potrebbero esserci molte possibili sottoespressioni che potrebbero essere sostituite e non sarà possibile sapere cosa sono finché non vedrete l'espressione. Ho scritto una funzione che fornisce le possibili sostituzioni, ma sembra che la funzione di trasformazione specificata debba solo restituire una singola trasformazione possibile, almeno dagli esempi nella documentazione. Qualche idea su come si potrebbe aggirare questa limitazione? Qualcuno ha un'idea migliore di come la semplificazione usi le funzioni di trasformazione che potrebbero suggerire una direzione in avanti?
immagino che dietro le quinte che semplificano la sta facendo un po 'di programmazione dinamica provando diverse semplificazioni su diverse parti delle espressioni e tornando quello con il più basso punteggio di complessità. Farei meglio a provare a fare questa programmazione dinamica da solo usando le semplificazioni algebriche comuni come factor e collect?
EDIT: ho aggiunto il codice che genera possibili sotto-espressioni per rimuovere
(*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];
]
volta che un comune sottoespressione viene scelto dall'elenco restituito dal CommonSubExpressions la funzione che fa la sostituzione è inferiore.
eliminateCSE[statements_, expr_] := Module[{temp},
temp = Unique["r"];
Prepend[ReplaceAll[statements, expr -> temp], temp[expr]]
]
A rischio che questa domanda si allunghi, inserirò un piccolo esempio di codice. Ho pensato che un'espressione decente per cercare di ottimizzare sarebbe il classico metodo Runge-Kutta per risolvere equazioni differenziali.
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])]
Infine, il codice per giudicare il costo relativo delle diverse espressioni è inferiore. I pesi sono concettuali a questo punto in quanto è ancora un'area che sto ricercando.
Input:
cost[e_] :=
Total[MapThread[
Count[e, #1, Infinity, Heads -> True]*#2 &, {{Plus, Times, Sqrt,
f}, {1, 2, 5, 10}}]]
cost[transformed]
Output:
100
Hi! Ti dispiace condividere la tua funzione * che fornisce le possibili sostituzioni *? –
Tnx! Ho trovato "Experimental'OptimizeExpression" ... che sembra rimuovere calcoli ripetuti. Non funziona ancora per me, comunque. –
BTW, Simplify è più simile alla ricerca euristica che tenta diverse regole di trasformazione per rendere l'espressione più breve. Il potere è nel conoscere molte relazioni funzionali speciali, ma spesso mi imbatto in espressioni con exp, +, -, /, * per le quali Simplify non riesce a trovare la forma più semplice, mentre alcune regole di riscrittura personalizzate a-> b fanno il lavoro –