¿Cómo se clasifican mil millones de filas de datos de enteros (unos pocos gigabytes) en un archivo con solo 1024 KB de memoria principal? Cazar Trabajos es un oficio

No tiene sentido declarar lo obvio que no va a encajar todo dentro de la memoria y ordenarlo allí, ¿verdad?

Muy bien, expongamos algunas suposiciones: estamos tratando con enteros de 64 bits aquí. Además, el prefijo ‘K’ en ‘KB’ es en realidad un kibibyte , porque así es como típicamente nos referimos a la memoria de acuerdo con los estándares de memoria JEDEC, por lo que tenemos 1,048,576B de memoria.

Dentro de esa porción, podemos almacenar 131,072 de esos enteros. Bueno, dado que necesitamos un poco de memoria para el código que hará la clasificación, así como también el código de biblioteca estándar, la pila y el montón, los asignadores, etc., supongamos que podemos acomodar alrededor de 100,000 de estos enteros.

Entonces, ¿cuál es el primer paso? ¿Sería útil si pudiéramos cargar todo lo que podamos, ordenar solo ese flujo y derramarlo? Por supuesto que sí, así que aquí hay un pseudocódigo que hace eso:

  const int stream_size = 100000;
 int stream_id = 0;

 while (! file.eof ()) {
	 // Lee hasta 100,000 entradas
	 int [] data = file.readInt (stream_size);

	 ordenar (datos);

	 // Derrame los datos en memoria.  Stream aquí es básicamente
     // un identificador de archivo glorificado.
	 stream = spill_stream (datos, stream_id ++);

	 // Almacenar la referencia a la secuencia ordenada en una cola.
	 input_queue.push (corriente);

	 // Libera los recursos.
	 libre (datos);
 }

Después de este paso, tenemos 10,000 archivos que contienen cada uno 100,000 enteros ordenados. ¿Es malo que lo hagamos en un solo hilo? Claro que sí, y obviamente podemos hacerlo mejor.

Ahora, para el siguiente paso, comencemos a fusionar esos archivos. Idealmente, deberíamos tener varios hilos masticando los datos. Dado que las secuencias son del mismo tamaño, estimamos que los subprocesos tendrán tiempos de ejecución similares, si permitimos que cada uno combine un par de secuencias.

El algoritmo para esta fase podría definirse como sigue. En cada punto, cada subproceso fusionará un par de secuencias de entrada en una única secuencia de salida, si hay al menos dos secuencias en la cola de entrada. De lo contrario, el flujo único restante se moverá a la cola de salida para su procesamiento en una etapa posterior, después de que todos los hilos hayan finalizado el procesamiento, por un solo hilo elegido. Antes del comienzo de la siguiente etapa, las colas se intercambiarán: la cola de salida ahora está llena de secuencias y se convertirá en la cola de entrada para la siguiente etapa, mientras que la cola de entrada para esta etapa se ha agotado y servirá como la cola de salida para la siguiente etapa, y seguimos haciendo ping-pong así hasta que tengamos una sola secuencia de salida.

En la práctica, en la primera etapa, comenzamos con 10,000 flujos de entrada, cada uno de los cuales tiene 100,000 elementos (enteros) de largo. Independientemente de cuántos subprocesos tengamos, al final de la primera etapa, la cola de salida tendrá 5.000 secuencias, cada una de las cuales tendrá una longitud de 200.000 enteros.

Después de la etapa 2, tendremos 2,500 transmisiones de 400,000 enteros.
Después de la etapa # 3, 1,250 transmisiones de 800,000 enteros.
…

Después de la etapa # 14, habrá un flujo de salida único de 1,000,000,000 de enteros. ¿Por qué 14? Lo dejo como ejercicio al lector.

Entonces, lo que está haciendo cada subproceso podría volver a escribirse en pseudocódigo como algo así:

  // Al final de cada etapa, intercambiamos colas de entrada y salida.
 // El tamaño de la cola de entrada en este punto es el tamaño de
 // cola de salida después de que se haya completado la etapa anterior, por lo que rompemos
 // cuando hemos tenido una secuencia de salida única en la etapa anterior.
 while (input_queue.size ()> 1) {

     // Siempre que veamos un par de secuencias en la cola de entrada
     // Tenga en cuenta que esto está demasiado simplificado, la comprobación de tamaño y aparece 
     // tendría que ejecutarse atómicamente.
     while (input_queue.size ()> = 2) {
         // Toma un par de secuencias de la cola
         stream_left = input_queue.pop ();
         stream_right = input_queue.pop ();

         // Crear una secuencia de salida
         output_stream = Stream.newStream ();

         fusionar (stream_left, stream_right, output_stream);

         output_queue.push (output_stream.filename);
     }

     // Espera a que todos los hilos terminen su trabajo en esta etapa
     sync_point.wait ();
     
     if (this.is_leader_thread ()) {
         // Intercambia referencias a colas de entrada y salida.
         swap_ref (input_queue, output_queue);
     }
 }

Tenga en cuenta que la operación de fusión requiere O (1) de memoria adicional, por lo que no hay presión de memoria oculta allí.

Nuevamente, si crees que hay formas de mejorar esto, no estás equivocado. Un defecto obvio es el hecho de que inicialmente estamos clasificando en un solo hilo. Si no estuviéramos tan ansiosos por elegir el tamaño de nuestra transmisión para que sea lo máximo posible y si estuviéramos conscientes del hecho de que tenemos múltiples subprocesos a nuestra disposición, podríamos haber tenido subprocesos que cargan los datos en paralelo (por, digamos, virtualmente paginación del archivo de entrada) y luego ordenar los datos localmente, en la memoria, el derrame de las secuencias. Sí, tendríamos muchas más transmisiones, pero serían más cortas y el tiempo de ejecución general no aumentaría. Además, si pudiéramos cargar ambas secuencias en la memoria, podríamos ejecutar el paso de fusión más rápido y con menos comparaciones.

Entonces, aunque no es el algoritmo perfecto, este sería el borrador de cómo abordaría el problema. Si se trata de una pregunta de entrevista, puede comenzar fácilmente con una implementación más simple y de un solo subproceso, luego avanzar hasta una solución paralela, dependiendo de qué tan seguro esté con el paralelismo y las características específicas de su idioma de elección. Creo que comprender bien el paralelismo es importante (y será cada vez más importante) en el mundo de hoy (y del mañana, especialmente para este tipo de problemas que giran en torno al procesamiento de grandes datos).

Los puntos clave para llevar son:

dividir la entrada en fragmentos (no arbitrarios) que le permiten dividir y conquistar (y paralelizar)
ordenar tanto como sea posible en la memoria, luego volver al disco
fusionar en etapas, un par a la vez, luego derramar
colas de flujo de entrada / salida de ping-pong
¡paralelismo!

AlgoritmoAlgoritmosProgramación de entrevistas