
Boost : 
Subject: [boost] [multi_index] MultiIndex as fast running median solver
From: Ryan Fogarty (ryan.fogarty.msece_at_[hidden])
Date: 20100816 12:38:45
I'm hoping to use multiindex' ordered_index (nonunique) to do a fast
running median. Given a set of M numbers and a window size of N compute the
medians (for each of M  N + 1 solutions). Here is my solution:
template<typename T>
class FastMedianSolver {
private:
// boost::multi_index does most of the heavy lifting for this
FastMedianSolver.
// This index is given both "sequence" and "tree" semantics.
typedef typename boost::multi_index_container<
T,indexed_by<sequenced<>,ordered_non_unique<identity<T> > > > SortedList;
typedef typename SortedList::template nth_index<0> SeqIndex;
typedef typename SeqIndex::type SIndex;
typedef typename SortedList::template nth_index<1> TreeIndex;
typedef typename TreeIndex::type TIndex;
SortedList mQueue;
const size_t mSize;
const size_t mHalfSize;
public:
typedef typename SIndex::iterator iterator;
/**
* Create a FastMedianSolver with queue size as argument
*
* @param size  size of the queue.
*/
// Note: fast divide by 2 is: X >> 1
FastMedianSolver(size_t size) : mSize(size), mHalfSize(size >> 1) {}
/**
* insert a value into the median queue
*/
void insert(const T& value) {
mQueue.push_front(value);
if(mQueue.size() > mSize) mQueue.pop_back();
}
/**
* Get the median for the elements within the queue. Note:
* the algorithm requires a full queue, o.w. may throw an exception.
*/
const T& getMedian() {
// Ensure queue is filled up before we ask for median!
assert((mQueue.size() >> 1) == mHalfSize);
typename TIndex::iterator tNdx(mQueue.get<1>().begin());
// Now grab the median element
// Note that unfortunately the root() node is not exposed so the
only way to get the central node
// is to iterate to it :( (this will incur a O(N) operation on this
function which is a little unfortunate
for(int i = 0; i < mHalfSize; ++i,++tNdx);
// This would be better if it were available and accurate!
// typename TIndex::iterator tNdx(mQueue.get<1>().beginAtRoot());
// TODO: Check if we need to average the output of 2 positions if
mSize is even
return *tNdx;
}
};
Note, that to get to the central node I just iterate the ordered list half
way through set:
for(int i = 0; i < mHalfSize; ++i,++tNdx);
However, what I was hoping was that I could get the root node directly.
ordered_index doesn't expose an iterator to root() so I put it in
ordered_index.hpp as:
iterator beginAtRoot(){return make_iterator(root());}
However, this isn't working out because the tree isn't always balanced. My
question is 2fold is there any way to force the internal redblack tree to
stay balanced; and secondly, would that have an appreciable performance
penalty.
Thank you,
Ryan
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk