The median is defined as the middle value of an array of sorted values. The two main advantages of using the median above an average is that it is not influenced by a single outlier and it allways represent a real measurement. On the other hand by averaging one could create extra precision. As all things in the world this library is eternally under construction
Please post comments and improvements in this thread,
It's very unlikely the size, count, and index need to be a full integer. An 8-bit data-type is more appropriate. You may have to continue using a signed data-type.
Given the fact that _size is a fixed size, it should be turned into a static const.
I don't think it's necessary to perform a complete sort. I believe a heap would get the result you want.
I believe 5 is a very good choice for _size. Given the fact that _size is fixed at 5, you may want to "unroll" the loops. I suspect the total code size will be reduced and the execution time will obviously improve.
This is a great benefit by dealing with sensor data. Especially due to the fact that the median is really robust against outlier!
How can I move the hardcoded 5 items value for computing the median from RunningMedian.h file to the scetch? Im am unfamiliar with modifying or overrice values from a library, so be patient with me. I can change the line "#define MEDIAN_SIZE 5" to "#define MEDIAN_SIZE 11" but it would be more convenient to do this not in the library directly but in the sketch. Can I use
It would be great if I can not set MEDIAN_SIZE globally--for all calculated median the same array lenght--but also different MEDIAN_SIZE if I deal with different and more than one sensor input.
Thanks for your interest, The median is indeed robust against outliers, and you can still do a running average to smooth the values additionally.
The advantage of the #define construct is that the intenal data structure is allocated compile time. If you use a parameter you want to allocate this runtime. Or allocate a fixed - and too large - array compile time and use only a part of it. Something like this:
Arduino and dynamic memory are not the bests friend imho (it works with a but or 2) Unfortunately I'm quite busy at the moment to write (and test) a parameterized version of the lib....
I did a new implementation using the same ideas, less features but with improved performance.
//
// Released to the public domain
//
// Remarks:
// This is a lean but fast version.
// Initially, the buffer is filled with a "default_value". To get real median values
// you have to fill the object with N values, where N is the size of the sliding window.
// For example: for(int i=0; i < 32; i++) myMedian.addValue(readSensor());
//
// Constructor:
// FastRunningMedian<datatype_of_content, size_of_sliding_window, default_value>
// maximim size_of_sliding_window is 255
// Methods:
// addValue(val) adds a new value to the buffers (and kicks the oldest)
// getMedian() returns the current median value
//
//
// Usage:
// #include "FastRunningMedian.h"
// FastRunningMedian<unsigned int,32, 0> myMedian;
// ....
// myMedian.addValue(value); // adds a value
// m = myMedian.getMedian(); // retieves the median
//
#include <inttypes.h>
template <typename T, uint8_t N, T default_value> class FastRunningMedian {
public:
FastRunningMedian() {
_buffer_ptr = N;
_window_size = N;
_median_ptr = N/2;
// Init buffers
uint8_t i = _window_size;
while( i > 0 ) {
i--;
_inbuffer[i] = default_value;
_sortbuffer[i] = default_value;
}
};
T getMedian() {
// buffers are always sorted.
return _sortbuffer[_median_ptr];
}
void addValue(T new_value) {
// comparision with 0 is fast, so we decrement _buffer_ptr
if (_buffer_ptr == 0)
_buffer_ptr = _window_size;
_buffer_ptr--;
T old_value = _inbuffer[_buffer_ptr]; // retrieve the old value to be replaced
if (new_value == old_value) // if the value is unchanged, do nothing
return;
_inbuffer[_buffer_ptr] = new_value; // fill the new value in the cyclic buffer
// search the old_value in the sorted buffer
uint8_t i = _window_size;
while(i > 0) {
i--;
if (old_value == _sortbuffer[i])
break;
}
// i is the index of the old_value in the sorted buffer
_sortbuffer[i] = new_value; // replace the value
// the sortbuffer is always sorted, except the [i]-element..
if (new_value > old_value) {
// if the new value is bigger than the old one, make a bubble sort upwards
for(uint8_t p=i, q=i+1; q < _window_size; p++, q++) {
// bubble sort step
if (_sortbuffer[p] > _sortbuffer[q]) {
T tmp = _sortbuffer[p];
_sortbuffer[p] = _sortbuffer[q];
_sortbuffer[q] = tmp;
} else {
// done ! - found the right place
return;
}
}
} else {
// else new_value is smaller than the old one, bubble downwards
for(int p=i-1, q=i; q > 0; p--, q--) {
if (_sortbuffer[p] > _sortbuffer[q]) {
T tmp = _sortbuffer[p];
_sortbuffer[p] = _sortbuffer[q];
_sortbuffer[q] = tmp;
} else {
// done !
return;
}
}
}
}
private:
// Pointer to the last added element in _inbuffer
uint8_t _buffer_ptr;
// sliding window size
uint8_t _window_size;
// position of the median value in _sortbuffer
uint8_t _median_ptr;
// cyclic buffer for incoming values
T _inbuffer[N];
// sorted buffer
T _sortbuffer[N];
};
#endif
// --- END OF FILE ---
test code:
#include "FastRunningMedian.h"
#include "RunningMedianStatic.h"
unsigned int value = 0;
FastRunningMedian<unsigned int,32, 0> newMedian;
RunningMedianStatic staticMedian = RunningMedianStatic(32);
void setup ()
{
while (!Serial) ;
Serial.begin(9600);
Serial.println("Starting....");
};
void loop()
{
unsigned int xmedian;
unsigned int cmedian;
// us measurement overhead is 4 us.
value = random(0, 255);
unsigned long loopstart = micros();
newMedian.addValue(value);
xmedian = newMedian.getMedian();
unsigned long loopstop = micros();
unsigned long fastdelay = loopstop - loopstart;
loopstart = micros();
staticMedian.add(value);
cmedian = staticMedian.getMedian();
loopstop = micros();
unsigned long slowdelay = loopstop - loopstart;
Serial.print("Loop FastTime(us)=");
Serial.print(fastdelay);
Serial.print(" SlowTime(us)=");
Serial.print(slowdelay);
Serial.print(" value=");
Serial.print(value);
Serial.print(" median=");
Serial.print(xmedian);
Serial.print(" excactmedian=");
Serial.print(cmedian);
Serial.println();
delay(500);
};
for the first n rounds the result values are incorrect, but afterwards they are identical. Your code takes around 1170us, mine below 100us in most cases. Your timing is more stable
Size of code is almost identical, my code a tiny bit smaller. I am not sure if this depends on the data type.
Static memory and stack usage is also more or less the same.
Your add-method is fast, the median calculation is slow.
My add-method does the whole work, my median returning is fast.
If you add a lot of values and retrieve the median only seldom there is maybe a speed advantage with your method.
the point is, that your algorithm takes O(n²) with full filled buffer (for add(); getMedian()), if i understand it right. My algorithm needs O(n) (ahem, anything between O(1) and O(2*n) in comparison)
for smaller buffers the difference is academic, but for my project I use several instances with n=33, where taking more than 1ms per median puzzled me a little bit :-))
I was looking for a way to average degrees for a project I'm working on and didn't want to use vector addition. So, I've implemented a median function in the RunningMedian library for compass readings to compensate for hassles of degree wraps at 359-0. This is based a previous version, not the current version of the library. Feel free to incorporate it into your library for others to use, if you wish.
/* function by WethaGuy to allow determination of median of a set of degrees, accounting for the 359-0 wrap */
int RunningMedian::getMedianDegrees()
{
if (_cnt > 0){
int index = 0;
sort();
/*check for valid compass value 0-359*/
if (_as[_cnt-1] > 359 || _as[0] < 0){return NAN;}
/*check 359-0 wrap*/
if (_as[_cnt-1]-_as[0] > 180){
/*find the index value of wrap*/
while(_as[index+1]-_as[index] < 180){
index++;
}
/* index value is less than the center of the list, the median is the sum of the index and the center of the list plus one (to account for odd number total list size) */
if (index < (_cnt/2)){
return _as[(_cnt/2) + index +1];
/*index value is not less than center of list, the median is the difference between center of the list and the index */
}else{
return _as[index -(_cnt/2)];
}
}
/* no 360-0 wrapping needed */
return _as[_cnt/2];
}
return NAN;
}