sarnold / medians-1d Goto Github PK

Who the heck wrote this thing anyway? Oh, right, I did...

This isn't an "issue", but an "enhancement" that others may find useful. First off, let me express my thanks for your collection of median algorithms. I was in need of a good median algorithm that was non-destructive without requiring a second copy of the data and that didn't require dynamic memory allocation and yet was decently fast for use in an embedded application with limited computing resources. The Torben algorithm you have featured here almost fit the bill.

Where the Torben algorithm, as presented, fell short was for even-sized datasets, where I needed it to be the true median between the center two elements, not a lower median. The fast median search blog mentions this, but says that in order to obtain the true median, the routine must be called twice, doubling the processing time. But at least for the Torben algorithm, this isn't true.

To get the true NIST median, simply change the exit return code from this:

    if (less >= half) return maxltguess;
    else if (less+equal >= half) return guess;
    else return mingtguess;

To this:

	if (less >= half) min = maxltguess;
	else if (less+equal >= half) min = guess;
	else min = mingtguess;
	if (n&1) return min;		// if n is odd, we are done
	if (greater >= half) max = mingtguess;
	else if (greater+equal >= half) max = guess;
	else max = maxltguess;
	return (min+max)/2;

This simply takes the upper median value, which it actually found in the search as well, and averages it with the lower median value that it was previously returning. The short-circuit check for an odd-n is optional and very slightly reduces execution time for the odd case, depending on the compiler and processor.

I don't know if this can be easily applied to the other algorithms or not. And I didn't submit this as a pull request because your repository was more of a comparison between the algorithms than a specific implementation for a single algorithm. But, I thought this should be mentioned somewhere along with the algorithm for others to reference.

Can we use just a python test driver here? Should demo.c include a test/compare option?

Pretty much what it says, as python funcs are not quite in sync yet anyway.

Decide which demo functions to include in shared lib and python interface and refactor as needed. Update doxy tags and config file.