Boost logo

Boost :

Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2010-02-28 12:53:57

Barend Gehrels wrote:
> Phil claimed that:
>> "consider trying to store the lifespans of people in a genealogy
>> program: recording a few thousand people living over a few hundred
>> years would approach the worse-case space complexity and need
>> megabytes of storage"
> This was part of my motivation to do project 1 above, because these few
> thousand people over a few hundred years is exactly what I have.
> Boost.Itl calculates and reports the livespans in 0.031 seconds. So,
> measured in time, no problem at all. I compared it with another
> implementation which run in 0.032 seconds, so the same. I will not say
> that it cannot be enhanced somehow or whatever, I didn't study it in
> depth, I would only say: the library is well performing, also if the
> input set grows larger. It should not be rejected for the assumption
> that it could have been built otherwise.

Barend, there are a couple of problems with your test.

The space complexity is only quadratic in the case where the map's
value types for overlapping intervals are all stored. Looking at your
example code:

> typedef itl::interval_map<int, int> map;
> map livetimes;
> ...
> livetimes += std::make_pair(itl::interval<int>(, death_date), 1);

You are just storing the number of people living on any particular
date. Try changing your code to record all of the names, e.g.
something like:

typedef itl::interval_map<int, string> map;
map livetimes;
livetimes += std::make_pair(itl::interval<int>(,

More fundamentally, you are taking my observation that it has poor
space complexity and then measuring the execution time. This is
obviously flawed, as time and space complexity are different things.


Boost list run by bdawes at, gregod at, cpdaniel at, john at