# Expand list of {{t1,x1},…} with new set of t's

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_] :=
Module[
{lind = 1, len = Length@l},
MapIndexed[(
If[# > l[[lind, 1]] && lind < len, lind++];
{#, l[[lind, 2]]}
) &,
grid
]];
data = Sort[RandomReal[1, {50000, 2}], First@#1 < First@#2 &];
newgrid = Union@Join[data[[All, 1]], RandomReal[1, {50000}]];
(* 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

-
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. –  Aky Jun 5 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.

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