Clasificación de paciencia - Patience sorting
| Clase | Algoritmo de clasificación |
|---|---|
| Estructura de datos | Formación |
| Rendimiento en el peor de los casos | O ( n log n ) |
| Rendimiento en el mejor de los casos | O ( n ) ; ocurre cuando la entrada está preordenada |
En informática , la clasificación por paciencia es un algoritmo de clasificación inspirado por la paciencia del juego de cartas y que lleva su nombre . Una variante del algoritmo calcula de manera eficiente la longitud de una subsecuencia creciente más larga en una matriz dada .
Visión general
El nombre del algoritmo deriva de una variante simplificada del juego de cartas de paciencia. El juego comienza con una baraja de cartas barajada. Las cartas se reparten una a una en una secuencia de montones sobre la mesa, de acuerdo con las siguientes reglas.
- Inicialmente, no hay pilas. La primera carta repartida forma una nueva pila que consta de una sola carta.
- Cada carta subsiguiente se coloca en la pila existente más a la izquierda cuya carta superior tiene un valor mayor o igual al valor de la nueva carta, o a la derecha de todas las pilas existentes, formando así una pila nueva.
- Cuando no quedan más cartas para repartir, el juego termina.
Este juego de cartas se convierte en un algoritmo de clasificación de dos fases, como sigue. Dada una matriz de n elementos de algún dominio totalmente ordenado , considere esta matriz como una colección de cartas y simule el juego de clasificación de la paciencia. Cuando termine el juego, recupere la secuencia ordenada seleccionando repetidamente la carta mínima visible; en otras palabras, realizar una k -way merge de los p pilas, cada una de las cuales se ordenan internamente.
Análisis
La primera fase de clasificación de paciencia, la simulación del juego de cartas, se puede implementar para tomar comparaciones O ( n log n ) en el peor de los casos para una matriz de entrada de n elementos: habrá como máximo n pilas y, por construcción, la parte superior las cartas de las pilas forman una secuencia creciente de izquierda a derecha, por lo que la pila deseada se puede encontrar mediante una búsqueda binaria . La segunda fase, la fusión de pilas, se puede realizar en tiempo O ( n log n ) y también utilizando una cola de prioridad .
Cuando los datos de entrada contienen "corridas" naturales, es decir, submatrices no decrecientes, el rendimiento puede ser estrictamente mejor. De hecho, cuando la matriz de entrada ya está ordenada, todos los valores forman una sola pila y ambas fases se ejecutan en tiempo O ( n ) . La complejidad promedio del caso sigue siendo O ( n log n ) : cualquier secuencia uniformemente aleatoria de valores producirá un número esperado de O ( √ n ) pilas, que toman O ( n log √ n ) = O ( n log n ) tiempo para producir y fusionar.
Chandramouli y Goldstein dan una evaluación del desempeño práctico de la clasificación con paciencia, quienes muestran que una versión ingenua es de diez a veinte veces más lenta que una clasificación rápida de última generación en su problema de referencia. Atribuyen esto a la cantidad relativamente pequeña de investigación puesta en clasificación con paciencia y desarrollan varias optimizaciones que llevan su rendimiento a un factor dos del de clasificación rápida.
Si los valores de las cartas están en el rango 1 ,. . . , n , hay una implementación eficiente con O ( n log n ) en el peor de los casos para poner las cartas en pilas, basándose en un árbol de Van Emde Boas .
Relaciones con otros problemas
La clasificación por paciencia está estrechamente relacionada con un juego de cartas llamado juego de Floyd. Este juego es muy similar al juego esbozado anteriormente:
- La primera carta repartida forma una nueva pila que consta de una sola carta.
- Cada carta subsiguiente se coloca en una pila existente cuya carta superior tiene un valor no menor que el valor de la nueva carta, oa la derecha de todas las pilas existentes, formando así una nueva pila.
- Cuando no quedan más cartas para repartir, el juego termina.
El objetivo del juego es terminar con el menor número posible de montones. La diferencia con el algoritmo de clasificación de paciencia es que no es necesario colocar una nueva carta en la pila más a la izquierda donde está permitido. La clasificación por paciencia constituye una estrategia codiciosa para jugar a este juego.
Aldous y Diaconis sugieren definir 9 o menos montones como un resultado ganador para n = 52 , lo que ocurre con aproximadamente un 5% de probabilidad.
Algoritmo para encontrar una subsecuencia creciente más larga
Primero, ejecute el algoritmo de clasificación como se describe arriba. El número de pilas es la longitud de una subsecuencia más larga. Siempre que se coloque una carta en la parte superior de una pila, coloque un puntero hacia atrás a la carta superior de la pila anterior (que, por supuesto, tiene un valor más bajo que la nueva carta). Al final, siga los indicadores hacia atrás de la carta superior en la última pila para recuperar una subsecuencia decreciente de la longitud más larga; su reverso es una respuesta al algoritmo de subsecuencia creciente más largo.
S. Bespamyatnikh y M. Segal dan una descripción de una implementación eficiente del algoritmo, sin incurrir en un costo asintótico adicional sobre el de clasificación (ya que el almacenamiento, la creación y el recorrido de los back-pointers requieren tiempo y espacio lineales). Además, muestran cómo informar todas las subsecuencias crecientes más largas de las mismas estructuras de datos resultantes .
Historia
La clasificación de paciencia fue nombrada por CL Mallows, quien atribuyó su invención a ASC Ross a principios de la década de 1960. Según Aldous y Diaconis, Hammersley reconoció por primera vez la clasificación por paciencia como un algoritmo para calcular la longitud de subsecuencia cada vez mayor más larga. ASC Ross e independientemente Robert W. Floyd lo reconocieron como un algoritmo de clasificación. Mallows realizó el análisis inicial. El juego de Floyd fue desarrollado por Floyd en correspondencia con Donald Knuth .
Usar
El algoritmo de clasificación de paciencia se puede aplicar al control de procesos . Dentro de una serie de mediciones, la existencia de una subsecuencia creciente larga se puede utilizar como marcador de tendencia. Un artículo de 2002 en la revista SQL Server incluye una implementación de SQL, en este contexto, del algoritmo de clasificación de paciencia para la longitud de la subsecuencia creciente más larga.