sorting - sort/2, keysort/2 vs. samsort/3, predsort/3

prolog iso-prolog

Question

ISO-Prolog proporciona sort/2 y keysort/2 que se basa en el orden de los plazos (7.2), a menudo denominado "orden de los términos estándar". La forma común de ordenar una lista con un orden diferente es mapear cada elemento El de esa lista de alguna manera a una lista de pares XKey-El y luego ordenar esa lista, y finalmente proyectar las teclas de distancia. Como ejemplo, considere cómo keysort/2 se puede expresar en términos de sort/2 ( vea la nota para una implementación ).

En muchas situaciones, este enfoque es mucho más rápido que usar un predicado de clasificación específico de implementación genérico que se basa en un orden definido por el usuario como predsort(C_3, List, SortedList) de SWI predsort(C_3, List, SortedList) o samsort de samsort(O_2, List, SortedList) .

Mi pregunta se reduce a:

¿Hay casos donde una clasificación usando predsort/3 resp. samsort/3 no puede ser reemplazado por algún mapeo, sort/2 -ing y proyección? ¹

Y por el bien de la claridad, es mejor atenerse a los términos finitos y básicos. Porque, los términos básicos infinitos no poseen un orden lexicográfico total, ya que sería necesario como una extensión del caso finito; y además, no está claro cómo resultará la comparación de variables con el caso de dos variables diferentes que dependen de la implementación dado el 7.2.1 de ISO / IEC 13211-1: 1995:

7.2.1 Variable

Si X e Y son variables que no son idénticas entonces
X term_precedes Y dependerá de la implementación
excepto que durante la creación de una lista ordenada (7.1.6.5,
8.10.3.1 j) el ordenamiento se mantendrá constante.

Por lo tanto, no está claro si predsort/3 todavía se calificaría como una creación de una lista ordenada. Lo que está claro es que el orden se mantiene constante durante la sort/2 y el keysort/2 .

1 Gracias a @WillNess, esta proyección debe incluir al menos también reverse/2 , o cualquier transformación lineal. También significa que se pueden implementar resultados con duplicados y únicos (de manera similar a la forma en que se implementa keysort/2 ).

Answer 1

Creo que podría tener una respuesta adecuada a su pregunta.

Si tiene una ordenación parcial, aún puede intentar y ordenar usando predsort/3 , y puede obtener un mejor resultado que simplemente diciendo que "no existe una ordenación total".

Aquí hay un ejemplo: digamos que tienes un juego jugado por dos equipos. Cada juego otorga un punto solo a uno de los equipos, y usted juega hasta que un equipo alcanza un cierto número de puntos.

Ahora, organiza un torneo, y tiene una fase de grupos, en grupos de 4 equipos, que es un round-robin. Solo los dos mejores equipos salen de los grupos.

Por cada juego jugado, los equipos obtienen un puntaje de own_points - other_teams_points . En otras palabras, si juegas a 7, y la puntuación final es:

Equipo A - 5: 7 - Equipo B

El equipo A marca -2 y el equipo B anota 2.

Al final de la fase de grupos, ordena los equipos por:

1. Puntaje total
2. Si el puntaje total es el mismo, el equipo que ganó la pelea directa recibe una orden más alta.

En particular, al usar este esquema de puntuación, no puede resolver un sorteo de tres vías si el Equipo A venció al Equipo B, el Equipo B venció al Equipo C y el Equipo C venció al Equipo A. Una clasificación "estable" no tiene sentido en este contexto.

Sin embargo, utilizando predsort/3 , puede intentar encontrar los dos mejores equipos y obtendrá una respuesta definitiva en la mayoría de los casos. Resolver un sorteo de tres vías como el anterior generalmente se resuelve usando un sorteo de monedas.

Answer 2

En primer lugar, puedes "negar" los átomos de Prolog. Llamémoslo atom_neg/2 (es un nombre tonto, pero de todos modos hace algo tonto):

atom_neg(A, NK) :-
    atom_codes(A, Cs),
    maplist(negate, Cs, NCs),
    append(NCs, [0], NK).

negate(X, N) :- N is -X.

No estoy diciendo que sea práctico hacer esto, pero aparentemente, es posible.

Una ordenación total es una ordenación débil, y una función clave f en un conjunto T junto con una ordenación total r en el codominio de f , define una ordenación débil wr (x, y) <==> r (f (x), f (y)) .

(El dominio de una función en ese contexto es el dominio de los valores que la función devuelve).

Podría estar totalmente equivocado, pero la existencia de una relación requiere la existencia de una clave: puede definir una relación en términos de otra relación, pero finalmente debe comparar algo que también puede existir de forma aislada: la clave.

El punto aquí es que la clave no necesita estar en el mismo dominio que lo que queremos ordenar, y que se define un ordenamiento débil (una relación) para los objetos del mismo dominio . Prolog hace algo raro aquí: define un orden estándar de términos para todos los términos posibles . Prolog tampoco tiene una noción adecuada de "tipos" o "dominios". Mi instinto me dice que clasificar las cosas que no pertenecen al mismo dominio simplemente no es muy útil, pero Prolog obviamente no está de acuerdo.

No se puede definir una función clave para dos casos:

1. El predicado de comparación mantiene su propio estado;
2. Tiene objetos "opacos" (definidos en C, por ejemplo) que proporcionan la función de comparación pero no una función clave.

De cualquier manera, predsort puede ser útil: nadie preferiría atom_neg/2 sobre la solución de Will Ness. Sin embargo, tiene una deficiencia grave en este momento: no permite una clasificación estable. El SWI-Prolog ya se puede usar de esta manera , todo lo que se necesita sería agregar el comportamiento actual a la especificación y documentación de predsort/3 .

Answer 3

edit : la respuesta de @Boris muestra cómo "negar" los átomos para los fines de comparación, por lo que invalida mi argumento contrario en ese caso. Y la nueva estipulación en la pregunta lo invalida por completo.

En el caso de criterios de clasificación complejos, se tendrán que organizar múltiples subclaves. Si se desea la retención de duplicados, los índices incrementales deben prefijarse al término original, siguiendo las subclaves de clasificación, en términos construidos para sort/2 para ordenar.

Sin embargo, la complejidad y el número de las subclaves construidas pueden salirse de control. Los puntos de clasificación de imágenes por X primero, luego por Y, en orden ascendente o descendente en algunas regiones, y por Y primero, y por X segundo, en otras.

Luego, la ventaja buscada de reemplazar el número loglineal de comparaciones (presumiblemente pesadas) con solo un número lineal de construcciones clave y un número loglinear de comparaciones (presumiblemente ligeras) en el orden estándar de los términos, puede desaparecer.

Trivialmente, predsort/3 ing, por ejemplo, una lista de átomos a la inversa, con predicado de comparación personalizado

comp(<,A,B):- B @< A.

etc., no se puede hacer por sort/2 que funciona en "orden de términos estándar" (citando la documentación de SWI). Con números, podríamos voltear la señal, pero no con nombres.

Tal vez quieras agregar el reverse a las acciones permitidas.

Con el sort/4 permitido, no veo nada que no funcione. Y como es estable, los criterios secundarios también pueden adaptarse a los pases secundarios (primero por un menor, luego por un criterio mayor).