
Boost Users : 
Subject: Re: [Boostusers] multiindex:Q  Space and time efficiency
From: joaquin_at_[hidden]
Date: 20090327 03:31:44
dhruva escribió:
> Hi,
> I have a struct with 2 members as follows:
>
> typedef struct time_series {
> time_t _time;
> double _value;
> } time_series_t;
>
> The data I get is sorted by time as it is a time series. I would like to maintain another index sorted by value. Since I need to keep removing the oldest records, I need the time based order and since I need to compute percentile, I need to sort it based on value. Would using multiindex save space (and time in insertion and removal) compared to having 2 vectors with different sort order?
>
The space taken per element by the Boost.MultiIndexbased solution
would be:
6p+sizeof(time_series_t)
where p is the size of a pointer, 4 bytes in a typical 32bit architecture.
(See http://www.boost.org/libs/multi_index/doc/performance.html for
details.)
As for having two vectors, one with the time_series_t objects
themselves, the
second with pointers to the elements of the first one, the space per
element is
c(p+sizeof(time_series_t))
where c is the capacity() to size() ratio for the vectors, which
oscillates (unless
explicitly controlled by the user) between 1 and some libspecific upper
bound (2 or 1.5 in most cases). So, if we have for instance
p=4, sizeof(time_series_t)=16, c=1.25
that would yield 40 bytes per element for scenario 1 and 25 bytes per
element
for scenario 2. Your mileage may vary depending on your particular
environment.
As for speed, this much depends on your usage patterns: how often you
sort the vectors, prune them, etc. In particular, take into account that
removing elements from a position in a vector other than the tail is
expensive, which might lead you to use (the more spaceconsuming)
std::queues instead. I guess your best option is to prototype both scenarios
and profile them.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net