P: n/a

Hi everybody,
suppose you have to order a list of integers which refer to points
located in the 3D space. The compare() function is based on the
distance that these points have with respect to the origin (0,0,0). So,
using the standart qsort() function, I think this task should be
accomplished as follows:
qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function);
where
static int compare_function(void *b0, const void *b1)
{
double eps = 1e6;
int pnt0 = *((int *)b0);
int pnt1 = *((int *)b1);
double d0 = get_distance(pnt0);
double d1 = get_distance(pnt1);
double dd = d0  d1;
if(dd > eps)
return 1;
else if (dd < eps)
return 1;
else
return 0.;
}
The question is: why two different qsort() implementations (AIX and
Linux) should give different results? In particular, the Linux
implementation seems to fail to to find the right order. Any hint?
Thanks
Max  
Share this Question
P: n/a

"Max" <ip*******@gmail.com> writes: suppose you have to order a list of integers which refer to points located in the 3D space. The compare() function is based on the distance that these points have with respect to the origin (0,0,0). So, using the standart qsort() function, I think this task should be accomplished as follows:
qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function);
If you have a visible prototype for qsort(), the cast is unnecessary.
where
static int compare_function(void *b0, const void *b1) { double eps = 1e6;
int pnt0 = *((int *)b0); int pnt1 = *((int *)b1);
double d0 = get_distance(pnt0); double d1 = get_distance(pnt1);
double dd = d0  d1;
if(dd > eps) return 1; else if (dd < eps) return 1; else return 0.;
}
The question is: why two different qsort() implementations (AIX and Linux) should give different results? In particular, the Linux implementation seems to fail to to find the right order. Any hint?
The comparison function has to be consistent. You're returning 0 for
points that are very close to each other but not actually equal.
For example, given:
x = 1.0e6
y = 1.6e6
z = 2.2e6
you would report x == y, y == z, but x < z, which causes undefined
behavior in qsort().
I suggest dropping eps and just doing a comparison:
if (d0 < d1)
return 1;
else if (d0 == d1)
return 0;
else
return 1;
Some other oddities:
Both parameters of compare_function should be const.
"return 0.;" should be "return 0;". You're returning a floatingpoint
zero, which will be converted to int, so it has the same effect, but
it's cleaner just to return an int.

Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.  
P: n/a

On Wed, 28 Jun 2006 00:13:47 0700, Max wrote: Hi everybody,
suppose you have to order a list of integers which refer to points located in the 3D space. The compare() function is based on the distance that these points have with respect to the origin (0,0,0). So, using the standart qsort() function, I think this task should be accomplished as follows:
qsort(int_vector, (size_t)no_of_points, sizeof(int), compare_function);
where
static int compare_function(void *b0, const void *b1) { double eps = 1e6;
int pnt0 = *((int *)b0); int pnt1 = *((int *)b1);
double d0 = get_distance(pnt0); double d1 = get_distance(pnt1);
double dd = d0  d1;
if(dd > eps) return 1; else if (dd < eps) return 1; else return 0.;
}
The question is: why two different qsort() implementations (AIX and Linux) should give different results? In particular, the Linux implementation seems to fail to to find the right order. Any hint? Thanks Max
I'm not sure if this is specified for qsort but I've learnt not to use
it unless the compare function really is an order, ie unless the compare
function only returns 0 if the two arguments are identical. Otherwise, in
may experience at least, qsort can fail spectacularly (cause a core dump),
and anyway I'd suspect that if it returns the final order of the array,
(ie the order of the elements that are all equal as fare as the compare is
concerned) is not just implementation but phaseofthemoon dependent if
the compare can return non zero for two different arguments
Could you perhaps extend your comparison, function, eg if two points
are the same distance from the origin, compare x then y
then z coordinates too?
Duncan  
P: n/a

