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.”
Using
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.
Using
[...] wrote about boost library for [...]
Using
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.
Using
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).
Using
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 -lUsing
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 -lfixt
Using
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
Using
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′
Using
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.
Using
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);
Using
Correction: That’s not a Zellers Congruence algorithm. It’s from Tomohiko Sakamoto – see comp.lang.c faq for details.