qsort de FreeBSD y Linux ordenan distinto...!

Discussion:

(demasiado antiguo para responder)

Horacio Castellini

2005-12-09 14:08:17 UTC

Holas
Me está surgiendo un problema con la portabilidad del qsort, supongamos que
quiero ordenar un arreglo de estructuras...

struct mail{
char *autor;
char *tema;
};
.....
struct mail A[50];
......
entonces defino la siguiente función para la ordenación lexicográfica...

int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
return strcmp(r1.tema,r2.tema);
}

Ahora bien cuando aplico en una parte del código la ordenación del arreglo
de registros ...
qsort(Contener,cont,sizeof(struct mail),comp_tema);

en caso de empate... es decir que comp_tema devuelve cero, tenía el
prejuicio que ambas bibliotecas C ordenaban igual... pero no...

Es decir en linux sale...

a1 t1
a3 t1
a4 t1

en cambio en FreeBSD

a4 t1
a1 t1
a3 t1

Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...

Saludos Horacio...

Eduardo Villanueva

2005-12-09 22:04:48 UTC

Permalink

// no copies las estructuras
const struct mail *r1 = (const struct mail*)c1;
const struct mail *r2 = (const struct mail*)c2;
int ret;

if (!(ret=strcmp(r1->tema,r2->tema)))
ret = strcmp(r1->autor,r2->autor);

return ret;

Post by Horacio Castellini
}
Ahora bien cuando aplico en una parte del código la ordenación del arreglo
de registros ...
qsort(Contener,cont,sizeof(struct mail),comp_tema);
en caso de empate... es decir que comp_tema devuelve cero, tenía el
prejuicio que ambas bibliotecas C ordenaban igual... pero no...

No es problema de bibliotecas ni de plataformas, sino de tu función de
comparación. Según tu función 2 mails son iguales *SOLO* si tienen el
mismo tema, y el orden de los elementos iguales dependerá de la
implementación del algoritmo.

Vamos que si el algoritmo cree que 2 elementos son iguales pondrá
primero el que mejor le venga, ya que el orden entre esos elementos no
importa porque *TU* le has dicho que son iguales ;)

Post by Horacio Castellini
Es decir en linux sale...
a1 t1
a3 t1
a4 t1
en cambio en FreeBSD
a4 t1
a1 t1
a3 t1
Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...

Sólo estas comparando el campo tema. Deberías comparar también con autor
cuando los temas sean iguales.

Post by Horacio Castellini
Saludos Horacio...

Saludos ;)

Claudio

2005-12-10 10:55:50 UTC

Permalink

Post by Horacio Castellini
Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...

Las implementaciones de qsort en linux y bsd son libres así que puedes
copiar la función de una y llevártela a la otra, por ejemplo llamándola
qsort2.

Pero la solución más fácil y lógica parece que pasa porque refines la
función de manera que nunca dé = (que para tí no tiene utilidad, sino
que es un estorbo). Por ejemplo usa el autor, como te dicen en otro
post, y después usa el resto de campos, el tamaño,...

Un saludo.
--claudio--

Azdo

2005-12-10 12:24:00 UTC

Permalink

Post by Horacio Castellini
Holas
Me está surgiendo un problema con la portabilidad del qsort,
supongamos que
quiero ordenar un arreglo de estructuras...
struct mail{
char *autor;
char *tema;
};
.....
struct mail A[50];
......
entonces defino la siguiente función para la ordenación lexicográfica...
int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
return strcmp(r1.tema,r2.tema);
}
Ahora bien cuando aplico en una parte del código la ordenación del arreglo
de registros ...
qsort(Contener,cont,sizeof(struct mail),comp_tema);
en caso de empate... es decir que comp_tema devuelve cero, tenía el
prejuicio que ambas bibliotecas C ordenaban igual... pero no...
Es decir en linux sale...
a1 t1
a3 t1
a4 t1
en cambio en FreeBSD
a4 t1
a1 t1
a3 t1
Como el oreden es crítico en mi caso... que solución puedo implementar
para que esto no me suceda...
Saludos Horacio...

¡Pues discrimínalo! ;)

int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
int res;

r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
if((res=strcmp(r1.tema,r2.tema))==0)
return strcmp(r1.autor,r2.autor);
else return res;
}

Iñaki Arenaza

2005-12-09 16:49:06 UTC

Permalink

Horacio> Como el oreden es crítico en mi caso... que solución
Horacio> puedo implementar para que esto no me suceda...

Si son lexicograficamente iguales ¿cual es el orden "correcto"? Creo
que no existe una respuesta para ello.

Ahora bien, si el orden es critico para ti, usa algo extra (el otro
campos de la estructura, por ejemplo) para deshacer la ambiguedad.

Saludos. Iñaki.

- --
Get PGP/GPG Keys at http://www.escomposlinux.org/iarenaza/pgpkey.php
I use free software / Yo uso software libre

Oscar Garcia

2005-12-09 16:50:07 UTC

Permalink

El Fri, 09 Dec 2005 11:08:17 -0300, Horacio Castellini

Post by Horacio Castellini
Holas
Me está surgiendo un problema con la portabilidad del qsort, supongamos que
quiero ordenar un arreglo de estructuras...
en caso de empate... es decir que comp_tema devuelve cero, tenía el
prejuicio que ambas bibliotecas C ordenaban igual... pero no...
Es decir en linux sale...
a1 t1
a3 t1
a4 t1
en cambio en FreeBSD
a4 t1
a1 t1
a3 t1
Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...

El problema principal es como interpreta cada librería la igualdad.
Parece que Linux (como debe ser) en caso de igualdad de elementos no
los intercambia. Sin embargo parece que FreeBSD sí que hace ese
intercambio en caso de igualdad.

