probability::windowed_median::WindowedMedian Class Reference

A class to calculate the median of a leading sliding window at the back of a stream of integer values. More...

Collaboration diagram for probability::windowed_median::WindowedMedian:

Public Member Functions
	WindowedMedian (size_type windowSize)
	Constructs a WindowedMedian object.
void	insert (int value)
	Insert a new value to the stream.
float	getMedian () const
	Gets the median of the values in the sliding window.
float	getMedianNaive () const
	A naive and inefficient method to obtain the median of the sliding window. Used for testing!

Private Member Functions
void	insertToSorted (int value)
	Inserts a value to a sorted multi-value BST.
void	eraseFromSorted (int value)
	Erases a value from a sorted multi-value BST.

Private Attributes
const size_type	_windowSize
	sliding window size
Window	_window
	a sliding window of values along the stream
std::multiset< int >	_sortedValues
std::multiset< int >::const_iterator	_itMedian

Detailed Description

A class to calculate the median of a leading sliding window at the back of a stream of integer values.

Constructor & Destructor Documentation

WindowedMedian()

probability::windowed_median::WindowedMedian::WindowedMedian ( size_type windowSize )

inlineexplicit

Constructs a WindowedMedian object.

Parameters

windowSize

Sliding window size

: _windowSize(windowSize){};

Member Function Documentation

eraseFromSorted()

void probability::windowed_median::WindowedMedian::eraseFromSorted ( int value )

inlineprivate

Erases a value from a sorted multi-value BST.

Parameters

value

Value to insert

If the erased value is on the left branch or the median itself and the number of elements is even, the new median will be the right child of the current one

O(1) - traversing one step to the right child

However, if the erased value is on the right branch or the median itself, and the number of elements is odd, the new median will be the left child of the current one

Find the (first) position of the value we want to erase, and erase it

                                    {
        const auto sz = _sortedValues.size();
 
        /// If the erased value is on the left branch or the median itself and
        /// the number of elements is even, the new median will be the right
        /// child of the current one
        if (value <= *_itMedian && sz % 2 == 0) {
            ++_itMedian;  /// O(1) - traversing one step to the right child
        }
 
        /// However, if the erased value is on the right branch or the median
        /// itself, and the number of elements is odd, the new median will be
        /// the left child of the current one
        else if (value >= *_itMedian && sz % 2 != 0) {
            --_itMedian;  // O(1) - traversing one step to the left child
        }
 
        /// Find the (first) position of the value we want to erase, and erase
        /// it
        const auto it = _sortedValues.find(value);  // O(logN)
        _sortedValues.erase(it);                    // O(logN)
    }

Here is the call graph for this function:

getMedian()

float probability::windowed_median::WindowedMedian::getMedian ( ) const

inline

Gets the median of the values in the sliding window.

Returns

Median of sliding window. For even window size return the average between the two values in the middle

O(1)

                            {
        if (_sortedValues.size() % 2 != 0) {
            return *_itMedian;  // O(1)
        }
        return 0.5f * *_itMedian + 0.5f * *next(_itMedian);  /// O(1)
    }

Here is the call graph for this function:

getMedianNaive()

float probability::windowed_median::WindowedMedian::getMedianNaive ( ) const

inline

A naive and inefficient method to obtain the median of the sliding window. Used for testing!

Returns

Median of sliding window. For even window size return the average between the two values in the middle

Sort window - O(NlogN)

Find value in the middle - O(N)

O(N)

                                 {
        auto window = _window;
        window.sort();  /// Sort window - O(NlogN)
        auto median =
            *next(window.begin(),
                  window.size() / 2);  /// Find value in the middle - O(N)
        if (window.size() % 2 != 0) {
            return median;
        }
        return 0.5f * median +
               0.5f * *next(window.begin(), window.size() / 2 - 1);  /// O(N)
    }

Here is the call graph for this function:

insert()

void probability::windowed_median::WindowedMedian::insert ( int value )

inline

Insert a new value to the stream.

Parameters

value

New value to insert

Push new value to the back of the sliding window - O(1)

If exceeding size of window, pop from its left side

Erase from the multi-value BST the window left side value

Pop the left side value from the window - O(1)

                           {
        /// Push new value to the back of the sliding window - O(1)
        _window.push_back(value);
        insertToSorted(value);  // Insert value to the multi-value BST - O(logN)
        if (_window.size() > _windowSize) {  /// If exceeding size of window,
                                             /// pop from its left side
            eraseFromSorted(
                _window.front());  /// Erase from the multi-value BST
                                   /// the window left side value
            _window.pop_front();   /// Pop the left side value from the window -
                                   /// O(1)
        }
    }

Here is the call graph for this function:

insertToSorted()

void probability::windowed_median::WindowedMedian::insertToSorted ( int value )

inlineprivate

Inserts a value to a sorted multi-value BST.

Parameters

value

Value to insert

Insert value to BST - O(logN)

For the first value, set median iterator to BST root

If new value goes to left tree branch, and number of elements is even, the new median in the balanced tree is the left child of the median before the insertion

However, if the new value goes to the right branch, the previous median's right child is the new median in the balanced tree

O(1) - traversing one step to the right child

                                   {
        _sortedValues.insert(value);  /// Insert value to BST - O(logN)
        const auto sz = _sortedValues.size();
        if (sz == 1) {  /// For the first value, set median iterator to BST root
            _itMedian = _sortedValues.begin();
            return;
        }
 
        /// If new value goes to left tree branch, and number of elements is
        /// even, the new median in the balanced tree is the left child of the
        /// median before the insertion
        if (value < *_itMedian && sz % 2 == 0) {
            --_itMedian;  // O(1) - traversing one step to the left child
        }
 
        /// However, if the new value goes to the right branch, the previous
        /// median's right child is the new median in the balanced tree
        else if (value >= *_itMedian && sz % 2 != 0) {
            ++_itMedian;  /// O(1) - traversing one step to the right child
        }
    }

Here is the call graph for this function:

Member Data Documentation

_itMedian

std::multiset<int>::const_iterator probability::windowed_median::WindowedMedian::_itMedian

private

an iterator that points to the root of the multi-value BST

_sortedValues

std::multiset<int> probability::windowed_median::WindowedMedian::_sortedValues

private

a DS to represent a balanced multi-value binary search tree (BST)

---

The documentation for this class was generated from the following file:

• probability/windowed_median.cpp