Ordenar algoritmos que funcionan en gran cantidad de datos

12

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

El único candidato que he encontrado hasta ahora es el tipo de combinación: puede implementar el algoritmo de tal manera que escanee su conjunto de datos en cada combinación sin mantener todos los datos en la memoria principal a la vez. La variación del tipo de fusión que tengo en mente se describe en este artículo en la sección Usar 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 caben en la memoria principal.

EDITAR

Aquí hay algunos detalles más, como lo requieren las respuestas:

  • Los datos deben clasificarse periódicamente, por ejemplo, una vez al 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 estarlo.
  • Los datos son volcados 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 sean lo suficientemente pequeños como para ordenarlos en la memoria, y finalmente fusionar todos estos archivos usando el algoritmo que he descrito anteriormente.

Giorgio
fuente
1
¿Qué tipo de datos? Diferentes conjuntos de datos pueden significar diferentes algoritmos que mejor se adapten a su propósito.
cuál es el
Es un archivo de texto y tengo que ordenar las líneas. Las líneas no tienen una longitud fija, pero la longitud no varía demasiado (alrededor de 50 caracteres por registro).
Giorgio
3
No conozco su entorno o sus limitaciones, pero usaría una base de datos para ordenar siempre que sea posible. Esto se debe a que es casi 100% a prueba de errores y será mucho más eficiente que mi código.
NoPuerto
Estoy trabajando en Linux / Java. He implementado el tipo de fusión y parece funcionar bastante bien. Ordenar varios millones de líneas lleva bastante tiempo, pero solo necesito hacer esto de vez en cuando.
Giorgio
@Giorgio, es bueno que hayas implementado dicho algoritmo. Para el trabajo de producción, aún le sugiero que use una base de datos. No solo por la velocidad, sino también por la fiabilidad y la facilidad de mantenimiento.
NoPuerto

Respuestas:

13

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

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

John R. Strohm
fuente
2
Gracias por la referencia: estoy casi seguro de que encontraré material interesante en el libro de Knuth. No estoy seguro de que las técnicas de clasificación sin memoria no sean relevantes hoy en día. Tal vez no sea para tareas cotidianas comunes, pero puedo imaginar que todavía hay muchas situaciones en las que se deben procesar conjuntos de datos muy grandes.
Giorgio
Los algoritmos de Knuth siempre son útiles. Por ejemplo, una ordenación combinada con un búfer de ordenación en montón puede ser muy efectiva y MUY fácil de implementar.
Sulthan
44
No es una respuesta muy útil porque el material referido no es gratuito. Para el OP, sugiero buscar en Google una respuesta. No necesita gastar $ 50 dólares para obtener un libro cuando este tipo de información puede encontrar al buscar en la web. Por supuesto, es probable que también pueda descargar esto gratuitamente de ( ejem ) ciertos sitios. Apenas merece una respuesta aceptada.
Thomas Eding
1
@ThomasEding, existen estas cosas llamadas "bibliotecas", que contienen grandes cantidades de estos dispositivos obsoletos de almacenamiento y recuperación de información llamados "libros". Las "bibliotecas" ponen a disposición "libros" de forma GRATUITA. Si su "biblioteca" particular no tiene el "libro" particular que busca, también ofrecen un servicio GRATUITO llamado "préstamo interbibliotecario", que permite que la "biblioteca" tome prestado el "libro" de otra "biblioteca", para que puedan te lo presto.
John R. Strohm
6

La combinación externa de R-Way como en el sortcomando UNIX es una buena alternativa. Según su formulación, no estoy seguro de si ese es el algoritmo que quiso decir con "ordenar fusión", y si no lo sabe, eche un vistazo.

thiton
fuente
Gracias. La fusión externa de R-Way parece diferente de lo que tenía en mente. Interesante lectura.
Giorgio
4

Sin más detalles "Merge Sort" es probablemente la mejor respuesta que obtendrá, sin embargo, puede implementar algo mucho más inteligente según sus requisitos.

