Re: [boost] [Review] ITL review starts today, February 18th

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>(p.indi.birth.date.year, 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>(p.indi.birth.date.year, 
death_date), p.name);

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.

Phil.