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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk