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