Una implementación en C podría ser:

void cambia (int *a, int *b) {
int t=*a;
*a=*b;
*b=t;
}

void __qsort (int arr[], int ini, int fin) {
if (fin > ini + 1) {
int piv = arr[ini], l = ini + 1, r = fin;
while (l < r) {
if (arr[l] <= piv) {
l++;
} else {
cambia (&arr[l], &arr[--r]);
}
}
cambia (&arr[--l], &arr[beg]);
__qsort (arr, ini, l);
__qsort (arr, r, fin);
}
}

Ese "if (arr[l] <= piv)" puede cambiarse por un "if (arr[l] < piv)"
sin que se modifique el resultado final (en cuanto al orden de
ordenación), pero hace que ciertos elementos del mismo valor quizá
sean comparados e intercambiados entre sí. Por supuesto esa
comparación realmente es el valor que devuelve la función que tú has
creado cuando se usa la función qsort de la librería de C.

Si de verdad deseas que el resultado sea exactamente igual te aconsejo
que ordenes por TODOS los campos de tu estructura sin dejarte ninguno
(a ser posible deja la clave primaria para el último lugar).

Es la única forma de garantizar la exactitud en la salida en cualquier
plataforma y usando cualquier método de ordenación.

Tú has puesto solo dos elementos en tu estructura, pero supongo que
tendrás aún más (no creo que se llame "mail" una estructura que no
contiene el correo electrónico de un autor :).

Tanto Azdo como Eduardo te han dado soluciones más prácticas. Yo te
agrego que compares todos y cada uno de los elementos de tu estructura
(por supuesto por prioridades: por ejemplo... primero nombre, luego
primer apellido, luego segundo apellido, etc).

Un saludo.

--
Óscar Javier García Baudet
LinaresDigital
http://redstar.linaresdigital.com/

Gonzalo Pérez de Olaguer Córdoba

2005-12-12 01:00:31 UTC

Permalink

esta función ordena por temas, ignorando autores

Post by Horacio Castellini
Ahora bien cuando aplico en una parte del código la ordenación del arreglo
de registros ...
qsort(Contener,cont,sizeof(struct mail),comp_tema);
en caso de empate... es decir que comp_tema devuelve cero, tenía el
prejuicio que ambas bibliotecas C ordenaban igual... pero no...
Es decir en linux sale...
a1 t1
a3 t1
a4 t1
en cambio en FreeBSD
a4 t1
a1 t1
a3 t1

ambos algoritmos están funcionando bien: les das tres elementos *iguales*
y te los devuelve *ordenados*

Post by Horacio Castellini
Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...

¿algo así tal vez?

int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
return strcmp(r1.tema,r2.tema) || strcmp(r1.autor,r2.autor);
}

si los temas son iguales, ordena por autor

--
Gonzalo Pérez de Olaguer Córdoba <***@iies.es>
PGP key 2861C704 --- F206 5671 6789 425D 111C 1302 214F 1934 2861 C704

Eduardo Villanueva

2005-12-13 02:31:09 UTC

Permalink

esta función ordena por temas, ignorando autores

ambos algoritmos están funcionando bien: les das tres elementos *iguales*
y te los devuelve *ordenados*

Post by Horacio Castellini
Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...

¿algo así tal vez?
int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
return strcmp(r1.tema,r2.tema) || strcmp(r1.autor,r2.autor);

Pues va a ser que no ;)

Una función de comparación debe devolver:

'Menor que 0' si c1 < c2
'0' si c1 == c2
'Mayor que 0' si c1 > c2

Aunque se considere el valor 0 como falso y cualquier otro valor como
verdadero, los operadores lógicos devuelven *SÓLO* 0 ó 1. En otras
palabaras: (-7 || X) == 1

Vamos, que con ese código devolverás '0' si son iguales y '1' (que será
interpretado como 'c1 mayor que c2') si son distintos.

Quim Testar

2005-12-13 23:44:09 UTC

Permalink

Post by Horacio Castellini
Holas
Me está surgiendo un problema con la portabilidad del qsort, supongamos que
quiero ordenar un arreglo de estructuras...
struct mail{
char *autor;
char *tema;
};
.....
struct mail A[50];
......
entonces defino la siguiente función para la ordenación lexicográfica...
int comp_tema(const void *c1,const void *c2)
{
struct mail r1,r2;
r1=*(struct mail*)c1;
r2=*(struct mail*)c2;
return strcmp(r1.tema,r2.tema);
}
Ahora bien cuando aplico en una parte del código la ordenación del arreglo
de registros ...
qsort(Contener,cont,sizeof(struct mail),comp_tema);
en caso de empate... es decir que comp_tema devuelve cero, tenía el
prejuicio que ambas bibliotecas C ordenaban igual... pero no...
Es decir en linux sale...
a1 t1
a3 t1
a4 t1
en cambio en FreeBSD
a4 t1
a1 t1
a3 t1
Como el oreden es crítico en mi caso... que solución puedo implementar para
que esto no me suceda...
Saludos Horacio...

Como dice la especificación:

"If two members compare as equal, their order in the sorted array is
unspecified."

O sea que, según entiendo yo, ni siquiera se te garantiza que de una
ejecución a otra en el mismo sistema te ordene idénticamente (que no
digo que no lo haga, ojo, sólo que no te lo garantizan).

Lo que yo haría sería incluir el autor en la comparación cuando el tema
sea igual y así seguro que te devuelve siempre lo mismo.

Quim Testar

2005-12-13 23:46:39 UTC

Permalink

En/na Quim Testar ha escrit:

Ui! con el follow-up no havia visto que estaba ya tan contestado el tema...