Ordenar un archivo con gran volumen de datos dada restricción de memoria

Puede leer los archivos en partes más pequeñas, ordenarlos y escribirlos en archivos temporales. Luego lee dos de ellos secuencialmente de nuevo y los fusiona en un archivo temporal más grande y así sucesivamente. Si solo queda uno, tendrá su archivo ordenado. Básicamente ese es el algoritmo Megresort realizado en archivos externos. Se escala bastante bien con archivos aribitrarios de gran tamaño, pero causa alguna E/S de archivo adicional.

Editar: Si tiene algún conocimiento sobre la probable varianza de las líneas en sus archivos, puede emplear un algoritmo más eficiente (ordenación por distribución). Simplificado leería el archivo original una vez y escribiría cada línea en un archivo temporal que solo toma líneas con el mismo primer carácter (o un cierto rango de primeros caracteres). Luego itera sobre todos los archivos temporales (ahora pequeños) en orden ascendente, los ordena en memoria y los anexa directamente al archivo de salida. Si un archivo temporal resulta ser demasiado grande para ordenar en memoria, puede repetir el mismo proceso para esto basado en la 2nd char en las líneas y así sucesivamente. Por lo tanto, si su primera partición fue lo suficientemente buena como para producir archivos lo suficientemente pequeños, solo tendrá una sobrecarga de E/S del 100%, independientemente del tamaño del archivo, pero en el peor de los casos puede ser mucho más que con el rendimiento en cuanto a la ordenación merge estable.

A pesar de su restricción, usaría embedded database SQLITE3. Como usted, trabajo semanalmente con 10-15 millones de líneas de archivos planos y es muy, muy rápido para importar y generar datos ordenados, y solo necesita un poco de ejecutable gratuito (sqlite3.exe). Por ejemplo: Una vez que descargue el archivo .exe, en un símbolo del sistema puede hacer esto:

C:> sqlite3.exe dbLines.db
sqlite> create table tabLines(line varchar(5000));
sqlite> create index idx1 on tabLines(line);
sqlite> .separator '\r\n'
sqlite> .import 'FileToImport' TabLines

Entonces:

sqlite> select * from tabLines order by line;

or save to a file:
sqlite> .output out.txt
sqlite> select * from tabLines order by line;
sqlite> .output stdout

Me gustaría girar un clúster EC2 y ejecutar Hadoop MergeSort.

Editar : no estoy seguro de cuánto detalle le gustaría, o sobre qué. EC2 es la nube de computación elástica de Amazon : le permite alquilar servidores virtuales por hora a bajo costo. Aquí está su sitio web.

Hadoop es un framework MapReduce de código abierto diseñado para el procesamiento paralelo de grandes conjuntos de datos. Un trabajo es un buen candidato para MapReduce cuando se puede dividir en subconjuntos que se pueden procesar individualmente y luego fusionados, generalmente clasificando las teclas (es decir, la estrategia de dividir y conquistar). Aquí está su sitio web.

Como se menciona en los otros carteles, la clasificación externa también es una buena estrategia. Creo que la forma en que decidiría entre los dos depende del tamaño de los datos y los requisitos de velocidad. Es probable que una sola máquina se limite a procesar un solo archivo a la vez (ya que usará la memoria disponible). Así que mira algo como EC2 solo si necesita procesar archivos más rápido que eso.

Como se mencionó anteriormente, puede procesar en pasos.
Me gustaría explicar esto con mis propias palabras (difiere en el punto 3) :

1. Lea el archivo secuencialmente, procese N registros a la vez en memoria (N es arbitrario, dependiendo de su restricción de memoria y el número T de archivos temporales que desee).

2. Ordena los N registros en memoria, escríbelos en un archivo temporal. Bucle en T hasta que haya terminado.

3. Abra todos los archivos temporales de T al mismo tiempo, pero lea solo un registro por archivo. (Por supuesto, con tampones). Para cada uno de estos registros T, encuentre el más pequeño, escríbalo en el archivo final y avance solo en ese archivo.

Ventajas:

• El consumo de memoria es tan bajo como quieras.
• Solo hace el doble de accesos al disco en comparación con una política de todo en memoria. No está mal! :-)

Ejemplo con números:

1. Archivo original con 1 millones de discos.
2. Elija tener 100 archivos temporales, así que lea y clasifique 10 000 registros a la vez, y colóquelos en su propio archivo temporal.
3. Abra el archivo 100 temp a la vez, lea el primer registro en memoria.
4. Compare los primeros registros, escriba los más pequeños y avance este archivo temporal.
5. Bucle en el paso 5, un millón de veces.

EDITADO

Mencionaste una aplicación multihilo, así que me pregunto ...

Como hemos visto en estos las discusiones sobre esta necesidad, usando menos memoria da menos rendimiento, con un factor dramático en este caso. Así que también podría sugerir que use solo un hilo para procesar solo un tipo a la vez, no como una aplicación multihilo.

