Boost logo

Boost :

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>(,
>> 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;

    int death_date = ?
: 9999;
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>(,
> death_date),;
> 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

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