¿La clasificación por "comparador" no transitivo funciona?

¿Qué pasará si proporciono un Comparator no transitivo al Collections.sort? ¿Puedo correr en un bucle infinito?¿La clasificación por "comparador" no transitivo funciona?

Una pequeña prueba que escribí produjo una salida, pero quiero asegurarme de que siempre sea así.

El problema es que, en algunos casos, mi comparador puede producir ciclos, y en este caso solo quiero asegurarme de que no se ejecutará en un bucle infinito. No me importa el resultado real.

Fuente

2011-10-31 duduamar

¿Tal vez publiques algún código relevante? – pap

Esta es una pregunta general, no relevante para un código específico: la pregunta es cuál es el comportamiento si proporciono un comparador que no es transitivo para Collections.sort – duduamar

El comportamiento de usar un 'Comparator' no transitivo no está definido, ya que ** Comparador no transitivo ** no está implementado correctamente **. En la práctica, estoy * bastante * seguro de que 'Collections.sort()' * no * se ejecutará en un bucle infinito, incluso si 'Comparator' está roto. Pero nada en las especificaciones * requiere * este comportamiento. –

El Java docs dice que debe asegurarse de que su comparador sea transitivo. Si proporciona un comparador que no cumple con lo solicitado, todas las apuestas están desactivadas. Podría funcionar para una implementación dada, pero podría fallar horriblemente (std::sort en C++) en otro.

En resumen, no debe confiar en que funcione incluso si lo hace por algunos u otros ejemplos.

Fuente

2011-10-31 08:24:51 Pablo

Sí ... eso tiene sentido. No debería confiar en eso, gracias. – duduamar

Hola Pablo.Lamento secuestrar un comentario, pero he hecho una pregunta aquí: https://stackoverflow.com/questions/45599509/why-does-stdsort-segfault-with-non-transitive-comparators Usted Al parecer, he enfrentado el problema que estoy enfrentando hoy, donde C++ std :: sort se bloquea con un comparador no transitivo. Me preguntaba si sabías por qué? De nuevo, siento secuestrar un comentario de 6 años de edad, pero existen muy pocos datos sobre este tema. –

El Collections.sort() se basa en un mergesort.

un mergesort tiene una O (logn) iteraciones en general, porque el tamaño de la matriz SIEMPRE está dividido, por lo que el sort() debería finalizar, independientemente de que el Comparador no sea transitivo, por lo que no se producirá un bucle infinito.

Sin embargo, no hay garantías en el orden de la lista resultante.

Fuente

2011-10-31 08:29:43 amit

Este es un buen comentario, pero la implementación podría ser modificada sin previo aviso ... – duduamar

Sí. Cambió en Java 7. – vz0

El comportamiento de Collections.sort en este caso depende de la implementación. La implementación de Java 6 SE usa una combinación de Mergesort e Insertionsort que son ambos deterministas con comparadores no transitivos, pero en Java 7 el algoritmo Timsort se usa y otras implementaciones pueden usar Quicksort u otra cosa, por lo que no puede estar seguro de que lo hará trabajar con todas las implementaciones

Fuente

2011-10-31 08:30:08 x4u

En primer lugar, sugiero que piense en la comparación - es la operación de compasión realmente relación de equivalencia. Si acepta que no es y debe ser, haga un seguimiento de objetos comparados en alguna variable local. Esta variable local se puede comparar con objetos o con la variable local de subprocesos. Esta variable puede ser el conjunto de pares de objetos comparados. Dentro de compare verificación de invocación de método si se visitó este par; si es verdadero, decida qué hacer. Pero tome el auto sobre el conjunto de objetos visitados, realmente debería contener algo como hash o id de objeto, porque puede ir al infinito de otra manera. Y también tenga en cuenta que el almacenamiento del par comparado en la variable local consume memoria.

Fuente

2011-10-31 08:30:12 Max

Dado que Java 7 Collections.sort utiliza TimSort. El uso de un comparador no transitivo para ordenar en Java> = 7 arrojará la siguiente excepción:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

Fuente

2014-12-04 13:50:50 Martin

¿La clasificación por "comparador" no transitivo funciona?

Respuesta

Cuestiones relacionadas