Blog Post

Boost library rocks!

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

This entry was posted in Development. Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.
  • 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.

  • Pingback: </depesz> » Blog Archive » how many 1sts of any month were sundays - since 1901-01-01?()

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

  • Fredrik

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

  • Yacin

    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

  • Yacin

    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

  • Yacin

    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.

  • RichB

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

  • RichB

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

  • Subscribe to nixternal.com

     Subscribe in a reader

    Or, subscribe via email:
    Enter your email address:

  • Archives


semidetached
semidetached
semidetached
semidetached
%d bloggers like this: