Re: [boost] [time_series] Review

From: Eric Niebler (eric_at_[hidden])
Date: 2007-08-09 22:40:56

Steven Watanabe wrote:
> AMDG
> 
> Eric Niebler <eric <at> boost-consulting.com> writes:
> 
>> How would you suggest ordered_append be implemented?
> 
> Mostly copied from dense_ordered_inserter:

<snip>

Hmm, yes an in-place append would be a good addition. Agreed.

>> Imagine the series storage is std::map<offset, value>. Inserting one 
>> value with insert(value) is O(log N). Inserting N values this way is O(N 
>> log N). But if you use insert(begin, end), where begin and end are 
>> iterators to sorted data, the insert is faster. O(N).
> 
> It is in fact possible to fill a binary tree by pushing
> sorted data in linear time.

<snip>

I don't doubt it. std::map does it for its range-based insert so it must 
be possible. And this may seem like splitting hairs to you, but what I 
said is true -- you can't efficiently build a std::map by pushing in 
sorted data in one element at a time, because the interface doesn't 
allow for it. You have to pass it a range of sorted elements. You may 
say, "Well, then don't use a std::map to build a time series!" Fair 
enough. But when a perfectly satisfactory data structure like std::map 
cannot be adapted to satisfy a concept, it suggests a faulty concept.

>> The point is, you should be able to efficiently be able to 
>> write ordered data to a series without any concern for how that data is 
>> being stored, or even if it's being stored.
> 
> I don't think you should have *only* a range insert.
> I think an output iterator that behaves more like
> std::back_inserter is necessary too.

An in-place append, yes.

>> But the lower-level stuff is still needed so that series types can be 
>> efficiently built in generic code (like the time series algorithms, for 
>> instance), which can't make any assumptions.
> 
> I agree that we need the lower level stuff.  I just disagree
> about *what* lower level stuff.

You're suggesting to replace the ordered_inserter (actually an 
ordered_assign) with an ordered_append? And perhaps also a clear() 
member? Or keep ordered_assign?

And (crucially) you would do away with commit() on both ordered_assign 
and ordered_append? Or would you keep them on the low-level interface 
and add a higher level interface that called commit for you and handled 
the 90% case?

The thoughts I've heard that I like so far are:

- add an ordered_append
- rename ordered_inserter to ordered_assign
- add a higher level interface to make them both easier to use

The thought I'm not sold on is:

- get rid of commit() on the lower level interface.

<snip>

> Actually what I would like most is
> 
> ordered_inserter inserter(series);
> for(;;)
>     *insert++ = make_tuple(poll_some_value(), last_time, current_time);
> 
> With the additional guarantee that you can
> process the partial results at any time.

OK. It seems to me that such a thing could be built on top of an 
ordered_append that has a commit(), simply by calling commit() after 
every appended element. Would you agree?

Thought: it occurs to me that commit() is a bad name. It is evocative of 
transactional semantics, which is not necessarily accurate. What I'm 
looking for is a way to signal the end of an input sequence, such that 
*if* the series has decided to buffer the input, it now knows it has 
received it all. It doesn't *have* to buffer the input, though. Maybe 
done() or end() or even eof().

Anyway, the STL-ish assign(begin,end) doesn't have this problem because 
the end is specified explicitly and it has extra benefits (the size may 
be known), but this doesn't mesh well with the signal processing domain. 
In assign(begin,end), the container *pulls* the data. In signal 
processing, data is often read by polling, and then *pushed* into a 
container, hence the desire for something like a back_inserter.

Time passes ...

If we ditched the assigners and the appenders and went with the 
range-based STL-ish interface, what happens? Any convenient push-based 
interface we build on top would have to resort to sticking in one value 
at a time, just like std::back_inserter. Do you really feel that's an 
improvement? It's an honest question.

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