# Simpler way to fill date gaps with zero values

One basic problem when working with data like sales and dates is the case where you don't have sales in all days, so you have to fill it to take information as average or to make a plot. See this toy code as example:

dateList={{{2012, 1, 1}, 1}, {{2012, 1, 2}, 2}, {{2012, 1, 5}, 3}, {{2012, 1, 8}, 4}};


And I need to get this answer:

{{{2012,1,1},1},{{2012,1,2},3},{{2012,1,3},0},{{2012,1,4},0},{{2012,1,5},3},{{2012,1,6},0},{{2012,1,7},0},{{2012,1,8},4}}


where the missing dates are filled with value zero. They are date and sales values that I get from an SQL database. I created this functions, but I feel that it could be simplified:

getDateRange[dtIni_,dtFim_]:=NestWhileList[DatePlus[#,1]&,dtIni,(#!=dtFim)&]

fillDateGaps[list_]:=Module[{sortedOrgList,dateRange,listGaps},
sortedOrgList=SortBy[list[[All,1]],#[[1]]&];
dateRange=getDateRange[First@sortedOrgList,Last@sortedOrgList];
listGaps={#,0}&/@Complement[dateRange,sortedOrgList];
Union[list,listGaps]
]


With this function I can do calculations and things like this:

DateListPlot[fillDateGaps[dateList], Joined -> True]


How to make it simpler and faster?

• Instead of your getDateRange function, what would be wrong with daterange[firstd_List, lastd_List] := Array[DatePlus[firstd, # - 1] &, DateDifference[firstd, lastd] + 1]. I don't have time to test extensively but I'm sure that will be much faster than anything using NestWhileList. – Verbeia Oct 8 '12 at 22:00
• Hi Verbeia, I didn't get a big difference, both are slow. See. DateRange1[dtIni_List, dtFim_List] := NestWhileList[DatePlus[#, 1] &, dtIni, (# != dtFim) &]; DateRange2[firstd_List, lastd_List] := Array[DatePlus[firstd, # - 1] &, DateDifference[firstd, lastd] + 1] DateRange1[{2012, 1, 1}, {2012, 12, 31}]; // AbsoluteTiming DateRange2[{2012, 1, 1}, {2012, 12, 31}]; // AbsoluteTiming {0.2456, Null} {0.2477, Null} – Murta Oct 8 '12 at 23:40
• this new form is what make all the difference getDateRange[dtIni_,dtFim_]:=Part[DateList/@(Range[##,24*60^2]&@@AbsoluteTime/@{dtIni,dtFim}),All,{1,2,3}]; Tks Mr Wisard – Murta Oct 9 '12 at 2:22

Without reading Leonid's answer (which is probably better) I recommend something like this:

fillDates[dates_] :=
Module[{f, all},
all = Part[DateList /@ (Range[##, 24*60^2] & @@
AbsoluteTime /@ dates[[{1, -1}, 1]]), All, {1, 2, 3}];
(f[#[[1]]] = #) & ~Scan~ dates;
f[x_] := {x, 0};
f /@ all
]

fillDates @ {{{2012, 1, 1}, 1}, {{2012, 1, 2}, 2}, {{2012, 1, 5}, 3}, {{2012, 1, 8}, 4}}

{{{2012, 1, 1}, 1}, {{2012, 1, 2}, 2}, {{2012, 1, 3}, 0},
{{2012, 1, 4}, 0}, {{2012, 1, 5}, 3}, {{2012, 1, 6}, 0},
{{2012, 1, 7}, 0}, {{2012, 1, 8}, 4}}


I believe the method is sound, and should be fast, but I haven't tuned it at all or even compared it with your own. I'll try to refine it later tonight or tomorrow.

### Improved version

fillDates2[dates_] :=
{#, Replace[#, Dispatch@Append[Rule @@@ dates, _ -> 0], {1}]}\[Transpose] & @
Part[DateList /@ Range[##, 24*60^2] & @@ AbsoluteTime /@ dates[[{1, -1}, 1]], All, ;; 3]


### Timings versus other methods posted

genDates = {#, RandomInteger[{1, 9}]} & /@
Union @ Part[DateList /@
RandomInteger[AbsoluteTime /@ {{#, 1, 1}, {2012, 12, 31}}, {#2}],
All, ;; 3] &;

time100 = Function[, First@AbsoluteTiming@Do[#, {100}]/100, HoldFirst];

dates = genDates[2006, 1500]; (* dense data *)

fillDates2 @ dates // time100

fillDateGapsJ @ dates // time100

fillDatesJM @ dates // AbsoluteTiming // First

fillGapsRM @ dates // AbsoluteTiming // First


0.004970284

0.006330362

1.9541118

1.0810618

dates = genDates[2000, 50]; (* sparse data *)

fillDates2 @ dates // time100

fillDateGapsJ @ dates // time100

fillDatesJM @ dates // AbsoluteTiming // First

fillGapsRM @ dates // AbsoluteTiming // First


0.007540432

0.007910453

1.7681011

1.7300989

• Wow, that's impressive. It is twice faster than my Java code, on my tests. +1. – Leonid Shifrin Oct 9 '12 at 0:28
• Actually, for really large lists of dates, my Java code starts to be faster, but it is also much uglier, and needs an additional infrastructure (Java, the reloader). – Leonid Shifrin Oct 9 '12 at 0:32
• I am probably in the phase where I don't want to spend any effort on optimizing M code with our usual tools. Basically, a version of my top-level recursive code would run reasonably fast in a decent compiled functional language. I am pretty tired of tricks and clever ways to optimize in Mathematica, and then I also overlook some really good ones too, like yours here. – Leonid Shifrin Oct 9 '12 at 0:42
• @Mr.Wizard You should not be worried, this is a deeply personal matter. I just started to dislike it more when M is bending us to think in a very particular way not because the problem algorithmically requires it, but because M's computational model requires such reformulations for the code to be efficient. Elegant code with a good underlying algorithm should IMO be always fast, which is very often not the case in M. Packed arrays etc are good practical means to speed up code in M, but from the language design perspective this is a hack, used to avoid a tougher problem of full compilation. – Leonid Shifrin Oct 9 '12 at 15:57
• @Mr.Wizard I also do not exclude that this is a price to pay for the incredible interactivity and high-level power of Mathematica. But I also hope that in the future at some point one would be able to improve on this part. Actually, this is one of the things which interest me the most. – Leonid Shifrin Oct 9 '12 at 16:22

### Top-level solution based on recursion

I suggest a solution based on linked lists and recursion. It will not be blazing fast, but I think it is conceptually rather simple. Here is the code:

Clear[toLinkedList];
toLinkedList[lst_] := Fold[ll[#2, #1] &, ll[], Reverse@lst]

ClearAll[fillGaps];
fillGaps[dates_] :=
Block[{\$IterationLimit = Infinity},

fillGaps[accum_, ll[val : {d_, _}, tail : ll[{dn_, _}, _ll]]] :=
With[{nxt = DatePlus[d, 1]},
fillGaps[
If[nxt === dn, ll[accum, val], accum],
If[nxt === dn, tail, ll[val, ll[{nxt, 0}, tail]]]
]];

fillGaps[accum_, ll[val_, ll[]]] :=
Append[List @@ Flatten[accum, Infinity, ll], val];


The logic is straightforward: if we have two consecutive dates, we add the first to the linked list of accumulated results, and remove it from the remaining list of dates. If not, we insert an extra date adjacent to the first one, after the first one, and repeat. For those who are wondering why I have duplicate code with the comparisons inside If statements, this is needed to make the function properly tail-recursive in Mathematica sense.

Here is the usage:

fillGaps[dateList]

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


My main message here is to not measure the simplicity necessarily by lines of code. This problem is a look-ahead type problem, and therefore linked lists and recursion seem a natural vehicle for solving it. OTOH, fitting it into the dominant Mathematica execution model where lists are operated on as a whole is of course possible, but IMO rather inelegant and indirect.

### Java solution

JCompileLoad@"import java.util.*;

public class DateGapFiller{
public List<int[]> newDates = new ArrayList<int[]>();
public List<Double>  newVals = new ArrayList<Double>();

public DateGapFiller(int[][] dates, double[] values){
if(dates.length==0) return;
Calendar c = Calendar.getInstance();
c.set(dates[0][0],dates[0][1]-1,dates[0][2]);
for(int i = 1, ctr = 0; i<dates.length;ctr++){
int y = c.get(Calendar.YEAR);
int m = c.get(Calendar.MONTH)+1;
int d = c.get(Calendar.DAY_OF_MONTH);
int[] newDate = new int[]{y,m,d};
double newVal = 0;
if(dates[i][0]== y && dates[i][1] == m && dates[i][2] == d){
newDate = dates[i];
newVal = values[i];
i++;
}
}
}
}"


The top - level code is

ClearAll[fillDateGapsJ];
fillDateGapsJ[dates_List] :=
Block[{newDates, newVals, toArray},
JavaBlock[
With[{res = JavaNew["DateGapFiller", Sequence @@ Transpose[dates]]},
Transpose[res[#][toArray[]] & /@ {newDates, newVals}]
]]];


The usage is the same:

fillDateGapsJ[dateList]


The speed comparison:

dates =
NestList[
{DatePlus[#[[1]],RandomInteger[{1,5}]],RandomInteger[10]}&,
{{2000,1,1},1},
1000
];

(filled1= fillDateGaps[dates]);//AbsoluteTiming
(filled2= fillDateGapsJ[dates]);//AbsoluteTiming
filled2 == filled1

(*
{2.4482422,Null}
{0.0751953,Null}
True
*)


So you get about 30x speedup.

### Remark

You may actually want to develop some custom data structure for "gapped dates" and a relevant custom plotting routine, as an alternative to all this. Which way to go depends on what you want to do with your data,of course.

• Hi Leonid. I get an error with your suggestion. There is my test: drange = getDateRange[{2012, 1, 1}, {2014, 12, 31}]; dateList = RandomChoice[{#, RandomInteger[100]} & /@ drange, 600]; fillGaps[dateList] – Murta Oct 8 '12 at 23:48
• @Murta Good point, I modified the code to handle long lists. But for your test to be fine, you also have to change to dateList = SortBy[RandomChoice[{#, RandomInteger[100]} & /@ drange, 10], First];, so that dates are sorted. Note that for your ranges, my top-level code will be very slow. Note also that I added fast Java code. Finally, if you have really huge gaps (sparse data), you will be much better off by developing some custom data structure and other routines for such data. – Leonid Shifrin Oct 9 '12 at 0:03
• Tks Leonid. I fell that some operations could be more simple for some basic things in Mathematica. – Murta Oct 9 '12 at 1:25

## TemporalData & ResamplingMethod

dateList = {{{2012, 1, 1}, 1},{{2012, 1, 2}, 2},{{2012, 1, 5}, 3},{{2012, 1, 8}, 4}};

td = TemporalData[#2, {#}, ResamplingMethod -> {"Constant", 0}]& @@ Transpose[dateList];

daterange = AbsoluteTime /@ DateRange[dateList[[1, 1]], dateList[[-1, 1]], {1, "Day"}];

DateListPlot[td["PathFunction"] /@ daterange, dateList[[1,1]],
Epilog -> {PointSize[Large], Red, Point @ dateList},
FrameTicks -> {{Automatic, Automatic}, {dateList[[All,1]], Automatic}}]


You can also create a new TemporalData and plot it:

td2 = TemporalData[td["PathFunction"]/@daterange, {daterange}];
DateListPlot[td2, Epilog -> {PointSize[Large], Red, Point @ dateList},
FrameTicks -> {{Automatic, Automatic}, {dateList[[All,1]], Automatic}}]


same picture

• Had to delete final "]" from both DateListPlot's for this to work. +1 – Christopher Lamb Dec 30 '17 at 16:28
• Thank you @Rabbit; fixed the typos. – kglr Dec 30 '17 at 20:06

I would suggest a simple solution based on replacement rules:

fillGaps[list_] := With[{rules = (Rule @@@ list) ~Join~ {_List -> 0}},
NestWhileList[
Composition[{#, # /. rules} &, DatePlus[#, 1] &, First],
First@list,
First@# =!= list[[-1, 1]] &]
]

fillGaps[dateList]
(* {{{2012, 1, 1}, 1}, {{2012, 1, 2}, 2}, {{2012, 1, 3}, 0}, {{2012, 1, 4}, 0},
{{2012, 1, 5}, 3}, {{2012, 1, 6}, 0}, {{2012, 1, 7}, 0}, {{2012, 1, 8}, 4}} *)