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; 
 }

• vnp: Formatting seems a bit off.
• Damien: Are you considering efficiency when you wrote "improvement". If yes, what are the maximum values of N and k ?
• Furch Radeon: @Damien as u can see from statement " Given an array of numbers arr and a window of size k " , it can be change anytime, dynamic.

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()).

• Furch Radeon: One more idea. Thank you. :)
• ALX23z: You misread the question. He needs not (lowest + highest)/2 but median value. The problem is that std::set doesn't allow one to get median element quickly. For this you'd need some custom set class or use a custom algorithm with std::vector as base.
• Toby Speight: No, I didn't misread the question, but perhaps I failed to explain my thinking clearly enough. We store two (multi-)sets, lower containing those values that are less than the median, and higher containing those greater than the median. When we add a new value and remove an old one, we add/remove from lower and/or higher as appropriate, and if necessary move an element from lower.back() to higher, or from higher.front() to lower. Then the new median can be computed from lower.back() and higher.front() (or just one of them for an odd-size window).

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.

• Furch Radeon: Thank you for you ideas. Yes, intentional to use int. Yes, i tried using std::array, but was little bit confused, how use in median. But now is more clear.
• L. F.: sort should probably be called inside median, because it is a step of calculating the median (there are more efficient ways, of course). So let median take the vector by value and move the window into it.