Re: [boost] [time_series] Review

From: Eric Niebler (eric_at_[hidden])
Date: 2007-08-08 20:06:22

Steven Watanabe wrote:
> AMDG
> 
> Eric Niebler <eric <at> boost-consulting.com> writes:
> 
>>> I strongly dislike ordered_inserter.  Its name
>>> indicates to me that it adds elements to a time_series--not
>>> at all that it deletes all pre-existing elements.  I would
>>> expect it to overwrite the old elements only where a new
>>> element is specified.
>> That's a valid criticism. Can you suggest a better name?
> 
> I can't say that I'm really comfortable
> with the way ordered_inserter works regardless
> of the name.  I would like it to behave something
> along the lines of:
> 
> The inserter puts elements directly in the series eliminating
> the need for commit.  It is an error when the series has elements
> after the offset of the inserter.  An inserter is invalidated
> when the container is modified without using the iterator.

It's not exactly what you're asking for, but if you want to modify a 
time_series in-place, you can do that with range_run_storage::set_at(). 
It's a terrible way to build a series though, because you need to find 
the place in the series where this element should be inserted (could be 
O(log N)) and then insert it (could be O(N)).

You seem to be asking for an ordered_append feature. That might be 
useful to add.

> Is there some reason why this doesn't work?  If I need the
> other behavior I can always create a new series fill it and swap
> myself.

Fill it how? That's exactly what ordered_inserter is for! So you can 
see, ordered_inserter is necessary. But the name isn't right.

The reason for ordered_inserter's existence is that it is the fastest 
way to build a time_series from scratch, regardless of the internal 
representation. When you know elements are sorted, you can just bang 
them into a dense vector, sparse vector, map, or what-have-you -- very 
efficient. Once you have a time series, there are other ways to 
manipulate it.

The reason for .commit() is that, since you're pushing in one datum at a 
time, there may be a more efficient intermediate representation than the 
final time series data structure. For the scenarios I've encountered, 
being able to efficiently build a series by pushing in one datum at a 
time is important.

The alternative would be use a range-based interface like the STL uses. 
E.g.:

   series.assign( from, to );

Here, "from" and "to" can't really be iterators though, or, if they are, 
they should yield a 3-tuple of (value, offset, end offset). An interface 
like this is very unwieldy in signal processing, where you often collect 
data by polling a value at an interval.

   for(;;)
     series.push_back(poll_some_value(), last_time, current_time);

Of course, push_back() may not be the most efficient way to build up 
some kinds of data structures. What the ordered_inserter gives is a way 
have something as efficient as a range-based assign() while retaining 
the poll-and-push-back convenience.

Does that make sense?

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com
The Astoria Seminar ==> http://www.astoriaseminar.com