Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

One basic problem when working with data like sales and dates is the case where you dont'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 fell 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?

share|improve this question
    
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
add comment

3 Answers

up vote 9 down vote accepted

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

share|improve this answer
    
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
2  
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
1  
@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
1  
@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
show 8 more comments

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.

share|improve this answer
    
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
add comment

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}} *)
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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