algorithm - recursive - mergesort y quicksort
¿Por qué se prefiere el tipo de fusión sobre el ordenamiento rápido para ordenar listas vinculadas? (3)
La clasificación rápida funciona bien para clasificar en el lugar. En particular, la mayoría de las operaciones se pueden definir en términos de intercambio de pares de elementos en una matriz. Para hacer eso, sin embargo, normalmente "camina" a través de la matriz con dos punteros (o índices, etc.) Uno comienza al principio de la matriz y el otro al final. Ambos se abren camino hacia el medio (y terminas con un paso de partición particular cuando se encuentran). Eso es costoso con los archivos, porque los archivos están orientados principalmente hacia la lectura en una dirección, de principio a fin. Comenzar desde el final y buscar hacia atrás suele ser relativamente costoso.
Al menos en su encarnación más simple, el tipo de fusión es más o menos lo contrario. La forma fácil de implementarlo solo requiere mirar los datos en una dirección, pero implica dividir los datos en dos partes separadas, clasificar las piezas y luego fusionarlas nuevamente.
Con una lista enlazada, es fácil tomar (por ejemplo) elementos alternados en una lista vinculada, y manipular los enlaces para crear dos listas enlazadas a partir de esos mismos elementos. Con una matriz, reorganizar elementos para que los elementos alternados entren en matrices separadas es fácil si está dispuesto a crear una copia tan grande como los datos originales, pero por lo demás bastante más no trivial.
Del mismo modo, fusionarse con matrices es fácil si combina elementos de las matrices de origen en una nueva matriz con los datos en orden, pero hacerlo en su lugar sin crear una nueva copia de los datos es una historia completamente diferente. Con una lista enlazada, la combinación de elementos de dos listas de origen en una sola lista de objetivos es trivial. De nuevo, solo manipula enlaces, sin copiar elementos.
En cuanto a usar Quicksort para producir las ejecuciones ordenadas para un tipo de combinación externa, funciona, pero (por definición) es subóptimo como regla. Para optimizar una ordenación por fusión, normalmente desea maximizar las longitudes de cada "ejecución" ordenada a medida que la produce. Si simplemente lee los datos que caben en la memoria, los envía rápidamente y los escribe, cada ejecución estará restringida (un poco menos) al tamaño de la memoria disponible.
Sin embargo, puedes hacerlo un poco mejor que eso. Empiezas leyendo en un bloque de datos, pero en lugar de usar un Quicksort en él, construyes un montón. Luego, a medida que escribe cada elemento del montón en el archivo "ejecutar" ordenado, lee otro elemento del archivo de entrada. Si es más grande que el artículo que acaba de escribir en el disco, lo inserta en su pila existente y lo repite.
Los elementos que son más pequeños (es decir, pertenecen antes de los elementos que ya se han escrito) se mantienen separados, y se construyen en un segundo montón. Cuando (y solo cuando) su primer montón está vacío, y el segundo montón se ha hecho cargo de toda la memoria, deja de escribir elementos en el archivo "ejecutar" existente y comienza uno nuevo.
Exactamente qué tan efectivo será esto depende del orden inicial de los datos. En el peor de los casos (entrada ordenada en orden inverso) no sirve para nada. En el mejor de los casos (entrada ya ordenada) le permite "ordenar" los datos en una sola ejecución a través de la entrada. En un caso promedio (entrada en orden aleatorio), le permite duplicar aproximadamente la duración de cada ejecución ordenada, lo que típicamente mejorará la velocidad en un 20-25% (aunque el porcentaje varía según cuánto más grande sea su información que la memoria disponible) )
Leí lo siguiente en un foro:
El tipo Merge es muy eficiente para estructuras de datos inmutables como listas vinculadas
y
La ordenación rápida suele ser más rápida que la ordenación por fusión cuando los datos se almacenan en la memoria. Sin embargo, cuando el conjunto de datos es enorme y se almacena en dispositivos externos, como un disco duro, el tipo de combinación es el claro ganador en términos de velocidad. Minimiza las costosas lecturas de la unidad externa
y
cuando se opera en listas enlazadas, la ordenación por fusión solo requiere una pequeña cantidad constante de almacenamiento auxiliar
¿Alguien puede ayudarme a entender el argumento anterior? ¿Por qué se prefiere el tipo de combinación para ordenar grandes listas enlazadas? y ¿cómo se reducen las lecturas costosas a un disco externo? Básicamente, quiero entender por qué uno elegiría el tipo de fusión para ordenar una gran lista vinculada.
Quicksort depende de poder indexar en una matriz o estructura similar. Cuando eso es posible, es difícil superar el Quicksort.
Pero no puede indexar directamente en una lista vinculada muy rápidamente. Es decir, si myList es una lista vinculada, entonces myList[x] , si fuera posible escribir dicha sintaxis, implicaría comenzar al principio de la lista y seguir los primeros x enlaces. Eso tendría que hacerse dos veces por cada comparación que haga Quicksort, y eso sería caro muy rápido.
Lo mismo en el disco: Quicksort debería buscar y leer cada elemento que quiera comparar.
La clasificación por fusión es más rápida en estas situaciones porque lee los elementos de forma secuencial, lo que generalmente hace que log2 (N) pase sobre los datos. Hay mucha menos E / S involucrada, y mucho menos tiempo dedicado a seguir enlaces en una lista vinculada.
Quicksort es rápido cuando los datos encajan en la memoria y pueden abordarse directamente. Mergesort es más rápido cuando los datos no caben en la memoria o cuando es costoso llegar a un elemento.
Tenga en cuenta que los tipos de archivos grandes normalmente cargan todo lo que pueden de un archivo en la memoria, lo ordena rápidamente y lo escribe en un archivo temporal, y lo repite hasta que haya pasado por todo el archivo. En ese punto hay una cierta cantidad de bloques, cada uno de los cuales está ordenado, y luego el programa realiza una fusión de N vías para producir el resultado ordenado.
Un quicksort moverá los registros al centro de la lista. Para mover un elemento al índice X, tiene que comenzar en 0 e iterar un registro a la vez.
Un mergesort divide la lista en varias listas pequeñas y solo compara el encabezado de los elementos de las listas.
La configuración para un tipo de combinación generalmente es más costosa que la requerida por un quicksort. Sin embargo, cuando una lista es lo suficientemente grande, o las lecturas son caras (como desde un disco), el tiempo que tarda la colección en iterar se convierte en un factor importante.