Cómo ordenar millones de filas de datos en un archivo con menos exigua memoria/

Question

(De here)

asistí a una entrevista la semana pasada y me hice esta pregunta:

¿Cómo ordenar un mil millones filas de datos en un archivo con solo 640 KB de memoria en una máquina basada en 8080 procesadores? Sin memoria virtual, sin disco externo.

Le pregunté explícitamente al entrevistador si podía usar un disco duro, por lo que puedo serializar árboles a medida que los ordené y luego los combiné al final. Él dijo no. Intenté de muchas maneras, diferentes algoritmos. Nada de lo que estuvo de acuerdo.

Me rendí y le pregunté educadamente, "¿cómo harías eso?" Dijo sin rodeos: "No te lo diría". (La entrevista terminó justo después de eso. No tenía intención de ofenderlo, como desarrollador, tenía curiosidad. Además, era una pregunta instintiva, tal como le preguntaría a cualquiera en mi lugar de trabajo)

Esta entrevista era para un banco realmente grande.

Entonces, ¿cómo alguien podría abordar este problema?

Answer 1

Si la velocidad no es un requisito, puede bubble sort filas en el archivo. Esto solo requiere mirar dos filas de datos a la vez, sin que se requiera información externa o almacenamiento.

Answer 2

No lo haría en C#, para empezar. ¿Estás seguro de que tienes esto etiquetado, verdad? Este es un problema C, si se puede resolver.

640K solo le ofrece 640 * 1024 * 8 bits, por lo que no hay forma de solucionar esto como enmarcado. Tal vez esa es la respuesta que estaba buscando. Estas entrevistas del Banco de inversiones son a veces un juego mental.

Answer 3

Heapsort sería mi consejo. Es relativamente rápido cuando n es grande, y solo tiene que mirar tres elementos con indecies definidas a la vez.

Habiendo dicho eso, mi intuición me dice que ordenar mil millones de filas en un 8080 incluso en C sería irrealmente lento.

Answer 4

¡Utilizaría la GPU! Incluso en una computadora rápida, the GPU is often faster at sorting. Y no sé cuán grandes son las "filas", pero no es difícil encontrar tarjetas de video de 1GB, por lo que también responde la pregunta de almacenamiento.

Además, si tuviera que trabajar en un 8080, definitivamente me gustaría poner la tarjeta gráfica más dulce que pude encontrar allí.

Solo tiene que estar preparado para la pregunta de seguimiento: "¿Cómo se consigue un 8080 para hablar con una tarjeta PCI Express 2.0 x16 moderna?". Descubrí un método verdaderamente maravilloso, pero este área de texto es demasiado limitado para contenerlo.

Answer 5

Knuth tiene una sección completa en external sorting; esto era algo común cuando no había unidades de disco duro & sin mucha memoria, y las unidades de cinta eran la norma. Mire la página de wikipedia, y/o vol. 3 del Arte de la Programación de Computadora de Knuth.

Estoy de acuerdo con el comentario de Robusto:

¿de dónde sacas el archivo desde si no se puede utilizar la unidad? Ciertamente no se guardará en la memoria.

No hay suficiente definición del problema.

Answer 6

Cuanto más pienso en esto, más creo que el tipo de combinación funcionaría muy bien en la ventana de memoria que se nos da.

Digamos que tiene x memoria disponible. Divida las mil millones de entradas en mil millones/x + 1 secciones y cúpelas (heapsort porque no se requiere memoria adicional y es O (2n (log n)) hora). Cuando todas las secciones estén ordenadas, realice un tipo de fusión que comience por los primeros elementos de todas las secciones. Esto funcionará siempre que tenga más de dos mil (mil millones) de memoria para trabajar con el uso de la memoria del sistema operativo básico 8080.

Haciendo los cálculos, esto supone que cada fila de datos es de menos de 165 bits.

Answer 7

Otra pregunta que se debe hacer es "¿Cuál es la naturaleza de las filas?" Si el número de valores distintos es suficientemente bajo, la respuesta podría ser pigeon hole sort.

Por ejemplo, supongamos que el archivo que se va a ordenar solo contiene filas que tienen un número entre 0 y 100 inclusive. Cree una matriz de 101 enteros sin signo de 32 o 64 bits con un valor de 0. Mientras lee una fila, úsela para indexar la matriz e incrementar el recuento de ese elemento. Una vez que se lee el archivo, comience en 0, lea el número de ceros leídos y escuche que muchos, vaya a 1, repita. Expanda el tamaño de la matriz según sea necesario para manejar el conjunto de números que llegan. Por supuesto, hay límites, digamos que los valores que se pueden ver abarcan desde -2e9 hasta + 2e9. Eso requerirá 4e9 contenedores, que no van a caber en 640K de RAM.

Si, por el contrario, las filas son cadenas, pero todavía está buscando un conjunto suficientemente pequeño de valores distintos, utilice una matriz asociativa o tabla hash para contener los recuentos.

Answer 8

Obviamente, debe poder leer y escribir en el archivo mil millones de filas. La restricción de ningún disco externo significa que debe restringirse a algoritmos en contexto o hacer algunas suposiciones sobre las condiciones de inicio y la distribución de datos para que pueda mantener los datos ordenados a medida que se agregan al archivo (por ejemplo, use la tecla como indexe y cree un archivo suficientemente grande para contener el número esperado de claves).

Si debe comenzar con un archivo no ordenado y ordenarlo, puede utilizar fusionar una clase de fusión in situ que funcione en fragmentos muy pequeños del archivo. Como no se hacen restricciones en los tiempos de acceso de los medios de almacenamiento, puede ser muy rápido.

Answer 9

Usted puede encontrar la discusión sobre un problema similar en Jon BentleyPerlas de programaciónColumn. 1. Aquí Bentley trata de un problema de clasificación de millones de códigos de área que están garantizados para ser único mediante el uso de una estructura de datos bitset.