Por ejemplo, ¿puede simplemente crear un índice en 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 el segundo, entonces es posible que no pueda ajustar un índice en la memoria, si es el primero, puede ordenar las dos mitades de manera más eficiente y luego combinarlas en un solo último paso.

Demonios, dado que no lo especificó, es posible que sus datos estén todos en una base de datos, de ser así, simplemente puede crear una tabla de índice y llamarla buena (supongo que este no es el caso, pero solo 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 hack 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 único registro, entonces será necesario un orden de inserción (Agregar un solo registro a los datos ordenados siempre es un orden de inserción).

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

Entonces:

  • ¿En el lugar o archivo múltiple?
  • ¿Una vez, periódico o mantenerlo ordenado en todo momento?
  • ¿Cuánto más grande que la memoria (¿Cuántas cargas de memoria pasar por todo el conjunto de datos)?
  • ¿Está en una base de datos? ¿Puede ser?
  • ¿Controla el código que lee los datos, o otros estarán volcando un archivo directamente?
  • ¿Formato de archivo? (¿Texto? ¿Registro fijo?)
  • ¿Alguna otra circunstancia especial que no haya preguntado?
Bill K
fuente
Gracias por la respuesta. ¿Qué quiere decir con "registro en el lugar o múltiple"?
Giorgio
Lo siento, debería haber corregido mi respuesta, me refería a varios archivos. En su lugar, prácticamente implica un tamaño de registro fijo e indexación, en cuyo punto probablemente querría una base de datos.
Bill K
No, no está en su lugar: los registros no tienen un tamaño fijo. Utilizo cuatro archivos temporales para mi implementación actual.
Giorgio
¿Puede interpretar la salida con código o tiene que estar en un formato específico (archivo de texto plano)? ¿Con qué frecuencia necesita ser ordenada, cada vez que se agrega algo o solo ocasionalmente? Cuando se agrega algo, ¿se agrega al final o puede escribir el código que lo agrega?
Bill K
Cada línea se puede analizar en un registro (el archivo es un archivo CSV) pero la mayoría de los campos son texto. Debe ordenarse de vez en cuando (p. Ej., Cada mes) y se tarda aproximadamente 1 hora en ordenar con mi implementación actual. Para insertar una línea, podría escribir el código que inserta la línea en el lugar correcto: con el código que tengo hasta ahora me tomaría 20 minutos escribir dicha herramienta.
Giorgio
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 .

m3th0dman
fuente
1
+1: enlace interesante. ¿La fusión no es un ejemplo de mapa / reducción, donde el mapa corresponde a la clasificación de sublistas, y la reducción corresponde a la fusión?
Giorgio
Puede verse así, pero puede usar Hadoop para hacer esto por usted en lugar de escribirlo usted mismo.
m3th0dman el
1

Puede que te interese un tipo de cubo . El rendimiento promedio del caso es el tiempo lineal.

= O (n + d) n: número de elementos yd = longitud del número más grande si tiene una intuición sobre sus datos, es decir. Si sabe cuántos 'dígitos' de largo es su número más grande. Entonces, si tiene 2 millones de números de 6 dígitos => 0 (n), entonces lineal.

metal de piedra
fuente
0

Utilice un algoritmo de ordenación de fusión externo (si sus datos son continuos), o una ordenación de cubetas con ordenación de conteo como implementación de la ordenación de cubetas (si sus datos son discretos y están distribuidos de manera uniforme).

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

  1. Solicite de alguna manera su "base de datos"
  2. Asigne un número entero a cada entrada (1, 2, 3, 4, ..., n) (mejor: use algunos índices dispersos)
  3. Al agregar un incremento, solo encuentre un espacio donde el número izquierdo sea menor o igual y el número derecho sea mayor o igual (no debería ser difícil con alguna versión modificada de una búsqueda binaria)
  4. Insertar, mientras que los espacios son suficientemente grandes, si no: simplemente reindexar (nunca ordenar de nuevo) :-)
malejpavouk
fuente
0

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

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

Aquí hay una publicación sobre cómo buscar big data utilizando mi gran cola de código abierto y estructuras de matriz grande.

Buldog
fuente