Duncan Muirhead schrieb: I'm not sure if this is specified for qsort but I've learnt not to use it unless the compare function really is an order, ie unless the compare function only returns 0 if the two arguments are identical.
You are right, but how to accomplish with that if you are dealing with
doubles? Such a routine is expected to order points belonging to two
different surfaces which are related by a geometrical transformation
(translation or rotation). Ordering them according to the distance from
the origin should store the pairs in sequence and make simple to split
the resulting ordered list in two vector. If you know other (cheap?)
algorithms, I will try them...
Otherwise, in may experience at least, qsort can fail spectacularly (cause a core dump), and anyway I'd suspect that if it returns the final order of the array, (ie the order of the elements that are all equal as fare as the compare is concerned) is not just implementation but phaseofthemoon dependent if the compare can return non zero for two different arguments Could you perhaps extend your comparison, function, eg if two points are the same distance from the origin, compare x then y then z coordinates too? Duncan
You are right and it is what the real code does. I gave an simpler
example (already tried) to focus on the topic.
Thanks
Max  
P: n/a

Max wrote: Duncan Muirhead schrieb:
I'm not sure if this is specified for qsort but I've learnt not to use it unless the compare function really is an order, ie unless the compare function only returns 0 if the two arguments are identical. You are right, but how to accomplish with that if you are dealing with doubles?
If you know other (cheap?) algorithms, I will try them...
Get rid of your epsilon and difference equations.
You don't want to equate near values
in an ordering function.
That's a bad thing to do.
If one number is just a smidgeon less than another,
then what's your objection to ordering it first?
static int compare_function(const void *b0, const void *b1)
{
int pnt0 = *((int *)b0);
int pnt1 = *((int *)b1);
double d0 = get_distance(pnt0);
double d1 = get_distance(pnt1);
return d1 > d0 ? 1 : d0 > d1;
}

pete  
P: n/a

Max wrote: [...] You are right and it is what the real code does. I gave an simpler example (already tried) to focus on the topic.
The simpler version has a bug, as has already been
explained. Now: Is that bug an artifact of the simplification
process, or is it also present in the original? Oh, drat: my
Ouija board is in the shop getting its phlogiston generator
repaired ...

Eric Sosman es*****@acmdotorg.invalid  
P: n/a

> [...] The simpler version has a bug, as has already been explained. Now: Is that bug an artifact of the simplification process, or is it also present in the original?
If you refer to the undefined behaviour, yes, I have tried to test the
code dropping out eps. I have got a different point list but it is
still wrong. As I have already explained above, I have the possibility
to visually check if the point list is correct or not.
The line
return 0.;
was just a typing error here.
Bye
Max  
P: n/a

"Max" <ip*******@gmail.com> writes: [...] The simpler version has a bug, as has already been explained. Now: Is that bug an artifact of the simplification process, or is it also present in the original?
If you refer to the undefined behaviour, yes, I have tried to test the code dropping out eps. I have got a different point list but it is still wrong. As I have already explained above, I have the possibility to visually check if the point list is correct or not.
How is it "wrong"? Are you sure your get_distance function is
correct? Do the points that are misordered have nearly identical
distances? Are you sure you're invoking qsort() correctly?
We can only point out flaws in code that you post. If you show us an
actual program that exhibits the problem, we can help. If not, we
can't guess.

Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.  
P: n/a
 How is it "wrong"? Are you sure your get_distance function is correct? Do the points that are misordered have nearly identical distances? Are you sure you're invoking qsort() correctly?
Yes, the functions works correctly and they have been tested
extensively. The qsort() call is not an issue. We can only point out flaws in code that you post. If you show us an actual program that exhibits the problem, we can help. If not, we can't guess.
I know what you mean, and you are right. Unfortunately the code is not
free and I am not allowed to distribute it...
Anyway, I will investigate better the "undefined behaviour" tip, since
this should be the problem. Up to now the algorithm has been used with
small lists and its application to larger vectors may results in such a
strange behaviour.
Thanks
Max  Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst> San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst> We must do something. This is something. Therefore, we must do this.   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1993
 replies: 8
 date asked: Jun 28 '06
