Ordenar en JavaScript: ¿Cada función de comparación debería tener una declaración de "retorno 0"?
Recientemente leí muchas respuestas sobre la clasificación en JavaScript y a menudo me topo con una función de comparación que se parece a esta:
array.sort(function(a,b){ a > b ? 1 : -1; });
Entonces es una función de comparación que devuelve 1 si aes mayor que by -1 si aes menor que O IGUAL bA. Como se describe en MDN ( enlace ), una función de comparación también puede devolver cero, para garantizar que la posición relativa de dos elementos permanezca sin cambios:
Si compareFunction(a, b) devuelve 0, deje a y b sin cambios entre sí, pero ordenados con respecto a todos los elementos diferentes.
Entonces los ejemplos oficiales se parecen más a esto:
function compare(a, b) {
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
Y, de hecho, al agregar una return 0declaración, el algoritmo de clasificación a menudo necesita menos iteraciones y se ejecuta más rápido en total ( JSPerf ).
Entonces me preguntaba si hay alguna ventaja en omitir una return 0declaración.
Me di cuenta de que en MDN también dice:
Nota: el estándar ECMAscript no garantiza este comportamiento y, por lo tanto, no todos los navegadores (por ejemplo, las versiones de Mozilla que se remontan al menos a 2003) lo respetan.
refiriéndose al comportamiento, eso ay bdebe permanecer sin cambios si se devuelve 0. Entonces, ¿tal vez, al devolver 0, obtenemos una matriz ordenada ligeramente diferente en diferentes navegadores? ¿Podría ser esa una razón? ¿Y hay otras buenas razones para no devolver cero?
Entonces me preguntaba si hay alguna ventaja al omitir una declaración de retorno 0.
Menos letras para escribir. Y podría ser un poquito más rápido debido a la comparación omitida. Todos los demás efectos son desventajas .
Me di cuenta de que en MDN también dice:
Nota: el estándar ECMAscript no garantiza este comportamiento y, por lo tanto, no todos los navegadores (por ejemplo, las versiones de Mozilla que se remontan al menos a 2003) lo respetan.
refiriéndose al comportamiento, que a y b deben permanecer sin cambios si se devuelve 0.
Que la posición de ay bpueda permanecer sin cambios es sólo el requisito para una especie estable . Este no es un comportamiento específico y algunos navegadores han implementado un algoritmo de clasificación no estable.
Sin embargo, el propósito real de devolver cero es que ninguno ase ordene antes b(como si fuera menor que 0) ni eso bse ordene antes a(como si fuera mayor que 0), básicamente cuando aes igual b. Esto es imprescindible para una comparación y todos los algoritmos de clasificación lo obedecen.
Para producir un orden válido y satisfactorio (matemáticamente: dividir los elementos en clases de equivalencia totalmente ordenadas ), una comparación debe tener ciertas propiedades. Se enumeran en la especificaciónsort como requisitos para una " función de comparación consistente ".
El más destacado es la reflexividad, que exige que un elemento asea igual a a(sí mismo). Otra forma de decir esto es:
compare(a, a)siempre debe regresar0
¿Qué sucede cuando una función de comparación no satisface esto (como obviamente lo hace la que encontró)?
La especificación dice
Si
comparefn[…] no es una función de comparación consistente para los elementos de esta matriz, el comportamiento desortestá definido por la implementación.
lo que básicamente significa: si proporciona una función de comparación no válida, la matriz probablemente no se ordenará correctamente. Es posible que se permute aleatoriamente o que la sortllamada ni siquiera finalice.
Entonces, ¿tal vez, al devolver 0, obtenemos una matriz ordenada ligeramente diferente en diferentes navegadores? ¿Podría ser esa una razón?
No, al devolver 0 obtienes una matriz ordenada correctamente en todos los navegadores (que puede ser diferente debido a la clasificación inestable). La razón es que al no devolver 0 se obtienen matrices permutadas ligeramente diferentes (si es que se obtienen), tal vez incluso produciendo el resultado esperado, pero generalmente de una manera más complicada.
Entonces, ¿qué podría pasar si no devuelve 0 por artículos equivalentes? Algunas implementaciones no tienen problemas con esto, ya que nunca comparan un elemento consigo mismo (incluso si es evidente en múltiples posiciones en la matriz); se puede optimizar esto y omitir la costosa llamada a la función de comparación cuando ya se sabe que el resultado debe ser 0.
El otro extremo sería un bucle sin fin. Suponiendo que tuviera dos elementos equivalentes uno detrás del otro, compararía el último con el primero y se daría cuenta de que tuvo que intercambiarlos. Probando nuevamente, este último aún sería más pequeño que el primero y tendrías que cambiarlos nuevamente. Etcétera…
Sin embargo, un algoritmo eficiente en la mayoría de los casos no vuelve a probar elementos ya comparados , por lo que normalmente la implementación finalizará. Aún así, podría realizar más o menos intercambios que en realidad eran innecesarios y, por lo tanto, llevará más tiempo que con una función de comparación consistente.
¿Y hay otras buenas razones para no devolver cero?
Ser vago y esperar que la matriz no contenga duplicados.
Un método de comparación debe obedecer al contrato.
Math.sign(compare(a, b)) = -Math.sign(compare(b, a))
Si devuelve una respuesta distinta de cero cuando a==b, se viola ese contrato.
