# Faster alternatives for DayOfWeek

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?

-
Here comes the self-answer :) – Rojo Jun 20 '12 at 19:39
– belisarius Jun 20 '12 at 19:47

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

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

-
+1. It is then really a shame that the Calendar  package function can be beaten several times by a completely top-level implementation. – Leonid Shifrin Jun 20 '12 at 22:15
Floor[c/4] is better written as Quotient[c, 4], I'd say. – 0x4A4D Jun 20 '12 at 23:17
Also, you could compact things a bit with {c, y} = QuotientRemainder[Y, 100] – 0x4A4D Jun 20 '12 at 23:19
I see you guys always use AbsoluteTiming, which gives you the elapsed real world time. Isn't Timing more appropriate, since it only seems to count the time spent by the kernel? – stevenvh Oct 10 '12 at 18:52

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

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] :=
DayOfWeekCalculatorgetDaysOfWeek@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).

-
 item 3, indeed, it is, see my own answer. – Andreas Lauschke Jul 6 '12 at 0:38

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

-
That switching date is valid only for weird island dwellers (and their sphere of influence) who always want to do things the unusual and inconvenient way :P – Szabolcs Jun 21 '12 at 15:15

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

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.

-
 Very cool, pretty fast ineed, +1. – Leonid Shifrin Jun 22 '12 at 21:54
Needs["JLink"];
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.

-
+1. I thought about using Joda library in my answer as well, but did not want to introduce external dependencies. The reason I provided a vectorized (longer) version in my answer is to outsource loops to Java. Without doing this, it would not really matter how fast is individual day of week computation in Java, since the call to Java method via JLink has a constant overhead, which is in fact much larger than this computation time. I avoid this overhead by calling the function only once, and of course also Java loops are very much faster than top-level M loops. – Leonid Shifrin Jul 6 '12 at 8:25
@Leonid: Yepp, fully agreed. I like short code and have no qualms about external dependencies. – Andreas Lauschke Jul 6 '12 at 13:26
Although my solution is 8 months old, I probably should add that Joda Time was upgraded to 2.2 on March 8. The download link is sourceforge.net/projects/joda-time/files/joda-time/2.2 – Andreas Lauschke Mar 12 at 18:47
Oh boy, it's been 8 months already. The time is flying. Can't say I am too happy about that, I could have been more productive... – Leonid Shifrin Mar 12 at 18:57

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.

-
+1. I should try using Joda library to see if I can beat that, but even if it so happens that pure Java code is somehow faster, I will probably lose anyway due to JLink/MathLink data transfer overhead - not to mention that this overhead is huge for smaller lists, which is not the case for LibraryLink. – Leonid Shifrin Mar 12 at 18:40
@LeonidShifrin That could be very interesting. I was astonished how fast your JLink/MathLink implementation was anyways and your JavaReloader is just simply genius. Why do I not come to an idea like that...sigh.... – Stefan Mar 12 at 18:46
part1: @Stefan, indeed, if the programmer knows what he/she is doing, then native code is not a problem. Hell, we can crash M with kernel commands alone. Regarding Java's legacies, indeed, Java is a pretty bad language by today's standards, but the performance is in the JVM. That's one of the reasons my product JVMTools supports Scala, because Scala is the "professional Java" nowadays, and also runs on the JVM. Performance-wise, there is no difference between Java-compiled and Scala-compiled code. If you want the speed of the JVM but a professional language for it, look no further than Scala. – Andreas Lauschke Mar 12 at 19:35
You should! @Leonid would that be something for the blog? I find that really interesting and I'm really curious in interfacing with mathematica, especially from a professional point of view. By professional I mean really serious stuff not just mumbo-jumbo...I think decent interfacing with the system could lead it into other environments where M doesn't play a role...but...sigh...Matlab (sorry for being religious...). High performance secure interfaces. That would be a go I presume... – Stefan Mar 12 at 19:57
Yes, that sounds good :-) – Leonid Shifrin Mar 12 at 20:17
show 27 more comments