ReplaceAll[expr, {patt1:>rhs1, patt2:>rhs2, …}]
works by looking for and making all possible replacements of subexpressions in expr
with rhs1
,rhs2
… that match patt1
,patt2
…. Then, the main evaluator evaluates all the rhs1
, rhs2
… appearing in the modified expr
.
This scheme of replacement works well especially if rhs1
,rhs2
… cause side effects (like i++
). However, if rhs1
,rhs2
… are computationally intensive functions without side effects, and expr
is a large expression containing many instances matching patt1
,patt2
…, the main evaluator ends up evaluating the big functions rhs1
,rhs2
… many times.
The canonical solution to this problem in Mathematica is memoization where rhs
is supposed to be defined like rhs := rhs = ...
so that even though many instances of rhs1
,rhs2
… appear in the modified expr
, the main evaluator will recognize precomputed values based on an ever growing list of DownValues
.
However, I believe another possible solution to this problem, especially suitable if rhs1
,rhs2
… are not recursive functions, is to follow a different scheme: (1) scout out and note the positions of subexpressions in expr
uniquely matching the patt1
, patt2
, (2) evaluate in place the corresponding rhs1
,rhs2
… exactly once for each unique match, and finally (3) substitute all results into expr
at their noted positions. I believe that apart from saving some memory, this scheme has the advantage of (a) not rebuilding a hash table of memoized DownValues
, (b) not looking for a possible match in the hash table, and (c) not scanning the entire expr
each time rhs
is evaluated in the modified expr
.
So my question is: is there a built-in replacement function that implements the replacement scheme described above? I would find it useful. Otherwise, is there a method to write a top-level implementation of the scheme?
Here is a first-attempt at an implementation:
ClearAll[ReplaceAllOnce];
ReplaceAllOnce[expr_, rules_] :=
ReplacePart[expr, (Position[expr, #, {0, Infinity}, Heads -> True] -> (Replace[#, rules])) & /@
DeleteDuplicates[Cases[expr, Alternatives @@ rules[[All, 1]], {0, Infinity}, Heads -> True]]]
However, I don't like it much because it has to traverse through expr
multiple times.
As requested, here is an example. Suppose I want to apply to this expression,
expr := (a parity[1] + b parity[2] + c parity[3])*
(d parity[1] + e parity[2] + f parity[3]);
The following set of rules
rules = {parity[x_Integer?OddQ] :> (Pause[1]; 1),
parity[x_Integer?EvenQ] :> (Pause[1]; 2)};
A straightforward ReplaceAll
takes 6 seconds (because there are 6 instances of parity
).
ReplaceAll[expr, rules] // AbsoluteTiming
(* {6.00317, (a + 2 b + c) (d + 2 e + f)} *)
Then using the search-and-replace once method using ReplaceAllOnce
proposed above takes only 3 seconds, and uses 5680 bytes of memory according to MemoryInUse[]
:
ReplaceAllOnce[expr, rules] // AbsoluteTiming
(* {3.00413, (a + 2 b + c) (d + 2 e + f)} *)
The timing is similar to using memoization, but this uses 12800 bytes (larger, to store the memoized cases):
Clear[parity];
parity[x_Integer?OddQ] := parity[x] = (Pause[1]; 1);
parity[x_Integer?EvenQ] := parity[x] = (Pause[1]; 2);
expr // AbsoluteTiming
(* {3.00486, (a + 2 b + c) (d + 2 e + f)} *)