Boost library rocks!
26 12 2007I have been messing with a project through the university and we decided that we would go with the Boost library for the project, so to read up on Boost and how to use it, I decided I would attack Project Euler using Boost. One area that Boost really showed its strength was determining how many Sundays fell on the first day of the month between January 1, 1901 and December 31, 2000. In just a few lines, the answer was apparent. Here is the lines of code that answers this problem, and answers it immediately. I had used other calendar solutions in C++ in the past, but the gregorian.hpp library is fast.
#include <iostream> #include "boost/date_time/gregorian/gregorian.hpp" int main(void) { using namespace boost::gregorian; int count = 0; date_period dp(date(1901, Jan, 1), date(2000, Dec, 31)); day_iterator iter(dp.begin()); while (iter != dp.end()) { if (iter->day() == 1 && iter->day_of_week().as_enum == 0) count++; ++iter; } std::cout << count << std::endl; return 0; }
The answer takes milliseconds, it is just that fast. Right now I would like to replace my gmpxx libraries for big numbers with a boost library and I think all of my Euler answers will be “boosted.”
time “miliseconds” doesn’t look impressive at all.
on my desktop machine (dual code intel 1.8ghz, 2gb ram) i can find it in 5ms using *SQL*:
# select count(*)
=# from (
=# select
=# cast(start.date + ‘1 month’::INTERVAL * generate_series(0, (finish.date - start.date)/28) as date) as date,
=# finish.date as “finish”
=# from
=# (select ‘2000-12-31′::date as date) as finish, (select ‘1901-01-01′::date as date) as start
=# ) x
=# where 1 = extract(day from x.date) and 0 = extract(dow from x.date) AND x.date <= x.finish
=# ;
count
——-
171
(1 row)
Time: 4.953 ms
this is postgresql.
i would hope that boosting library to be at least an order of magnitude faster.
[...] wrote about boost library for [...]
Problem 19 Answer: 171
0.02 s
This is a Celeron M 420 (1.6GHz) w/ 1.5GB of RAM. Better than the 1s I was getting with other library implementations for sure, and definitely a heck of a lot less code.
Just had to try it in Python…
from datetime import date,timedelta
delta = timedelta(1)
d,end = date(1901, 1, 1),date(2000, 12, 31)
sundays = 0
while d < end:
if d.day == 1 and d.weekday() == 6:
sundays +=1
d += delta
print sundays
I tried to measure the time and it varies between 15-50ms (AMD 64 4200+ win XP).
Psh, bash 4tw:
for i in `seq 1 12` ; do for j in `seq 1901 2000`; do cal $i $j | grep " 1 2 3 4 5 6 7"; done; done | wc -lfor i in `seq 1 12` ; do for j in `seq 1901 2000`; do cal $i $j | grep " 1 2 3 4 5 6 7"; done; done | wc -lfixt
Ugh, it messes up the spaces, this one actually works
for i in `seq 1 12` ; do for j in `seq 1901 2000`; do cal $i $j | sed ’s/ //g’ | grep 1234567 ; done; done | wc -l
this version of shell should be a bit faster:
for a in `seq 1901 2000`; do cal $a; done | sed ’s/ /\n/g’ | grep -c ‘^ 1 2 3 4 5 6 7′
hmm - there should be *3* spaces in sed. i dont know how to add them in comment box. but it should be like:
sed ’s/XXX/\n/g’
where “X” is space.
JavaScript version using Zeller’s Congruence (doesn’t anyone read the comp.lang.c FAQ nowadays?). I haven’t timed it, but it’s on the order of milliseconds:
window.Zeller={};
Zeller.getDayOfWeek = function(y, m, d) {
var t = [0,3,2,5,0,3,5,1,4,6,2,4];
y-=m<3;
return (y+Math.floor(y/4)-Math.floor(y/100)+Math.floor(y/400)+t[m-1]+d)%7;
}
var sundayCount=0;
for(var i=1901; i<=2000; i++) {
for(var j=1; j<=12; j++) {
if(Zeller.getDayOfWeek(i, j, 1)==0) {
sundayCount++;
}
}
}
document.write(”Number of sundays between 1901-01-01 and 2000-12-31 is ” + sundayCount);
Correction: That’s not a Zellers Congruence algorithm. It’s from Tomohiko Sakamoto - see comp.lang.c faq for details.