Boost library rocks!

26 12 2007

I 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.”


Actions

Informations

11 responses to “Boost library rocks!”

27 12 2007
 depesz (04:29:41) :
 Using Mozilla Firefox 2.0.0.10 on Ubuntu Linux

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.

27 12 2007
 </depesz> » Blog Archive » how many 1sts of any month were sundays - since 1901-01-01? (04:58:02) :
 Using WordPress 2.2.3

[...] wrote about boost library for [...]

27 12 2007
 nixternal (11:49:08) :
 Using Konqueror 3.5 on Kubuntu Linux

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.

27 12 2007
 Fredrik (19:57:24) :
 Using Mozilla Firefox 2.0.0.11 on Windows XP

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).

27 12 2007
 Yacin (20:18:49) :
 Using Safari 523.12.2 on Mac OS X

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

27 12 2007
 Yacin (22:45:21) :
 Using Safari 523.12.2 on Mac OS X

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

fixt

27 12 2007
 Yacin (23:04:23) :
 Using Safari 523.12.2 on Mac OS X

Ugh, it messes up the spaces, this one actually works :P

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

28 12 2007
 depesz (06:12:04) :
 Using Mozilla Firefox 2.0.0.11 on Ubuntu Linux

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′

28 12 2007
 depesz (06:54:54) :
 Using Mozilla Firefox 2.0.0.11 on Ubuntu Linux

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.

29 12 2007
 RichB (09:06:02) :
 Using Mozilla Firefox 2.0.0.11 on Mac OS X

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);

29 12 2007
 RichB (09:24:21) :
 Using Mozilla Firefox 2.0.0.11 on Mac OS X

Correction: That’s not a Zellers Congruence algorithm. It’s from Tomohiko Sakamoto – see comp.lang.c faq for details.

Leave a comment

You can use these tags : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="">