java - que - Ordene un archivo con gran volumen de datos dada la restricción de memoria

qué es el garbagecollector (12)

Puntos:

Procesamos miles de archivos planos en un día, al mismo tiempo.
La restricción de memoria es un problema importante.
Usamos hilo para cada proceso de archivo.
No ordenamos por columnas. Cada línea (registro) en el archivo se trata como una columna.

No se puede hacer:

No podemos usar los comandos de ordenamiento de Unix / Linux.
No podemos usar ningún sistema de base de datos sin importar lo livianos que puedan ser.

Ahora, no podemos simplemente cargar todo en una colección y usar el mecanismo de clasificación. Se comerá toda la memoria y el programa recibirá un error de montón.

En esa situación, ¿cómo ordenarías los registros / líneas en un archivo?

Como otros mencionaron, puede procesar en pasos.
Me gustaría explicar esto con mis propias palabras (difiere del punto 3):

Lea el archivo secuencialmente, procese N registros a la vez en la memoria (N es arbitrario, dependiendo de su restricción de memoria y del número T de archivos temporales que desee).
Ordene los N registros en la memoria, escríbalos en un archivo temporal. Bucle en T hasta que haya terminado.
Abra todos los archivos T temp al mismo tiempo, pero lea solo un registro por archivo. (Por supuesto, con buffers). 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:

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

EDITADO

Usted mencionó una aplicación de subprocesos múltiples, así que me pregunto ...

Como hemos visto en estas discusiones sobre esta necesidad, usar menos memoria da menos rendimiento, con un factor dramático en este caso. Así que también podría sugerir utilizar solo un hilo para procesar solo un género a la vez, no como una aplicación de subprocesos múltiples.

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

Después de leer esta respuesta: Ordene un archivo con un gran volumen de datos debido a la restricción de memoria. Le sugiero que considere esta distribución de clasificación. Podría ser una gran ganancia en tu contexto.

La mejora con respecto a mi propuesta es que no necesita abrir todos los archivos temporales a la vez, solo abre uno de ellos. ¡Ahorra tu día! :-)

Esta es una forma de hacerlo sin un uso intensivo de la ordenación de Java en el lado y sin utilizar DB. Suposiciones: tiene 1TB de espacio y los archivos contienen o comienzan con un número único, pero no están clasificados

Divida los archivos N veces.

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

Nombra ese archivo con el número correspondiente. Mientras nombras, mantén un contador actualizado para almacenar menos conteos.

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

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

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

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

Editar : no estoy seguro de la cantidad de detalles que le gustaría, o en qué. EC2 es Elastic Compute Cloud de Amazon: le permite alquilar servidores virtuales por horas a bajo costo. Aquí está su website .

Hadoop es un marco 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 fusionar, generalmente clasificando las teclas (es decir, la estrategia de dividir y vencer). Aquí está su website .

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 busque algo como EC2 solo si necesita procesar archivos más rápido que eso.

Parece que lo que estás buscando es una clasificación externa .

Básicamente, primero ordena pequeños trozos de datos, los escribe de nuevo en el disco y luego itera sobre aquellos para ordenarlos todos.

Puede hacerlo solo con dos archivos temporales, fuente y destino, y con la poca memoria que desee. En el primer paso, su fuente es el archivo original, en el último paso, el destino es el archivo de resultados.

En cada iteración:

leer desde el archivo de origen en un buffer deslizante un pedazo de datos de la mitad del tamaño del buffer;
ordenar todo el buffer
escriba en el archivo de destino la primera mitad del búfer.
desplazar la segunda mitad del búfer al principio y repetir

Mantenga un indicador booleano que indique si tuvo que mover algunos registros en la iteración actual. Si la bandera sigue siendo falsa, su archivo está ordenado. Si aparece, 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

Puede leer los archivos en partes más pequeñas, ordenarlos y escribirlos en archivos temporáneos. Luego lee dos de ellos secuencialmente de nuevo y los combina con un archivo temporal más grande, y así sucesivamente. Si solo queda uno, tiene su archivo ordenado. Básicamente, ese es el algoritmo Megresort realizado en archivos externos. Se escala bastante bien con archivos grandes aribitrary pero causa un poco de E / S de archivo adicional.

Editar: si tiene algún conocimiento sobre la posible variación de las líneas en sus archivos, puede emplear un algoritmo más eficiente (clasificación de distribución). Simplificado, usted leería el archivo original una vez y escribiría cada línea en un archivo temporal que toma solo líneas con el mismo primer carácter (o un cierto rango de primeros caracteres). Luego itere sobre todos los archivos temporales (ahora pequeños) en orden ascendente, ordénelos en la memoria y añádalos directamente al archivo de salida. Si un archivo temporal resulta ser demasiado grande para clasificar en la memoria, puede repetir el mismo proceso para esto basado en el segundo carácter en las líneas y así sucesivamente. Entonces, si su primera partición fue lo suficientemente buena como para producir archivos lo suficientemente pequeños, tendrá solo un 100% de sobrecarga de E / S sin importar qué tan grande sea el archivo, pero en el peor de los casos puede ser mucho más que con el tipo de combinación estable de rendimiento.

Puede usar el archivo db de SQL Lite, cargar los datos en el db y luego dejar que se ordene y devolver los resultados por usted. Ventajas: no necesita 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

Puede usar la siguiente estrategia de dividir y vencer:

Cree una función H () que pueda 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. Use esta función para dividir todos los registros en archivos separados que encajarán 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 tiene este archivo de entrada donde cada línea representa un registro

Alan Smith Jon Doe Bill Murray Johnny Cash

Solo construyamos H () para que use la primera letra del registro, por lo que puede obtener hasta 26 archivos, pero en este ejemplo obtendrá 3:

<file1> Alan Smith <file2> Bill Murray <file10> Jon Doe Johnny Cash

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

Tenga en cuenta que divide primero y solo conquista (ordena) más tarde. Sin embargo, asegúrese de hacer las particiones de 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 implementa la función de división H () depende en gran medida de la naturaleza de sus datos de entrada. Una vez que tenga esa parte resuelta, el resto debería ser muy fácil.

Sé que mencionaste que no usas una base de datos, no importa cuán ligero ... así que, quizás esta no sea una opción. Pero, ¿qué pasa con hsqldb en la memoria ... enviarlo, ordenarlo por consulta, purgarlo. Solo un pensamiento.

Si puede avanzar o retroceder en un archivo (buscar) y reescribir partes del archivo, entonces debe usar sort de burbuja .

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

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 forma, obtendrá todas las ventajas de una base de datos sin dependencias de infraestructura externas.

A pesar de su restricción, usaría la base de datos incrustada SQLITE3 . Al igual que usted, trabajo semanalmente con 10-15 millones de líneas de archivos planos y es muy, muy rápido importar y generar datos ordenados, y solo necesita un pequeño archivo 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