Mathematica:utilizzando semplificare fare comune sotto-espressione di eliminazione e riduzione in forza

Question

Così ultimamente sto giocando intorno con come Mathematica del pattern matching e termine di riscrittura potrebbe essere messo a buon uso in ottimizzazioni del compilatore...cercando di altamente ottimizzare brevi blocchi di codice che le parti interne del loop.Due modi per ridurre la quantità di lavoro necessario per valutare un'espressione per identificare sub-espressioni che si verificano più di una volta e di salvare il risultato e quindi utilizzare il risultato archiviato presso i punti per salvare il lavoro.Un altro approccio è quello di utilizzare meno operazioni, ove possibile.Per esempio, la mia comprensione è che l'assunzione di radici quadrate richiedere più cicli di clock di addizioni e moltiplicazioni.Per essere chiari, non mi interessa il costo, in termini di operazioni in virgola mobile che la valutazione dell'espressione vorresti prendere, non quanto tempo ci vuole Mathematica per la valutazione.

Il mio primo pensiero è stato che vorrei affrontare il problema in via di sviluppo utilizzando Mathematica s semplificare funzione.È possibile specificare una complessità funzione che confronta la relativa semplicità delle due espressioni.Stavo per creare uno utilizzando pesi per le relative operazioni aritmetiche e aggiungi la LeafCount per l'espressione di account per l'assegnazione di operazioni che sono necessarie.Che indirizzi la riduzione della forza laterale, ma è l'eliminazione di sottoespressioni comuni che mi ha scattato up.

Stavo pensando di aggiungere l'eliminazione delle sottoespressioni comuni per la possibile trasformazione di funzioni che semplificano la utilizza.Ma per una grande espressione ci potrebbero essere molte possibili sottoespressioni che potrebbe essere sostituito e non sarà possibile sapere che cosa si sono fino a vedere l'espressione.Ho scritto una funzione che dà la sostituzione possibile, ma sembra che la funzione di trasformazione si specifica deve restituire solo 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 semplificare utilizza le funzioni di trasformazione che potrebbe alludere a una direzione di marcia?

Immagino che dietro le quinte che Semplificano sta facendo di programmazione dinamica provando diverse semplificazioni su diverse parti delle espressioni e la restituzione di quello con la più bassa complessità punteggio.Sarebbe meglio cercare di fare questa programmazione dinamica sul mio proprio uso comune algebrica semplificazioni come fattore di raccogliere?

EDIT:Ho aggiunto il codice che genera eventuali sub-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];
  ]

Una volta che un comune sotto-espressione viene scelto dalla lista restituita da CommonSubExpressions la funzione che esegue la sostituzione qui di seguito.

eliminateCSE[statements_, expr_] := Module[{temp},
temp = Unique["r"];
Prepend[ReplaceAll[statements, expr -> temp], temp[expr]]
]

Il rischio di questa domanda ormai, ho messo un po ' di codice di esempio fino.Ho pensato che un decente espressione per cercare di ottimizzare sarebbe la classica Runge-Kutta metodo per la soluzione di 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 di giudicare il costo relativo delle diverse espressioni è al di sotto.I pesi sono concettuale, a questo punto, che è ancora una zona io sono alla ricerca.

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

Per identificare la ripetizione di espressioni, si potrebbe usare qualcosa come questo

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

Ci sono anche alcune routine qui svolto da questo autore: http://stoney.sb.org/wordpress/2009/06/converting-symbolic-mathematica-expressions-to-c-code/

Ho condensato in un *.M file e hanno risolto un bug (se l'espressione non ha ripetuto sottoespressioni l'muore), e sto cercando di trovare l'autore le informazioni di contatto per vedere se riesco a caricare il suo codice modificato per pastebin o dovunque.

EDIT:Ho ricevuto il permesso da parte dell'autore di caricare e incollato qui: http://pastebin.com/fjYiR0B3