Compile error qsort comparison
My medianfilter.cpp class calls qsort
like below.
vector<float> medianfilter::computeMedian(vector<float> v) {
float arr[100];
std::copy(v.begin(), v.end(), arr);
unsigned int i;
qsort(arr, v.size(), sizeof(float), compare);
for (i = 0; i < v.size(); i++) {
printf("%f ", arr[i]);
}
printf("median=%d ", arr[v.size() / 2]);
return v;
}
As a result of my comparison:
int medianfilter::compare(const void * a, const void * b) {
float fa = *(const float*) a;
float fb = *(const float*) b;
return (fa > fb) - (fa < fb);
}
while the declaration in mediafilter.hpp is set to private and looks like this:
int compare (const void*, const void*);
Compilation error occurs: cannot convert ‘mediafilter::compare’ from type ‘int (mediafilter::)(const void*, const void*)’ to type ‘__compar_fn_t {aka int (*)(const void*, const void*)}’
I don't understand this error. How do I properly declare and implement this comparison method? Thank!
source to share
Comparison is a non-static member function, whereas qsort expects a non-member (or static member) function. Since the compare function does not use any non-static class members, you can simply declare it static. I'm not really sure what your middle class filters are doing at all. Maybe you just need a namespace.
Why not sort the vector directly instead of copying it into a second array? Also, your code will be split if the vector contains more than 100 elements.
The default behavior is just what you want, but for the sake of completeness, I show you how to use the compare function.
I also changed the return type of your function because I don't understand why the function with the name computeMedian
will not return the median.
namespace medianfilter
{
bool compare(float fa, float fb)
{
return fa < fb;
}
float computeMedian(vector<float> v)
{
std::sort(v.begin(), v.end(), compare);
// or simply: std::sort(v.begin(), v.end());
for (size_t i = 0; i < v.size(); i++) {
printf("%f ", v[i]);
}
if (v.empty())
{
// what do you want to happen here?
}
else
{
float median = v[v.size() / 2]; // what should happen if size is odd?
printf("median=%f ", median); // it was %d before
return median;
}
}
}
source to share
You cannot invoke the comparison as it is a member function and requires a pointer this
(i.e. it needs to be called on an object). However, since your comparison function doesn't need a pointer this
, just make it a function static
and your code will compile.
Declare it in your class like this:
static int compare(const void * a, const void * b);
source to share
Not directly related to your question (for which you already have an answer), but some observations:
- Your median calculation is wrong. If the cardinality is equal, you should return the average of the two center values, not the value of the bottom.
- A copy of the array with the given size overflows the buffers. Copy to another vector and std: sort it, or (as suggested by @NeilKirk), just sort the original if you have no reason to change it.
- No protection against blank input. The median is undefined in this case, but your implementation will just return whatever happens on arr [0]
source to share
Ok, this is more of an appendix to Eli Algranti's (excellent) answer than an answer to the original question ... please don't reduce oblivion;)
Here is the generic code for calculating the quantile quant
of a double vector called x
(which is stored below in the code).
First of all: there are many definitions of quantiles (only R lists 9 ). The code below matches definition # 5 (which is also the default quantile function in matlab, and generally by statisticians when they think of quantile).
The basic idea here is that when the quantile does not hit the exact observation (for example, when you want to get 15% of the quantiles of an array of length 10), the implementation below implements (correct) interpolation (in this case between 10% and 20%) between adjacent quantile. This is important so that when you increase the number of observations (here I am hinting at the name medianfilter
here), the value of the quantile does not leap, but converges smoothly (which is one of the reasons why this is the preferred definition of statistics).
The code assumes it x
has at least one element (the code below is part of a longer one, and I feel like that point has already been made).
Unfortunately, it is written using many functions from (excellent!) C ++ native library, and it is too late for me at this advanced time at night to translate native functions - or misinform variable names - but the key ideas should be readable.
#include <Eigen/Dense>
#include <Eigen/QR>
using namespace std;
using namespace Eigen;
using Eigen::MatrixXd;
using Eigen::VectorXd;
using Eigen::VectorXi;
double quantiles(const Ref<const VectorXd>& x,const double quant){
//computes the quantile 'quant' of x.
const int n=x.size();
double lq,uq,fq;
const double q1=n*(double)quant+0.5;
const int index1=floor(q1);
const int index2=ceil(q1);
const double index3=(double)index2-q1;
VectorXd x1=x;
std::nth_element(x1.data(),x1.data()+index1-1,x1.data()+x1.size());
lq=x1(index1-1);
if(index1==index2){
fq=lq;
} else {
uq=x1.segment(index1,x1.size()-index1-1).minCoeff();
fq=lq*index3+uq*(1.0-index3);
}
return(fq);
}
So the code uses one call to nth_element, which has an average complexity of O (n) [sorry for sloppely using big O for medium] and (when n is even) one extra call to min () [which is marked in its own dialect .minCoeff()
] at most by n / 2 elements of the vector, which is O (n / 2).
This is much better than using partial sort (which will cost O (nlog (n / 2)), worst case ) or sort (which will cost O (nlogn) )
source to share