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

Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Barend Gehrels (barend_at_[hidden])
Date: 2010-02-28 14:29:51

Hi Phil,

> 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.
OK, I see. But you didn't mention that in your review. So yes, I 
understand, if you store names to the intervals as sets, and split an 
interval each time, you will get a fragmented map of fragmented sets. 
However, I did this at start, so read on.
> 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:
Yes, I did this in my review. The first version of my program listed 
like this:
    typedef boost::itl::set<std::string> itl_set_string;
    typedef boost::itl::interval_map<int, itl_set_string> itl_map;
    (...)
    itl_set_string person;
    person.insert(p.indi.name);

    int death_date = p.indi.death.date.hasdate ? p.indi.death.date.year 
: 9999;
    livetimes.add(std::make_pair( 
boost::itl::interval<int>::rightopen(p.indi.birth.date.year, 
death_date), person));
    (...)
    itl_set_string const& who = it->second;
    stream << when.first() << " - " << when.upper() << " : " << 
who.size() << std::endl;

But I then realized that this did too much, because I only wanted to 
know how much persons are alive in what period. So I did a second 
implementation and timing.

Also this first test did have no noticeable delay. It is subsecond, and 
I did also write the names of all these persons in this test which 
should not be timed, so it is not problematic.

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

You mentioned the time as well:
> but to do so it needs worst-case O(N2) space and I think it needs O(N2 
> log N) time to build that structure. 
so I measured time and, admitted, I didn't measure space. I only observe 
that it runs fast in the example you are giving.

Regards, Barend