15
$\begingroup$

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]

DateListPlot with filled zeros

How to make it simpler and faster?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Verbeia
    Commented Oct 8, 2012 at 22:00
  • $\begingroup$ 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} $\endgroup$
    – Murta
    Commented Oct 8, 2012 at 23:40
  • $\begingroup$ 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 $\endgroup$
    – Murta
    Commented Oct 9, 2012 at 2:22

5 Answers 5

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
13
  • $\begingroup$ Wow, that's impressive. It is twice faster than my Java code, on my tests. +1. $\endgroup$
    – Leonid Shifrin
    Commented Oct 9, 2012 at 0:28
  • $\begingroup$ 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). $\endgroup$
    – Leonid Shifrin
    Commented Oct 9, 2012 at 0:32
  • 2
    $\begingroup$ 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. $\endgroup$
    – Leonid Shifrin
    Commented Oct 9, 2012 at 0:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – Leonid Shifrin
    Commented Oct 9, 2012 at 15:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – Leonid Shifrin
    Commented Oct 9, 2012 at 16:22
5
$\begingroup$

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

enter image description here

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

TimeSeriesResample + ResamplingMethod

ts = TimeSeriesResample[dateList, {1, "Day"}, 
      ResamplingMethod -> {"Constant", 0}];

DateListPlot[ts, 
  Epilog -> {PointSize[Large], Red, Point@dateList}, 
  FrameTicks -> {{Automatic, Automatic}, {dateList[[All, 1]], Automatic}}]

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Had to delete final "]" from both DateListPlot's for this to work. +1 $\endgroup$
    – Rabbit
    Commented Dec 30, 2017 at 16:28
  • $\begingroup$ Thank you @Rabbit; fixed the typos. $\endgroup$
    – kglr
    Commented Dec 30, 2017 at 20:06
4
$\begingroup$

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[ll[], toLinkedList[dates]]];

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

Addressing your speed request in your edit, here is a Java solution (be sure to load the Java reloader first, along the steps described e.g. here:

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]);
         newVals.add(values[0]);
         newDates.add(dates[0]);        
         for(int i = 1, ctr = 0; i<dates.length;ctr++){    
            c.add(Calendar.DATE,1);
            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++;
            } 
            newVals.add(newVal);
            newDates.add(newDate);          
         }          
       }
   }"

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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] $\endgroup$
    – Murta
    Commented Oct 8, 2012 at 23:48
  • $\begingroup$ @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. $\endgroup$
    – Leonid Shifrin
    Commented Oct 9, 2012 at 0:03
  • $\begingroup$ Tks Leonid. I fell that some operations could be more simple for some basic things in Mathematica. $\endgroup$
    – Murta
    Commented Oct 9, 2012 at 1:25
2
$\begingroup$

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}} *)
Improve this answer
$\endgroup$
2
$\begingroup$ 
dateList =
   {{{2012, 1, 1}, 1}, {{2012, 1, 2}, 2}, {{2012, 1, 5}, 3}, {{2012, 1, 8}, 4}};

All dates between first and last dates:

dateRange = 
 Query[All, 1 ;; 3] @ Apply[DateRange] @ DateBounds @ dateList[[All, 1]]

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

Now we can use the automatic replacement feature of Association:

result = <|Thread[dateRange -> 0], Rule @@@ dateList|>;

DateListPlot[result, GridLines -> Automatic]

enter image description here

List format conversion:

KeyValueMap[List] @ result

{{{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}}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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