Ordenando datos más grandes que el tamaño de RAM

Question

Esta es una pregunta de la entrevista de Google: Dadas 2 máquinas, cada una con 64 GB de RAM, que contienen todos los enteros (8 bytes), ordena los datos completos de 128 GB. Puede suponer una pequeña cantidad de RAM adicional. Extiéndalo para clasificar los datos almacenados en 1000 máquinas.

Se me ocurrió una clasificación externa. En eso, dividimos todos los datos en fragmentos y utilizamos el tipo de combinación en ellos. Ese es el primero que ordena los trozos y los vuelve a colocar y los vuelve a juntar en pedazos y fusionarlos. ¿Hay una mejor manera? ¿Cuál sería la complejidad?

Answer 1

Cada uno de los 64 GB se puede ordenar usando un quicksort por separado y luego usando la memoria externa para mantener los punteros en las cabezas de ambos 64GB. Consideremos que queremos RAM1 y RAM2 en ese orden para tener todos los datos, seguir aumentando puntero en RAM1 si es más pequeño que el valor del puntero en RAM2; de lo contrario, cambie el valor con RAM2 hasta que el puntero llegue al final de RAM1.

tome el mismo concepto para ordenar todas las N RAM. Toma pares de ellos y ordena usando el método anterior. Te quedan N/2 RAM clasificadas. Usa el mismo concepto arriba recursivamente.

Answer 2

ChingPing propone un orden O (n log n) para cada subconjunto, seguido de una fusión lineal (mediante el intercambio de los elementos). El problema con Quicksort (y la mayoría de los n log n géneros es que requieren n memoria. En su lugar, recomendaría usar un SmoothSort que utiliza memoria constante, aún se ejecuta en O (n log n).

Lo peor de los casos es donde usted tiene algo así como:.

setA = [maxInt .. 1] 
setB = [0..minInt] 

donde ambos conjuntos están ordenados a la inversa, pero luego de la fusión está en el orden inverso

el - explicación (OMI más clara) de la solución de ChingPing es :

Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array 
While setA's pointer is not at the end 
    if (setA[pointerA] < setB[pointerB]) 
    then { pointerA++; } 
    else { swap(setA[pointerA], setB[pointerB]); pointerB++; } 

Los conjuntos deberían estar ahora ordenados.

Answer 3

Ya hay respuestas para la carcasa de la máquina 2.

Supongo que los 128 GB de datos que se ordenarán se almacenan como un único archivo en un único disco duro (o cualquier dispositivo externo). No importa cuántas máquinas o discos duros se utilicen, el tiempo que lleva leer el archivo original de 128GB y escribir el archivo ordenado de 128GB sigue siendo el mismo. El único ahorro se produce durante los géneros basados ​​en RAM internas para crear fragmentos de datos ordenados. El tiempo que lleva fusionarse con n + 1 discos duros para hacer una fusión de n vías en un único archivo ordenado de 128 GB en el disco duro restante sigue siendo el mismo, limitado por el tiempo que lleva escribir el archivo ordenado de 128 GB en el restante disco duro.

Para n máquinas, los datos se dividirían en trozos de 128 GB/n. Cada una de las máquinas podría alternar la lectura de subunidades, tal vez 64 MB a la vez, para reducir la sobrecarga de acceso aleatorio, de modo que la "última" máquina no esté esperando que todas las máquinas anteriores lean todos sus fragmentos antes incluso de que comience .

Para n máquinas (64GB ram cada una) y n + 1 discos duros con n> = 4, cada máquina puede usar una ordenación de radix con O (n) complejidad de tiempo para crear fragmentos de 32 GB o menores en n discos duros al mismo tiempo, seguidos de una combinación de n vías en el disco duro de destino.

Hay un punto de rendimientos decrecientes que limita el beneficio de n mayor. En algún lugar más allá de n> 16, el rendimiento de fusión interna podría ser mayor que el ancho de banda de E/S del disco.Si el proceso de fusión está vinculado a la CPU en lugar de a la E/S, existe una compensación en la sobrecarga de la CPU durante el tiempo que lleva crear fragmentos en paralelo frente a la sobrecarga de fusión mayor que el tiempo de E/S.