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.
fuente
Respuestas:
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.
fuente
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.fuente
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:
fuente
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 .
fuente
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.
fuente
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.
fuente
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.
fuente