Si procesa diez subprocesos, cada uno con una décima parte de la memoria disponible, su rendimiento será miserable, mucho menos que una décima parte del tiempo inicial. Si utiliza solo un hilo, y pone en cola las otras 9 demandas y las procesa a su vez, se el rendimiento será mucho mejor, terminarás las diez tareas mucho más rápido.

Después de leer esta respuesta : Ordenar un archivo con gran volumen de datos dada restricción de memoria Le sugiero que considere este tipo de distribución. Podría ser una gran ganancia en su contexto.

La mejora sobre mi propuesta es que no necesita abrir todos los archivos temporales a la vez, solo abre uno de ellos. Se salva el día! :-)

Si su restricción es solo no usar un sistema de base de datos externo, puede probar con una base de datos incrustada (por ejemplo, Apache Derby). De esta manera, obtendrá todas las ventajas de una base de datos sin dependencias de infraestructura externas.

Podrías usar la siguiente estrategia de divide y vencerás:

Crea una función H() que puede asignar un número a cada registro en el archivo de entrada. Para un registro r2 que se ordenará detrás de un registro r1 debe devolver un número mayor para r2 que para r1. Utilice esta función para particionar todos los registros en archivos separados que quepan en la memoria para que pueda ordenarlos. Una vez que haya hecho eso, puede concatenar los archivos ordenados para obtener un archivo ordenado grande.

Supongamos que usted tiene este archivo de entrada donde cada línea representa un registro

Alan Smith
Jon Doe
Bill Murray
Johnny Cash

Vamos a construir H() para que use la primera letra en el registro para que pueda obtener hasta 26 archivos, pero en este ejemplo solo obtendrá 3:

<file1>
Alan Smith

<file2>
Bill Murray

<file10>
Jon Doe
Johnny Cash

Ahora puede ordenar cada archivo individual. Que cambiaría "Jon Doe" y "Johnny Cash" en . Ahora, si solo concatenas los 3 archivos tendrás una versión ordenada de la entrada.

Tenga en cuenta que divide primero y solo conquistar (ordenar) más tarde. Sin embargo, usted hace asegúrese de hacer la partición de una manera que las partes resultantes que necesita ordenar no se superpongan, lo que hará que la fusión del resultado sea mucho más simple.

El método por el cual implementas la función de particionamiento H() depende mucho de la naturaleza de tus datos de entrada. Una vez que haya resuelto esa parte, el resto debería ser muy fácil.

Sé que mencionaste no usar una base de datos sin importar cuán ligera sea... por lo tanto, tal vez esto no es una opción. Pero, ¿qué pasa con hsqldb en la memoria... enviarlo, ordenarlo por consulta, purgarlo. Sólo una idea.

Puede usar SQL Lite file db, cargar los datos en la base de datos y luego dejar que ordene y devuelva los resultados por usted. Ventajas: No hay necesidad de preocuparse por escribir el mejor algoritmo de clasificación. Desventaja: Necesitará espacio en disco, procesamiento más lento. https://sites.google.com/site/arjunwebworld/Home/programming/sorting-large-data-files

Aquí hay una manera de hacerlo sin un uso intensivo de la ordenación en Java y sin usar DB. Supuestos: Tiene 1 TB de espacio y los archivos contienen o comienzan con un número único, pero no están ordenados

Divide los archivos N veces.

Lea esos N archivos uno por uno, y cree un archivo para cada línea/número

Nombre ese archivo con el número correspondiente.Al nombrar mantener un contador actualizado para almacenar menos recuento.

Ahora ya puede tener la carpeta raíz de archivos marcada para ordenar por nombre o pausar el programa para darle el tiempo para disparar el comando en su sistema operativo para ordenar los archivos por nombres. También puedes hacerlo programáticamente.

Ahora tiene una carpeta con archivos ordenados con su nombre, usando el contador comience a tomar cada archivo uno por uno, ponga números en su archivo de SALIDA, ciérrelo.

Cuando haya terminado, tendrá un archivo grande con números ordenados.

Puede hacerlo con solo dos archivos temporales - origen y destino - y tan poca memoria como desee. En el primer paso su fuente es el archivo original, en el último paso el destino es el archivo de resultado.

En cada iteración:

• leer desde el archivo fuente en un búfer deslizante un trozo de datos de la mitad del tamaño del búfer;
• ordenar todo el búfer
• escriba en el archivo de destino la primera mitad del búfer.
• cambie la segunda mitad del búfer a la comienzo y repetición

Mantenga una bandera booleana que indique si tuvo que mover algunos registros en la iteración actual. Si el indicador sigue siendo false, el archivo se ordena. Si se genera, repita el proceso utilizando el archivo de destino como fuente.

Número máximo de iteraciones: (tamaño del archivo) / (tamaño del búfer) * 2

Si puedes avanzar/retroceder en un archivo (seek), y reescribir partes del archivo, entonces deberías usar bubble sort.

Tendrá que escanear líneas en el archivo, y solo tendrá que tener 2 filas en memoria en este momento, y luego intercambiarlas si no están en el orden correcto. Repita el proceso hasta que no haya archivos para intercambiar.