# Speed up replace all

I have large list of rules, I would like to use list/.rule, but assume that rule is a set of rules rule 1, rule2 rule...I want the Replace All to find first match of rule 1 then apply rule,and so go over to look for match of rule two. This would speed up the process in a very large dataset.

I want the first rule on only the first match found, then continue with the next rule from start of the list, if there are any cases of no match go to to next rule. Result would be the list but with applied rules where matches of patterns have been found.If a rule changes a value, and that new value is matched by a later rule, then leave it untouched.(Do not apply rule on al ready changed value)

Example:

list={{"02jan2001", "A", 47.98, ""}, {"03jan2001", "A", 52.9312,
""}, {"04jan2001", "A", 54.9353, ""}, {"05jan2001", "A", 51.9292,
""}, {"08jan2001", "A", 50.2198, ""}, {"09jan2001", "A", 49.9841,
""}}

Rules= {{"02jan2001", "A", q$___} -> 0.815473, {"03jan2001", "A", q$___} ->
0.840296, {"04jan2001", "A", q\$___} -> 0.833659}


Wanted output {0.815473, 0.840296, 0.833659, {"05jan2001", "A", 51.9292, ""}, {"08jan2001", "A", 50.2198, ""}, {"09jan2001", "A", 49.9841, ""}}

-
Your question is ambiguous. Do you mean you want a replacement by the first rule on only the first match found, then continue with the next rule from that point in the target, etc? What if the is no match? Please provide a minimal example of input and output... –  ciao May 12 '14 at 22:12
Without more detail all I'd suggest is that you read the docs on ReplaceRepeated and ReplaceList. Also for speeding up replacements generally see Dispatch and note that if you know the structure of your list then try replacing to a specific levelspec rather than all levels. –  Mike Honeychurch May 12 '14 at 22:13
Perhaps a concrete example of the "dataset" and typical rules you expect with desired result could be added to OP: all the machinations in our various answers re: handling heads of expressions, etc. are for naught if you're just wanting simple numeric/symbolic substitution rules with the "first found" restriction... –  ciao May 13 '14 at 6:50
That is correct Mr.Wizard –  ALEXANDER May 13 '14 at 9:49
@ALEXANDER The example you appended doesn't require the behavior that I indicated in a comment above; it doesn't require avoiding replacement of already-modified expressions. Is this behavior important or not? Further, your rules appear (in Rules) in the same order as they are matched within your list; is this always the case? –  Mr.Wizard May 13 '14 at 15:15

Here is another alternative in which I assume that once a rule is applied to a list you search further along the list for matches to apply the next rule ...and so on. As with other answers the ambiguity of the OPs question probably needs to be cleared up. This is a line by line systematic approach:

 findPositions[list_][position_, rule_] :=
Module[{pos},
pos = Flatten[Position[list, rule[[1]], {1}]];
pos = Cases[pos, x_ /; x > position, {1}, 1];
If[pos =!= {}, First@pos, position]
]


then:

