Faster alternatives for DayOfWeek

Question

It has been noticed on several occasions that DayOfWeek function is rather slow when applied to a large list of dates, e.g. in this recent question. What faster alternatives do we have in such situations?

Answer 1

Just a literal implementation of a formula for the day of the week:

Clear[dow];
dow[{year_, month_, day_, _ : 0, _ : 0, _ : 0}] :=
  Module[{Y = If[month == 1 || month == 2, year - 1, year], 
    m = Mod[month + 9, 12] + 1, y, c, 
    s = {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}},
    y = Mod[Y, 100];
    c = Quotient[Y, 100];
    s[[Mod[day + Floor[2.6 m - 0.2] + y + Quotient[y, 4] + Quotient[c, 4] - 2 c, 7] + 1]]];

Seems to give a 5-fold speed increase:

d = RandomDates[100000];
DayOfWeek /@ d // Short // AbsoluteTiming
dow /@ d // Short // AbsoluteTiming

{19.5781250,{Thursday,Thursday,Sunday,Friday,<<99992>>,Tuesday,Saturday,Saturday,Thursday}}

{3.7968750,{Thursday,Thursday,Sunday,Friday,<<99992>>,Tuesday,Saturday,Saturday,Thursday}}

Addition

Your function is readily compilable:

dowc = Compile[{{year, _Integer}, {month, _Integer}, {day, _Integer}},
    Module[
        {Y, m, y, c, s},
        Y = If[month == 1 || month==2, year-1, year];
        m = Mod[month + 9, 12] + 1; 
        y = Mod[Y, 100]; c = Quotient[Y, 100];
        Mod[day + Floor[2.6 m-0.2] + y + Quotient[y, 4] + Quotient[c, 4]-2 c,7]+1
    ],
    CompilationTarget -> "C",
    RuntimeAttributes -> {Listable},
    Parallelization -> True
];

In[286]:= dowc @@@ d[[All, 1 ;; 3]] // Short // AbsoluteTiming
Out[286]= {0.136741,{6,4,5,2,4,5,3,7,<<99984>>,5,4,2,4,3,2,5,6}}

Answer 2

I will provide one solution which will be using Java and a simple Java reloader I recently introduced. This solution brings to the table up to 100-fold speed-up for large lists of dates.

Preparation

I will borrow @Mike's functions to generate a random list of dates, from his code in his recent question

RandomDateList[] := {
   RandomInteger[{1800, 2100}], 
   RandomInteger[{1, 12}], RandomInteger[{1, 28}], 
   RandomInteger[{0, 23}], RandomInteger[{0, 59}], 
   RandomInteger[{0, 59}]
};

RandomDates[n_] := Table[RandomDateList[], {n}]

Implementation

1. Load the Java reloader

2. Compile the following class:

   JCompileLoad@
     "import java.util.*;
      public class DayOfWeekCalculator {
          public static int[] getDaysOfWeek(int[][] dateDataList){
             Calendar calendar = new GregorianCalendar();
             int[] result = new int[dateDataList.length];
             int ctr = 0;
             for(int[] date: dateDataList){                        
                calendar.set(date[0],date[1],date[2]);
                result[ctr++]=calendar.get(Calendar.DAY_OF_WEEK);
             }
             return result;    
          }    
      }"
   

3. The actual function is then:

   Clear[dayOfWeek];
   dayOfWeek[dates_List] :=
      DayOfWeekCalculator`getDaysOfWeek@Transpose@
          {#[[All, 1]], #[[All, 2]] - 1, #[[All, 3]]} &@dates;
   

The input is a nested list of the type we construct randomly, which is a natural date format as it appears in Mathematica. I subtract 1 from month, to comply with the Java conventions.

Use and benchmarks

d=RandomDates[100000];

dayOfWeek[d]//Short//AbsoluteTiming

(*
   {0.1259765,{6,6,1,3,6,6,3,5,3,2,2,4,4,5,6,3,4,2,5,6,7,2,4,
     <<99954>>,2,2,3,1,1,6,5,7,6,7,5,1,6,3,7,4,6,4,5,7,4,1,3}}
*)

DayOfWeek/@d//Short//AbsoluteTiming

(*
    {14.0732422,{Friday,Friday,Sunday,Tuesday,Friday, 
     <<99990>>,Thursday,Saturday,Wednesday,Sunday,Tuesday}}
*)

There is a 100-fold speedup for this example. Note that there is a small constant overhead of calling Java, so the larger is your list of dates, the more you gain.

Remarks

I think that this can be one of the "canonical" examples of a situation where the use of Java is more than appropriate. Generally, this happens when some of the following is true:

• You have a large collection of Mathematica objects, which you want to process somehow.
• The top-level overhead of explicit looping is (very) large, but the problem is not easily amenable to Compile
• The functionality you seek for is readily available via Java libraries, or can be easily implemented using those.

Effective use of Java / JLink implies that loops are outsourced to Java. Only then the overhead of Java / JLink will not play a big role. Performing looping in Mathematica while invoking Java functions is likely to not be faster, and often be slower, than doing it all in Mathematica.

A big thanks goes to @Mike for spotting a bug in the reloader (which has been now fixed).

Answer 3

I've shown off Larsen's method before (and see this as well), but here it is as a formal answer:

larsen[{yr_Integer, mo_Integer, da_Integer, ___}] := Module[{y = yr, m = mo, d = da, q},
  If[m < 3, y--; m += 12];
  q = d + 2 m + 1 + Quotient[3 (m + 1), 5] + y + Quotient[y, 4] +
      Quotient[y, 400] - Quotient[y, 100];
  {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}[[Mod[q, 7] + 1]]]

This assumes the use of the Gregorian system, so this will require some modification if you need to work with dates older than the switching date September 14, 1752 (where the Julian system was still in use).

---

Here's how to adapt larsen[] for both Julian and Gregorian systems:

Options[larsen] = {"Calendar" -> "Gregorian"};

larsen[{yr_Integer, mo_Integer, da_Integer, ___}, OptionsPattern[]] :=
Module[{y = yr, m = mo, d = da, q, f},
       If[m < 3, y--; m += 12];
       f = Switch[OptionValue["Calendar"],
                  "Gregorian", Quotient[y, 400] - Quotient[y, 100],
                  "Julian", 5,
                  _, Return[]];
       q = d + 2 m + 1 + Quotient[3 (m + 1), 5] + y + Quotient[y, 4] + f;
       {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}[[Mod[q, 7] + 1]]]

Answer 4

This recent post reminded me that AbsoluteTime is a fast kernel function.

Using the RandomDates function from Leonid's post:

dates = RandomDates[500000];

Needs["Calendar`"]

