Re: [boost] Time series: sparse/dense containers for use with non-time-indexed data?

From: Eric Niebler (eric_at_[hidden])
Date: 2007-08-08 21:39:52

Phil Endecott wrote:
> I have had a look at the Time Series docs and it looks like a 
> worthwhile library, though I have not done anything recently with 
> time-indexed data that could use it.
> 
> I have, however, had to deal with sparse vs. dense data structure 
> decisions with other index types, e.g. integers; this leads me to 
> wonder what ties this library specifically to _time_ series.

Well, the TimeSeries concept adds the notion of a discretization -- or 
stride that is implicit between consecutive integral offsets -- or more 
generally, a multiplicative factor to be applied to the difference 
between two offsets, be they integral or floating point. A 
discretization is specific to time series and signal processing, but the 
TimeSeries concept is built on top of other, lower-level storage 
abstractions: InfiniteRangeRunStorage, RangeRunStorage and Sequence.

There is a collection of storage data structures in the time series 
library that model InfiniteRangeRunStorage. They don't have any notion 
of a discretization. They live in the time_series/storage sub-directory.

> One of the elements of this library is a pair of containers that have a 
> common interface but store their contents either in a dense or a sparse 
> structure.  I wonder whether it would be worth generalising those 
> containers to make them applicable to non-time applications - and to 
> make them as close to standard library containers as possible.  One way 
> to approach this would be to think about how a std::map-like interface 
> can be presented to a std::vector, and/or how a std::vector-like 
> interface can be presented to a std::map.  My motivation is that I 
> sometimes find myself with code like this:
> 
> typedef std::map<int,T> T_container;  // I'm not sure yet if this is 
> best stored in a sparse
> T_container tt;                       // (map) or dense (vector) 
> structure, but by making
>                                        // it a typedef I can easily 
> change it later.
> 
> Of course, when I change the typedef from map<int,T> to vector<T> I 
> discover that there are plenty of other places where I have to change 
> the code; for example I have to add or remove '->second' wherever I 
> dereference an iterator.  How about:
> 
> dense_map<int,T> : provides the interface of std::map<int,T> (or a 
> subset of it), implemented using a vector.  Needs to grow the vector 
> when something is inserted.
> 
> sparse_vector<T> : provides the interface of std::vector<T> (or a 
> subset of it), implemented using a map.  Needs an iterator that can 
> point to gaps between the map elements.
> 
> How close do the sparse and dense time series containers come to this?

Very close indeed. If you program to the RangeRunStorage concept, you 
can use either dense_array or sparse_array (in the time_series::storage 
namespace) interchangeably. I think there is an opportunity to move 
these types out of the time_series/storage directory and into the 
range_run_storage subdirectory so they can be reused in other contexts.

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