rules[[All, 1]] = Rest@FoldList[findPositions[list], 0, rules];
Scan[(list[[#[[1]]]] = #[[2]]) &, rules]


For example:

list = {1, 2, 3};
rules = {_Integer -> 4, _Integer -> 5, _Integer -> 6};

rules[[All, 1]] = Rest@FoldList[findPositions[list], 0, rules];
Scan[(list[[#[[1]]]] = #[[2]]) &, rules]
list
(* {4, 5, 6} *)


and

rules = {1 -> 9, 2 -> 3, 3 -> 4, 9 -> 8};
list = {5, 1, 3, 2, 2, 2, 0, 4, 0, 3, 2, 4, 1, 9, 1, 5, 2, 5, 4, 3};

rules[[All, 1]] = Rest@FoldList[findPositions[list], 0, rules];
Scan[(list[[#[[1]]]] = #[[2]]) &, rules]
list
(* {5, 9, 3, 3, 2, 2, 0, 4, 0, 4, 2, 4, 1, 8, 1, 5, 2, 5, 4, 3} *)

-
+1 for addressing my interpretation, but can you make this work for all levels? –  Mr.Wizard May 13 '14 at 0:27
@Mr.Wizard short answer would be yes but obviously requires a re-jig of the code to accomplish that. Long answer is that I have already spent way too long on this and won't do anymore until the OP offers some clarity. –  Mike Honeychurch May 13 '14 at 1:16

Following my own interpretation of the question here is one approach. It seems quite clumsy but I can't think of a better way at the moment. Perhaps I can refine it later.

myRA[expr_, rules_List] :=
Module[{next, f, i = 1, n = Length@rules},
next[] /; i >  n := (f = Identity);
next[] /; i <= n := (
Clear[f];
(f[#] := (next[]; #2)) & @@ rules[[i++]];
f[other_] := f /@ Operate[f, other]
);
next[];
f @ expr
]


Test:

myRA[foo[1, {2, 3, 0}], {_Integer -> 4, _Integer -> 5, _Integer -> 6}]

foo[4, {5, 6, 0}]


This relies on evaluation within the expression, and won't work on e.g. Hold, which means that is it not equivalent to ReplaceAll. Nevertheless it may have value.

-
Note: compared to rasher's repper this is orders of magnitude slower. Back to the drawing board. –  Mr.Wizard May 13 '14 at 0:46
+1 for some subtle cleverness there. Waiting on OP clarification before pursuing other ideas... –  ciao May 13 '14 at 7:56
It does work with integer pattern, but I am not able to get it to work with my type of pattern, still it is something with your code that looks very interesting. I am not able to grasp what is going one, would you be able to explain? –  ALEXANDER May 13 '14 at 14:42
@ALEXANDER As noted above this scales very poorly so I don't recommend using it. However, in answer to your question it works by continually redefining a function f to act as the current rule, while mapping this function across all levels of the input expression. Each time a match is found next[] is called which redefines f to behave like the next rule in the sequence. After writing this I realized that depending on your meaning it may not be correct as it does not start over from the beginning, but rather the last point of evaluation. I shall look at the example that you added. –  Mr.Wizard May 13 '14 at 15:04

Here's an example of a way to do this.

list = RandomInteger[5, 20]

(* {5, 1, 3, 2, 2, 2, 0, 4, 0, 3, 2, 4, 1, 1, 1, 5, 2, 5, 4, 3} *)

rules = {1 -> 2, 2 -> 3, 3 -> 4, 9 -> 8};

ReplacePart[list, Cases[Thread[Position[list, #, 1, 1] & /@ rules[[All, 1]] ->
rules[[All, 2]]], ({{a_}} -> b_) :> a -> b]]

(* {5, 2, 4, 3, 2, 2, 0, 4, 0, 3, 2, 4, 1, 1, 1, 5, 2, 5, 4, 3} *)


This works by finding the position of the first occurrence (if it exists) for each left-hand side of the rules, and re-writing the rules to use that position in place of the value.

Pretty snappy, if you need it faster that can be done at the cost of more convoluted code.

Update: Based on Mr.Wizard's comments, perhaps this is more in line with desired results:

repper[list_, rules_, depth_: 1] :=
Module[{rg = GatherBy[rules, First], m1, rp},
m1 = Map[Position[list, #[[1]], depth, #[[2]]] &, Tally[rules[[All, 1]]]];
rp = Flatten@MapIndexed[# -> rg[[Sequence @@ #2]][[2]] &, m1, {2}];
ReplacePart[list, rp]]

list = {1.25, 1, 2, 3, 5.5, 20, 30};

rules = {_Integer -> 4, _Integer -> 5, _Integer -> 6, _Real -> 2.5, _Integer -> 66,
3 -> 999};

repper[list, rules]

(* {2.5, 4, 5, 6, 5.5, 66, 30} *)

repper[foo[1, {2, 3, 0, 1/3}],
{_Integer -> 4, _Integer -> 5, _Integer -> 6, foo -> bar, _Rational -> 2.5},
Infinity]

(* bar[4, {5, 6, 0, 2.5}] *)

-
Nice idea. +1 Now let me see if I can find another way... –  Mr.Wizard May 12 '14 at 22:46
@Mr.Wizard: Thanks! I think the ordering trick would be the fastest, at the cost of much more code... –  ciao May 12 '14 at 22:47
Actually this doesn't do what I think the OP wants, but it's a valid interpretation of the original question so my vote stands. Nevertheless I am guessing that list = {1, 2, 3}; rules = {_Integer -> 4, _Integer -> 5, _Integer -> 6}; should result in {4, 5, 6} for output. Does that make sense? (This is easy enough at a single level, but seems difficult for full /. behavior.) –  Mr.Wizard May 12 '14 at 22:51
@Mr.Wizard: Yes, I agree with your assessment, perhaps further clarification by OP warranted. –  ciao May 12 '14 at 23:02
Would you please give a version of repper that operates at all levels? (Including heads.) –  Mr.Wizard May 13 '14 at 0:31

If a replacement is only to be made once for each rule then I think you can re-think the problem and do it this way:

rules = {1 -> 9, 2 -> 3, 3 -> 4, 9 -> 8};
list = {5, 1, 3, 2, 2, 2, 0, 4, 0, 3, 2, 4, 1, 9, 1, 5, 2, 5, 4, 3};
Scan[(list[[Flatten@Position[list, #[[1]], {1}, 1]]] = #[[2]]) &, rules]
list

(* {5, 4, 3, 2, 2, 2, 0, 4, 0, 3, 2, 4, 1, 8, 1, 5, 2, 5, 4, 3} *)


As another check with rules = {1 -> 9, 2 -> 3, 3 -> 4, 9 -> 8} I get

   (* {5, 8, 4, 3, 2, 2, 0, 4, 0, 3, 2, 4, 1, 9, 1, 5, 2, 5, 4, 3} *)


so the second element in list is initially changed from 1 to 9 and then subsequently from 9 to 8. I believe that this transformation is what you are seeking.

As an aside, for applying one rule at a time to an entire list:

Fold[Replace[#1 , #2, {1}] &, list, rules]
`
-