Ordenar algoritmos que funcionan con una gran cantidad de datos

12

Estoy buscando algoritmos de clasificación que puedan funcionar con una gran cantidad de datos, es decir, que puedan funcionar incluso cuando todo el conjunto de datos no se puede mantener en la memoria principal a la vez.

El único candidato que he encontrado hasta ahora es la ordenación de combinación: puede implementar el algoritmo de tal manera que escanee su conjunto de datos en cada combinación sin tener todos los datos en la memoria principal al mismo tiempo. La variación del tipo de combinación que tengo en mente se describe en este artículo en la sección Uso con unidades de cinta .

Creo que esta es una buena solución (con complejidad O (nx log (n)) pero tengo curiosidad por saber si hay otros algoritmos de clasificación (posiblemente más rápidos) que puedan funcionar en grandes conjuntos de datos que no encajan en el main memoria.

EDIT

Aquí hay algunos detalles más, según lo requieren las respuestas:

  • Los datos deben ordenarse periódicamente, por ejemplo, una vez en un mes. No necesito insertar algunos registros y ordenar los datos de forma incremental.
  • Mi archivo de texto de ejemplo tiene aproximadamente 1 GB de texto UTF-8, pero quería resolver el problema en general, incluso si el archivo fuera, digamos, 20 GB.
  • No está en una base de datos y, debido a otras restricciones, no puede estar.
  • Los datos son descargados por otros como un archivo de texto, tengo mi propio código para leer este archivo de texto.
  • El formato de los datos es un archivo de texto: los nuevos caracteres de línea son separadores de registros.

Una posible mejora que tenía en mente era dividir el archivo en archivos que son lo suficientemente pequeños para ser ordenados en la memoria, y finalmente fusionar todos estos archivos utilizando el algoritmo que he descrito anteriormente.

    
pregunta Giorgio 03.01.2012 - 15:57

7 respuestas

13

La referencia canónica sobre clasificación y búsqueda es Knuth, vol. 3 . Comience allí.

El libro se escribió originalmente cuando las computadoras eran mucho más pequeñas y lentas de lo que son ahora, lo que hizo que las técnicas de clasificación fuera de la memoria fueran más importantes de lo que se cree que son hoy.

    
respondido por el John R. Strohm 03.01.2012 - 20:13
6

Fusión R-Way externa como en UNIX El comando sort es una buena alternativa. A partir de su formulación, no estoy seguro de si ese es el algoritmo al que se refería con "orden de fusión", y si no lo sabe, eche un vistazo.

    
respondido por el thiton 03.01.2012 - 16:05
4

Sin más detalles, "Combinar clasificación" es probablemente la mejor respuesta que obtendrás, sin embargo, puedes implementar algo mucho más inteligente según tus requisitos.

Por ejemplo, ¿puede simplemente crear un índice en la memoria del archivo y luego copiar todos los valores a la vez, almacenando en caché la ubicación de varios valores clave? ¿Encaja 1/2 en la memoria a la vez, o 1/1000000? Si es la segunda, es posible que no pueda incluir un índice en la memoria, y si la primera puede clasificar ambas mitades de manera más eficiente y combinarlas en un último paso.

Demonios, ya que no lo especificaste, es posible que tus datos estén todos en una base de datos, si es así, puedes crear una tabla de índices y calificarla como buena (supongo que no es así, pero señalando que su situación es crítica para resolver un problema complicado como este).

Si desea hacerlo solo una vez y está buscando un truco muy rápido, parece que ese tipo de fusión externa sería un buen comienzo si está ejecutando Unix (ya que aparentemente está integrado)

Si tiene que mantenerlo en orden y siempre está agregando un solo registro, entonces será necesario un orden de inserción (Agregar un solo registro a los datos ordenados siempre es una orden de inserción).

¿Puedes controlar el código que "lee" los datos? Si es así, entonces muchas formas de indexación (en lugar de clasificar moviendo los datos en el disco) ayudarán a MUCHO (en realidad será un requisito absoluto).

Entonces:

  • ¿En lugar o archivo múltiple?
  • ¿Una vez, periódicamente o mantenerlo ordenado en todo momento?
  • ¿Cuánto más grande que la memoria (cuántas cargas de memoria pasan por todo el conjunto de datos)?
  • ¿Está en una base de datos? ¿Puede ser?
  • ¿Controla el código que lee los datos, o otros descargarán un archivo directamente?
  • ¿Formato de archivo? (¿Texto? ¿Registro fijo?)
  • ¿Alguna otra circunstancia especial que no haya preguntado?
respondido por el Bill K 03.01.2012 - 18:04
3

Si realmente desea una solución escalable, debería echar un vistazo a TeraSort, la implementación de clasificación estándar con map-reduce; más detalles sobre StackOverflow .

    
respondido por el m3th0dman 01.11.2012 - 09:28
1

Es posible que te interese un ordenación de depósito . El rendimiento promedio del caso es el tiempo lineal.

= O (n + d) n: número de elementos y d = longitud del número más grande Si tienes una intuición sobre tus datos, es decir. Si sabes cuántos "dígitos" de largo es tu número más grande. Entonces, si tiene 2 millones de números de 6 dígitos = > 0 (n) por lo tanto lineal.

    
respondido por el stonemetal 03.01.2012 - 23:02
0

Use el algoritmo de clasificación de combinación externa (si sus datos son continuos), o una clasificación de cubo con < a href="http://en.algoritmy.net/article/40549/Counting-sort"> counting sort como una implementación de la clasificación de grupos (si sus datos son discretos y están distribuidos uniformemente).

Probablemente, el mejor enfoque es crear su propio archivo de índice / mapeo si el incremento es pequeño.

  1. De alguna manera ordena tu "base de datos"
  2. Asigne un entero a cada entrada (1, 2, 3, 4, ..., n) (mejor: use algunos índices dispersos)
  3. Cuando agregue un incremento, simplemente encuentre un espacio donde el número de la izquierda sea menor o igual y el número de la derecha sea mayor o igual (no debería ser difícil con alguna versión modificada de una búsqueda binaria)
  4. Insertar, mientras que las brechas son suficientemente grandes, si no: simplemente reindexar (nunca ordenarlas de nuevo) :-)
respondido por el malejpavouk 06.01.2012 - 12:30
0

Acabo de crear algunas estructuras abstractas llamadas cola grande y matriz grande para simplificar la tarea de clasificación y búsqueda de datos grandes en una sola máquina con memoria limitada. Básicamente, el algoritmo utilizado es similar al que mencionó anteriormente: clasificación de combinación externa.

Puedo ordenar datos de 128GB (cada elemento de 100 bytes) en 9 horas en una sola máquina, y luego buscar en binario los datos ordenados casi sin tiempo.

Aquí es una publicación sobre cómo buscar Big Data mediante el uso de mi gran cola de código abierto y grandes estructuras de matriz.

    
respondido por el Bulldog 26.01.2013 - 16:29

Lea otras preguntas en las etiquetas