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.

Definition at line 56 of file windowed_median.cpp.

Constructor & Destructor Documentation

WindowedMedian()

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

inlineexplicit

Constructs a WindowedMedian object.

Parameters

windowSize

Sliding window size

Definition at line 123 of file windowed_median.cpp.

: _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

Definition at line 95 of file windowed_median.cpp.

                                    {
        const auto sz = _sortedValues.size();
 
        if (value <= *_itMedian && sz % 2 == 0) {
            ++_itMedian;  
        }
 
        else if (value >= *_itMedian && sz % 2 != 0) {
            --_itMedian;  // O(1) - traversing one step to the left child
        }
 
        const auto it = _sortedValues.find(value);  // O(logN)
        _sortedValues.erase(it);                    // O(logN)
    }

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)

Definition at line 148 of file windowed_median.cpp.

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

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)

Definition at line 161 of file windowed_median.cpp.

                                 {
        auto window = _window;
        window.sort();  
        auto median =
            *next(window.begin(),
                  window.size() / 2);  
        if (window.size() % 2 != 0) {
            return median;
        }
        return 0.5f * median +
               0.5f * *next(window.begin(), window.size() / 2 - 1);  
    }

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)

Definition at line 129 of file windowed_median.cpp.

                           {
        _window.push_back(value);
        insertToSorted(value);  // Insert value to the multi-value BST - O(logN)
        if (_window.size() > _windowSize) {  
            eraseFromSorted(
                _window.front());  
            _window.pop_front();   
        }
    }

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

Definition at line 69 of file windowed_median.cpp.

                                   {
        _sortedValues.insert(value);  
        const auto sz = _sortedValues.size();
        if (sz == 1) {  
            _itMedian = _sortedValues.begin();
            return;
        }
 
        if (value < *_itMedian && sz % 2 == 0) {
            --_itMedian;  // O(1) - traversing one step to the left child
        }
 
        else if (value >= *_itMedian && sz % 2 != 0) {
            ++_itMedian;  
        }
    }

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

Definition at line 62 of file windowed_median.cpp.

_sortedValues

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

private

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

Definition at line 59 of file windowed_median.cpp.

_window

Window probability::windowed_median::WindowedMedian::_window

private

a sliding window of values along the stream

Definition at line 58 of file windowed_median.cpp.

_windowSize

const size_type probability::windowed_median::WindowedMedian::_windowSize

private

sliding window size

Definition at line 57 of file windowed_median.cpp.

---

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

• probability/windowed_median.cpp