Timing problem with ReplaceRepeated

Question

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.

Answer 1

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.

Answer 2

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]]];

Answer 3

This should do what you want:

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

while being functional and hopefully fast enough.

Answer 4

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.