# Timing problem with ReplaceRepeated

I have the following data:

data =
{{{1931, 1, 1}, 7.78}, {{1931, 1, 2}, 5.}, {{1931, 1, 3}, "x"},
{{1931, 1, 4}, "x"}, {{1931, 1, 16}, 5.}, {{1931, 1, 17}, 3.89},
{{1931, 1, 18}, "x"}, {{1931, 1, 20}, 2.22}};


I want to replace the "x"-values with the last preceding number:

data //. {a___, b : {_, c_}, {d_, "x"}, e___} :> {a, b, {d, c}, e}


gives the expected result:

{{{1931, 1, 1}, 7.78}, {{1931, 1, 2}, 5.}, {{1931, 1, 3}, 5.},
{{1931,1, 4}, 5.}, {{1931, 1, 16}, 5.}, {{1931, 1, 17}, 3.89},
{{1931, 1, 18}, 3.89}, {{1931, 1, 20}, 2.22}}


but becomes very slow as elements grow: $4.6$ seconds with $10000$ elements and seemingly forever with $25000$. My lists are long ($25000+$ elements) but have very few ($50$ - $100$) "x"-values.

I have no idea how a fast functional solution could look like.

• g[v : {s_List, n_?NumericQ}] := (temp = n; v); g[v : {s_List, "x"}] := {s, temp}; g /@ data – Dr. belisarius Oct 29 '15 at 20:36
• Thanks @ belisarius - your solution is right, short and fast. Would you post it as an answer ? – eldo Oct 29 '15 at 20:50

Your data looks like an EventSeries to me. Therefore let's treat it like one.

es = EventSeries[data /. "x" -> Missing[],
MissingDataMethod -> {"Interpolation", InterpolationOrder -> 0}]

es["Path"]

{{978220800, 7.78}, {978307200, 5.}, {978393600, 5.}, {978480000, 5.}, {979516800, 5.},
{979603200, 3.89}, {979689600, 3.89}, {979862400, 2.22}}


Or

es["DatePath"] // Normal

{{{1931, 1, 1, 0, 0, 0.}, 7.78}, {{1931, 1, 2, 0, 0, 0.}, 5.},
{{1931, 1, 3, 0, 0, 0.}, 5.}, {{1931, 1, 4, 0, 0, 0.}, 5.},
{{1931, 1, 16, 0, 0, 0.}, 5.}, {{1931, 1, 17, 0, 0, 0.}, 3.89},
{{1931, 1, 18, 0, 0, 0.}, 3.89}, {{1931, 1, 20, 0, 0, 0.}, 2.22}}


AbsoluteTimings for a list with 15492 entries, 37 % containing "x":

• ReplaceRepeated: 7326.01
• Map data: 0.0268449
• Map data[[All, 2]]: 0.0175813
• Scan: 0.0581277
• FoldList: 0.123955
• EventSeries: 0.727509

Creating the EventSeries object costs some extra time, but it is potentially advantageous for the subsequent processing.

• Yes indeed, dates with (missing) values. A very interesting solution with some options to play with. Thank you :) – eldo Oct 29 '15 at 22:19

Without patterns:

g[v : {s_List, n_?NumericQ}] := (temp = n; v);
g[v : {s_List, "x"}] := {s, temp};

g /@ data


{{{1931, 1, 1}, 7.78}, {{1931, 1, 2}, 5.}, {{1931, 1, 3}, 5.}, {{1931, 1, 4}, 5.}, {{1931, 1, 16}, 5.}, {{1931, 1, 17}, 3.89}, {{1931, 1, 18}, 3.89}, {{1931, 1, 20}, 2.22}}

Or even faster:

data[[All, 2]] = Block[{temp, g},
g[n_?NumericQ] := temp = n;
g["x"] := temp; g /@ data[[All, 2]]];

• It's even faster, if you only Map over the second column: data[[All, 2]] = Block[{temp, g}, g[n_?NumericQ] := temp = n; g["x"] := temp; g /@ data[[All, 2]]]; – Karsten 7. Oct 30 '15 at 17:49
• @Karsten7. Thanks! I made that yesterday but haven't have the time to check the performance. Feel free to edit the answer! – Dr. belisarius Oct 30 '15 at 17:57
• +1. Great Answer, Is there any reason you choose Block not Module? – Basheer Algohi Oct 30 '15 at 19:44
• @Algohi In general using Block is faster, that's the only reason. – Karsten 7. Oct 30 '15 at 20:12

This should do what you want:

Rest @ FoldList[
Replace[{##}, {{{_, c_}, {d_, "x"}} :> {d, c}, {_, arg_} :> arg}]&,
{},
data
]


while being functional and hopefully fast enough.

• Thanks, much to learn for me from your answer :) – eldo Oct 29 '15 at 22:23

Using Position and Scan a fast solution is possible.

Proof of concept

First a short synthetic data set for proof of concept.

dataN = {{1931, RandomInteger[{1, 12}], RandomInteger[{1, 30}]},
RandomReal[{1., 10.}]} & /@ Range[2];

dataX = {{1931, RandomInteger[{1, 12}], RandomInteger[{1, 30}]},
"x"} & /@ Range[2];

data = Riffle[dataN, dataX]

{{{1931, 12, 13}, 3.89908}, {{1931, 3, 28}, "x"},
{{1931, 8, 6}, 2.41899}, {{1931, 7, 2}, "x"}}


Very simply we get the position of elements that contain the string "x" and then replace them, using Scan, with the numerical value preceding it in the same position.

Since we start at the beginning repeated elements with "x" will have the same preceding value.

Scan[
(data[[Sequence @@ #]] = data[[#[[1]] - 1, #[[2]]]]) &,
Position[data, "x"]
]


produces

{{{1931, 5, 1}, 4.47596}, {{1931, 1, 15}, 4.47596},
{{1931, 5, 13}, 8.81877}, {{1931, 5, 6}, 8.81877}}


Timing

Now we make a large (25000) length dataset.

dataN = {{1931, RandomInteger[{1, 12}], RandomInteger[{1, 30}]},
RandomReal[{1., 10.}]} & /@ Range[12500];

dataX = {{1931, RandomInteger[{1, 12}], RandomInteger[{1, 30}]},
"x"} & /@ Range[12500];

data = Riffle[dataN, dataX];


Run and time the Scan and check the results.

Scan[
(data[[Sequence @@ #]] = data[[#[[1]] - 1, #[[2]]]]) &,
Position[data, "x"]
] // Timing

{0.171601, Null}


With this test data every other component had an "x". Check the first four:

data[[1 ;; 4]]

{{{1931, 8, 27}, 9.75179}, {{1931, 2, 17}, 9.75179},
{{1931, 8, 5}, 1.3279}, {{1931, 6, 8}, 1.3279}}


Leonid's approach took 0.218 seconds.

Belisarius's approach was the fastest: 0.0468 seconds.

• You don't need the Scan[ ] part. Like this(data[[#, 2]] = data[[# - 1, 2]]) & /@ (Position[data, "x"][[All, 1]]) – Dr. belisarius Oct 29 '15 at 23:45
• @belisariusisforth Scan works slightly faster on my system than Map. My perception is that Scan should be used when you are only producing side effects. Reformulating (data[[Sequence @@ #]] = data[[#[[1]] - 1, #[[2]]]]) &, Position[data, "x"] to (data[[#, 2]] = data[[# - 1, 2]]) &, Position[data, "x"][[All, 1]]]` provides a speed up. – Jack LaVigne Oct 30 '15 at 13:53
• Seems you're right :) – Dr. belisarius Oct 30 '15 at 14:00