Ordenar archivo 1TB en la máquina con 1 GB de RAM

Question

Esta pregunta parece fácil, pero no puedo entender el verdadero trabajo detrás de ella. Sé que la gente dirá, divide en trozos de 512 Megs y clasifícalos como si usaras Merge Sort usando Map reduce.

Así que aquí es la pregunta real que tengo:

Supongamos que romper el archivo en 512 megas trozo y luego enviar a diferentes máquinas host para ordenarlos. suponga que estas máquinas usaron Merge Sort. Ahora digamos, tenía 2000 máquinas cada una clasificada 2000, 512 megas de trozo. Ahora cuando los vuelvo a fusionar, ¿cómo funciona eso? ¿El tamaño no seguirá aumentando de nuevo? Por ejemplo, fusionar dos 512 megas hará 1024Megs, que es el tamaño de mi RAM, ¿cómo funcionaría esto? Cualquier máquina no puede fusionar un trozo de más de 512 megas con otro trozo porque entonces el tamaño> 1 GB.

Cómo al final de la fusión alguna vez podré unir dos trozos de 0.5 TB con otro trozo de 0.5 TB. ¿Entra aquí en juego el concepto de Memoria Virtual?

Estoy aquí para aclarar mis conceptos básicos y espero hacer esta pregunta tan importante (correctamente) correctamente. Además, ¿quién debería hacer esta fusión (después de la clasificación)? ¿Mi máquina o algunas de esas 2000 máquinas?

Answer 1

Aquí hay una manera teórica que debería funcionar. Supongamos que tiene sus archivos 2000 512mb listos para crear un archivo de 1TB.

Si simplemente recorre todos los archivos, busque cuál tiene el valor FIRST más bajo, luego muévalo a su archivo de destino y repita, luego terminará con todo en orden. El uso de RAM debe ser pequeño, ya que nunca será necesario abrir más de una línea a la vez.

Obviamente, debe poder optimizar esto: mantenga la primera línea de cada archivo en la RAM sobre la marcha y debería ser algo más rápido.

Answer 2

La versión corta de cómo combinar es así:

1) Se crea una tabla con una ranura para cada máquina está fusionando a partir.

2) Solicite a cada máquina la entrada más baja que tengan y que todavía no le hayan asignado.

3) Elimina la entrada de menor valor de su tabla, la envía y le pide a esa máquina que rellene el lento con la entrada más baja que todavía no le ha asignado, dejando la ranura vacía si la máquina está sin entradas .

4) Repite el paso 3 hasta que la tabla esté vacía.

Esto le permite combinar desde N máquinas que almacenan solo N entradas a la vez. Por supuesto, puede optimizarlo trivialmente para mantener M entradas de cada máquina. En ese caso, debe almacenar las entradas N * M, y cuando una ranura esté vacía, solicite a esa máquina M entradas para volver a llenarla.

Answer 3

Lo bueno de un tipo de combinación es que no necesita acceso aleatorio; acceso secuencial va a hacer. Eso es lo que lo convierte en una solución perfecta cuando el conjunto de datos no cabe en la memoria.

Una sola pasada de fusión requiere 2 (o más) entradas y produce una salida. Simplemente sigue combinando entradas en salidas hasta que solo quede un archivo.

Answer 4

Ahora digo, tenía 2000 máquinas cada una clasificada 2000, 512 megas de trozo.Ahora cuando los vuelvo a unir, ¿cómo funciona eso? ¿No seguirá aumentando el tamaño en ? Por ejemplo, fusionar dos 512 megas hará 1024Megs , que es el tamaño de mi RAM, ¿cómo funcionaría? Cualquier máquina no puede fusionar un trozo de más de 512 megas con otro fragmento porque y luego tamaño> 1 GB.

Así no es como funciona una implementación práctica de mergesort. Lo bueno de mergesort (y los algoritmos de clasificación relacionados) es que no necesita tener todo el conjunto de datos en la memoria para que funcione. Cuando se fusiona, solo necesita leer en la memoria una pequeña parte del archivo a la vez, que luego se escribirá pronto.

En otras palabras, no necesita acceso aleatorio para mergesort. Si no fuera por esta agradable propiedad, sería imposible sort the data on tape drives con la tecnología disponible en ese momento. Las unidades de cinta no son, por supuesto, medios de acceso aleatorio y la RAM en aquel entonces se midió en kilobytes.

Answer 5

Este problema puede ser reducido a un problema más simple. Este problema fue diseñado para forzarte a un acercamiento. Aquí está:

• Recoger trozos = ~ 1GB, ordenar & almacenarlos como archivos separados separados.
• Usted termina con 1000 archivos clasificados 1GB en el sistema de archivos.

• Ahora, es simplemente un problema de combinar matrices clasificadas k en una nueva matriz.

  La combinación de matrices ordenadas k necesita que mantenga un min-heap (cola de prioridad) con k elementos a la vez.

es decir k = 1000 (archivos) en nuestro caso. (1 GB ram puede almacenar 1000 números)

Por lo tanto, siga sacando elementos de la cola de prioridad y guárdelos en el disco.

Tendrá un nuevo archivo, ordenado en tamaño de 1TB.

Consulte: http://www.geeksforgeeks.org/merge-k-sorted-arrays/

actualización

PS: se puede realizar en una sola máquina con 1 GB de RAM con una mejor estructura de datos

Merge se puede hacer en menos de O (N) espacio con cola de prioridad es decir O (K) espacio es decir, el corazón del problema.