rls = Thread[
       Range[0, 6] -> 
        {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}
      ];

Timing[result1 = DayOfWeek /@ dates;]

Timing[result2 = Mod[Quotient[AbsoluteTime /@ dates, 60^2 24], 7] /. rls;]

result1 === result2

{37.783, Null}

{0.921, Null}

True

~ 41X speed-up.

Answer 5

Needs["JLink`"];
AddToClassPath[ToFileName[{$HomeDirectory,"javafiles","joda-time-2.1"}]];
JavaNew["org.joda.time.DateTime",2012,4,17,0,0]@dayOfWeek[]@getAsText[]

Super-fast. You need the Joda Time library for that.

If you're a hardcore JLink user, you have the first two lines in your init.m anyway, so the problem reduces to 71 characters, with an amazing speed.

Joda Time is ISO 8601-compliant.

Answer 6

I will provide one solution which will be using ANSI C and LibraryLink. Needless to say that this is a speeder...(Platform: MacOSX, gcc 4.2)

The preparations are the same as in Leonid's answer.

Implementation

dayofweek = "
#include \"WolframLibrary.h\"

DLLEXPORT mint WolframLibrary_getVersion(){
   return WolframLibraryVersion;
}

DLLEXPORT int WolframLibrary_initialize( WolframLibraryData \
  libData) {
return 0;
}

DLLEXPORT void WolframLibrary_uninitialize( WolframLibraryData \
  libData) {
return;
}

#define _LEAP_YEAR(year)  (((year) > 0) && !((year) % 4) && \
    (((year) % 100) || !((year) % 400)))

#define _LEAP_COUNT(year) ((((year) - 1) / 4) - (((year) - 1) / \
    100) + (((year) - 1) / 400))

const int yeardays[2][13] = {
  { -1, 30, 58, 89, 119, 150, 180, 211, 242, 272, 303, 333, 364 },
  { -1, 30, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 }
};

const int monthdays[2][13] = {
  { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
  { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }
};

int weekday(int year, int month, int day)
{
  int ydays, mdays, base_dow;
  /* Correct out of range months by shifting them into range (in the same year) */
  month = (month < 1) ? 1 : month;
  month = (month > 12) ? 12 : month;
  mdays = monthdays[_LEAP_YEAR(year)][month - 1];
  /* Correct out of range days by shifting them into range (in the same month) */
  day = (day < 1) ? 1 : day;
  day = (day > mdays) ? mdays : day;
  /* Find the number of days up to the requested date */
  ydays = yeardays[_LEAP_YEAR(year)][month - 1] + day;
  /* Find the day of the week for January 1st */
  base_dow = (year * 365 + _LEAP_COUNT(year)) % 7;
  return (base_dow + ydays) % 7;
}

DLLEXPORT int dayOfWeek(WolframLibraryData libData,
        mint Argc, MArgument *Args, MArgument Res) {
  mint I0, I1, I2;
  I0 = MArgument_getInteger(Args[0]);
  I1 = MArgument_getInteger(Args[1]);
  I2 = MArgument_getInteger(Args[2]);

  MArgument_setInteger(Res, weekday(I0, I1, I2));
  return LIBRARY_NO_ERROR;
}
";

Create the Library and load it

lib = CreateLibrary[dayofweek, "dayOfWeek", CompileOptions -> "-O3 -funroll-loops"];
dow = LibraryFunctionLoad[lib, "dayOfWeek", {Integer, Integer, Integer}, Integer];

Microsoft's compiler (CL) has similar options with just different naming...

The dayOfWeek function

Clear[dayOfWeek];
dayOfWeek[dates_List] := 
   dow[#[[1]], #[[2]], #[[3]]] & /@ 
      Transpose@{#[[All, 1]], #[[All, 2]] - 1, #[[All, 3]]} &@dates

Timing

dayOfWeek[RandomDates[100000]] // Short // AbsoluteTiming
{0.067380,{6,5,6,6,3,2,0,0,4,6,4,3,5,3,4,6,6,<<99966>>,...}}

Conclusion

As the argumentation holds to use Java, because of it's simple interface I think I've shown that this holds as well for C/C++ and is unbeatable fast.