Re: [boost] [multi_index] Multi-Index as fast running median solver

Subject: Re: [boost] [multi_index] Multi-Index as fast running median solver
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2010-09-05 14:23:12

Ryan Fogarty <ryan.fogarty.msece <at> gmail.com> writes:

> 
> I'm hoping to use multi-index' ordered_index (non-unique) 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:
>
> [...]
> 
> 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 2-fold is there any way to force the internal red-black tree to
> stay balanced; and secondly, would that have an appreciable performance
> penalty.

Hi Ryan,

Excuse my very late answering, been on vacation the last two weeks.

ordered_index internal implementation relies on red-back trees,
which are not perfectly balanced but only roughly so (the longest
root-to-leaf path is at most twice as long as the shortest one).
I don't think it's easy to modify the handling code to improve
on that.

Joaquín M López Muñoz
Telefónica, Invewstigación y Desarrollo