I have a list of the form data={{t1,x1}, {t2,x2},...} and a list newt = {nt1,nt2,...} and I want to expand data to these new times to become {{nt1,x(1)},{nt2,x(2)},{nt3,x(3)},...} where x(i) is equal to the xi of whichever data point is preceding nti.

I assume that t1<=t2<=t3<=.., nt1<=nt2<=... and the old times is a subset of the new ones.

I did this the following way, but it is far too slow:

PadDataList[l_, grid_] :=
   {lind = 1, len = Length@l},
      If[# > l[[lind, 1]] && lind < len, lind++];
      {#, l[[lind, 2]]}
      ) &,
data = Sort[RandomReal[1, {50000, 2}], First@#1 < First@#2 &];
newgrid = Union@Join[data[[All, 1]], RandomReal[1, {50000}]];
AbsoluteTiming[PadDataList[data, newgrid];]
(* 0.4 seconds *)

Is there a cleverer and more efficient way to do this?

I am using this together with another function that takes multiple lists like above and creates a new list with elements f[nti,x(i),y(i),...]

Excuse the abuse of (i) syntax

  • $\begingroup$ I haven't looked at your example that carefully, but are you trying to do zero-order interpolation? If that's the case, you might take a look at Interpolation. It has an option called InterpolationOrder which you could set to zero. $\endgroup$ – Aky Jun 5 '13 at 2:46

I'm not sure whether your implementation is consistent with your explanation. You wrote:

where x(i) is equal to the xi of whichever data point is preceding nti

I interpret this in the following way: when we have this simple example

data = {{1, x1}, {2, x2}, {4, x3}};
newgrid = {1, 2, 3, 4};

then nti=3 clearly should get the value x2 because this point is the preceding one when we insert the new time point. Your function gives

{{1, x1}, {2, x2}, {3, x3}, {4, x3}}

which I think is not what you meant, but maybe this is only a detail. Nevertheless, my implementation will return x2 in this place.

Regarding your question whether there is a cleverer and more efficient way to do this I have to admit that my implementation beats your function only by about .02 seconds, but I wanted to use highlevel code only this time. Therefore, you better look at this as an alternate approach:

PadDataList[data_, grid_] := With[
  {rules = Dispatch[Rule[#1, {##}] & @@@ data]},
  FoldList[If[NumericQ[#2], {#2, Last[#1]}, #2] &, First[data], Rest[grid] /. rules]

This function works as follows: It first creates a fast set of rules from your data so that I have a list {t1->{t1,x1}, t2->{t2,x2}, ...}. When I apply this rule to your new grid, I get a mixed list. Times that were available are replaced to their complete {tn,xn} pair, while new times stay untouched.

Now I go through this list with FoldList and if I meet a time only (NumericQ), I use this time value combined with the x of the last pair. You may now ask how I not this last value: This is the good thing with Fold, because the last result is always given as first argument and we can just use it.

  • $\begingroup$ Thanks for noticing the bug about preceeding. I've underestimated Dispatch I expected rule based approach to be slower. $\endgroup$ – ssch Jun 5 '13 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.