Rolling median function (Daily Coding Problem 377)

Question

Given an array of numbers arr and a window of size k, print out the median of each window of size k starting from the left and moving right by one position each time.

For example, given the following array and k = 3:

[-1, 5, 13, 8, 2, 3, 3, 1]

Your function should print out the following:

5 <- median of [-1, 5, 13]
8 <- median of [5, 13, 8]
8 <- median of [13, 8, 2]
3 <- median of [8, 2, 3]
3 <- median of [2, 3, 3]
3 <- median of [3, 3, 1]

Recall that the median of an even-sized list is the average of the two middle numbers.

Is there any improvement possible in this implementation?

    #include <iostream>
    #include <vector>
    #include <array>
    #include <algorithm>

    template <typename T>
    struct range
    {
        auto begin()const {return  a; }
        auto end()const {return b;}

        T a,b;
    };

    range<const int*>make_range(const int* begin, const int* end)
    {
        return {begin, end};
    }

    range<const int *> make_window(const std::vector<int>& vec, size_t start, size_t end)
    {
        return make_range(vec.data() + start, vec.data() + end);
    }

    int median(int arr[], size_t N)
    {
        //sort the array
        std::sort(arr, arr + N);
        if(N % 2 == 0)
            return (arr[N/2 - 1] + arr[N/2])/2;
        return arr[N/2];
    }

     int main(){
        const auto window_length = 3;
        std::vector<int> input{-1, 5, 13, 8, 2, 3, 3, 1};
        const auto end_length = input.size() - window_length;
        std::array<int, window_length> arr{};


    for(size_t i(0); i < end_length; i++)
    {
        int counter (0);
        const auto window = make_window(input, i, i + window_length);
        for(const auto& value : window)
        {
            std::cout << value << ' ';
            arr[counter++] = value;
        }
        int result = median(arr.data(), arr.size());
        counter = 0;
        std::cout << "\nmedian " << result << '\n';
        std::cout << '\n';
    }

    return EXIT_SUCCESS; 
   }

Answer 1

This compiles cleanly and produces reasonable integer output (though not in the format required by the problem statement).

Note that you are required to include <cstdlib> before using EXIT_SUCCESS; failing to do so may be a portability bug.

All that copying and sorting gets expensive as the input and k both get larger. We should probably create a stateful class that we can update with the new right-most value and the left-most to be removed. I'd probably implement that with two sets - one holding values lower than the median and one holding higher values. When we shift the window by one position, then we update the two sets and move an element if necessary to balance them (remember that because a set is sorted, it's easy to find the lowest and highest values using front() and back()).

Answer 2

My main issue is that the median function takes a C-style array. Generally C-style arrays are avoided in modern C++. It would be much better if it took an std::array, set or vector as its input.

Similarly, your make window function seems mostly unnecessary. It should only take one or two lines to get the window from the array.

In general there is very rarely a good reason to use use the data() functions on on STL containers; you should just use the container instead.

Other minor points:

There is some inconsistent formatting in number of spaces and {} positioning. Not a major issue but make things harder to read.

main() doesn't strictly need a return statement and will return 0 by default if no value is given.

You've included <algorithm> but haven't used anything from it.

Given these changes, my version looks like:

#include <array>
#include <iostream>
#include <vector>

int median( const std::vector< int >& window )
{
    const size_t N = window.size();
    if ( N % 2 == 0 )
        return ( window[N / 2 - 1] + window[N / 2] ) / 2;
    return window[N / 2];
}

int main()
{
    const auto window_length = 3;
    std::vector< int > input{ -1, 5, 13, 8, 2, 3, 3, 1 };

    for ( auto it = input.begin(); it != input.end()-window_length+1; ++it )
    {
        std::vector< int > window( it, it + window_length );

        for ( const auto& value : window )
        {
            std::cout << value << ' ';
        }

        std::sort( window.begin(), window.end() );
        int result = median( window );
        std::cout << "\nmedian " << result << '\n';
        std::cout << '\n';
    }
}

Another issue I haven't considered. If you take the median of 3, 4 I would expect 3.5, but your code does integer division and returns an int from median(), so will return 3. Not clear whether this is intentional or an oversight.