performance algorithm language-agnostic sorting

performance - Clasificación eficiente fuera del núcleo



algorithm language-agnostic (7)

Estoy tratando de averiguar cómo ordenar de manera eficiente un gran conjunto de datos que no cabe en la memoria. La respuesta obvia a un nivel alto es ordenar un montón de trozos que encajan en la memoria usando un algoritmo estándar, escribirlos en el disco y luego combinarlos. Fusionarlas es el problema.

Digamos que los datos se dividen en segmentos C, por lo que tengo archivos C para fusionar. Si hago una combinación de C-way en una pasada, técnicamente tengo un algoritmo O (N ^ 2), aunque uno que solo tiene que realizar escrituras O (N) en el disco. Si los fusiono de forma iterativa en archivos C / 2, luego en archivos C / 4, etc., entonces tengo un algoritmo O (N log N), pero uno que tiene que realizar escrituras O (N log N) en el disco, y por lo tanto tiene Un gran término constante.

¿Cuál es la solución típica a este enigma? ¿Hay alguna buena?

¿Está clasificando en su lugar o creando una nueva copia? Si está ordenando en su lugar, entonces la IO asignada en memoria es generalmente una buena opción. Simplemente asigne todo el archivo y realice una clasificación de fusión en él. El sistema operativo mantendrá la mayor parte del archivo en la memoria y, dependiendo del conjunto de datos, generalmente minimizará su IO.

Si escribe su propio algoritmo de clasificación, un truco es revertir su dirección después de cada paso. Entonces, si es tu primer paso, comienzas de principio a fin, luego avanza de principio a fin en tu segundo paso. Si divide sus archivos en las partes A, B, C y D, luego de clasificar C y D, debe combinar C y D, y no volver a A y B. La razón, por supuesto, es que su sistema operativo pagará partes de la archivos en la memoria, y desea utilizar el caché tanto como sea posible.

¿Por qué no mirar el problema desde una perspectiva diferente? Por ejemplo, si está clasificando nombres, haga un pase, clasifique cualquier cosa que comience con AF , una segunda secuencia de clasificación que comience con GM , etc. Luego, los resultados pueden simplemente agregarse en orden. La desventaja es que los datos se deben leer del disco C veces.

Es gracioso cuando escuché esta misma pregunta hace un mes ... y la respuesta que también dio nuestro gurú local.

"Usa el comando de clasificación de Unix "

Aunque, de manera admirable, pensamos que era una broma a costa del que pregunta ... resulta que no lo fue. El razonamiento es que esos chicos inteligentes ya pensaron mucho en cómo resolver el problema de archivos muy grandes, y crearon una implementación impresionante que hace un buen uso de los recursos disponibles.

Por lo tanto, a menos que planee reinventar la rueda: es decir, tiene tiempo y esto es fundamental para el negocio, entonces simplemente usar la unix sort es probablemente una excelente idea.

El único inconveniente es su sintaxis arcana. Esta página está dedicada al comando y varias explicaciones.

Mi consejo personal: tome una pequeña muestra de los datos para comprobar que el comando hace exactamente lo que quiere.

La respuesta simple es que no hay una respuesta simple para esta pregunta. Hay muchas respuestas, la mayoría bastante complejas: Knuth volumen 3 (por ejemplo, le dedica una gran cantidad de espacio).

Una cosa que se vuelve obvia cuando se analiza lo que se ha hecho es que realmente desea minimizar el número de ejecuciones que crea durante su clasificación inicial y maximizar la longitud de cada una. Para hacer eso, generalmente desea leer la mayor cantidad de datos que puede caber en la memoria, pero en lugar de simplemente ordenarlos y escribirlos, querrá ponerlos en un montón. Luego, a medida que escribe cada registro, lee EN otro registro.

Luego verifica si ese registro se clasificaría antes o después del registro que acaba de escribir. Si lo ordenara, insértelo en su montón y continúe. Si se ordenara antes, insértelo en un segundo montón.

Deja de agregar registros a la ejecución actual cuando el primer montón está completamente vacío, y su segundo montón está ocupando toda su memoria. En ese punto, repite el proceso, escribiendo una nueva ejecución en un nuevo archivo.

Por lo general, esto producirá corridas intermedias considerablemente más largas en la fase inicial, por lo que fusionarlas es sustancialmente menos trabajo. Suponiendo que los registros de entrada están en orden aleatorio, puede esperar que esto duplique aproximadamente la longitud de cada ejecución, pero si la entrada se clasifica parcialmente, esto puede aprovechar el orden existente para extender aún más las longitudes de ejecución.

Aparte de eso, ciertamente no inventé esto, probablemente lo leí primero en Knuth, pero quizás en Algorithms + Data Structures = Programs (Niklaus Wirth), ambos lo discuten. Knuth acredita la primera publicación del método a "H. Seward", en su tesis de maestría en el MIT en 1954. Si tiene la segunda edición de Knuth, está en la página 254 del volumen 3. No tengo una copia de la tercera. Edición, así que no tengo un número de página para eso.

Nick tiene razón, usa la clasificación externa. Tu fusión C-way no implica O (N ^ 2), por cierto. Use una cola de prioridad para la combinación y aún es O (N lg N).

También puede consultar los algoritmos ajenos a la caché para la clasificación.

Una buena solución es la clasificación externa . Específicamente, echa un vistazo al algoritmo de combinación externa .

La clasificación externa es un término para una clase de algoritmos de clasificación que pueden manejar grandes cantidades de datos. La clasificación externa es necesaria cuando los datos que se están clasificando no encajan en la memoria principal de un dispositivo informático (generalmente RAM) y, en cambio, deben residir en la memoria externa más lenta (generalmente un disco duro). El algoritmo de clasificación externo típico utiliza una estrategia de combinación de ordenación, que comienza con la clasificación de subarchivos pequeños. El algoritmo básico consta de dos fases: la fase de clasificación y la fase de fusión. En la fase de clasificación, los subarchivos pueden caber en el espacio disponible en el búfer, se leen en la memoria principal, se clasifican utilizando un algoritmo de clasificación interno y se vuelven a escribir en el disco como subarchivos clasificados temporalmente. En la fase de fusión, los subarchivos ordenados se combinan durante una o más pasadas.