c++ - trabajo - preguntas para una entrevista google

Rompecabezas de la entrevista: ordenando una entrada de un millón de números con memoria limitada

Question

Intenté responder a esto usando una clasificación externa, pero el entrevistador respondió que la complejidad era alta nn (log (n)), es decir, n cuadrado * logn. Hay una mejor alternativa.

Para simplificar la pregunta: Supongamos que tenemos 1000 elementos para ordenar con espacio asignado solo para 100 elementos. ¿Cuál es el mejor algoritmo que tomará menos tiempo que el tipo externo?

Answer 1

La forma estándar de hacerlo es una clasificación externa .

En el orden externo, no solo es importante tener la O(nlogn) sino que también es fundamental minimizar al máximo las lecturas / escrituras del disco, y hacer las más leídas y escritas de forma secuencial (y no aleatoria), ya que el acceso al disco es mucho más eficiente cuando se hace de forma secuencial.

La forma estándar de hacerlo es de hecho un tipo de combinación k-way, como sugirió @JanDvorak, pero hay algunas fallas y además de la sugerencia que intento corregir:

1. En primer lugar, al hacer una RS (Replacement-Selection) en la entrada disminuye el número de "runs" iniciales (número de secuencias en aumento) y, por lo tanto, generalmente disminuye el número total de iteraciones necesarias para el tipo de fusión posterior.
2. Necesitamos memoria para el almacenamiento en búfer (lectura y escritura de entrada); por lo tanto, para tamaño de memoria M y tamaño de archivo M * 10, no podemos fusionar en 10 direcciones; se generarán MUCHOS discos de lectura (leyendo cada elemento, en lugar de en bloques).
   La fórmula estándar para k - el "orden" de la fusión es M/(2b) (donde M es el tamaño de su memoria, y b es el tamaño de cada "búfer" (generalmente bloque de disco).
3. Cada paso de clasificación de fusión se realiza leyendo las entradas de cada "ejecución" generada en la iteración anterior, llenando M/2 en la memoria. El resto de la memoria es para "predicción" (que permite un trabajo continuo con espera mínima para IO), que solicita más elementos de una ejecución y para el búfer de salida, para garantizar el derecho secuencial en bloques.
4. El número total de iteraciones con este enfoque es log_k(N/(2M)) donde k es el número de ejecuciones (calculado previamente), M es el tamaño de la memoria y N es el tamaño del archivo. Cada iteración requiere 1 lectura secuencial y 1 escritura secuencial del archivo completo.

Dicho eso, la proporción de file_size / memory_size suele ser MUCHO más que 10. Si solo está interesado en una proporción de 10, pueden realizarse optimizaciones locales, pero no es para el caso más común donde file_size/memory_size >> 10

Answer 2

No sé qué tipo externo (o el entrevistador) quiere decir, pero

mi sugerencia es una fusión de 10 vías (en su caso):

• Divida el archivo en fragmentos de tamaño MAX_MEM (100 elementos)
  • esto es O(1)
• Clasifica cada fragmento en la memoria y almacena como un archivo separado
  • esto es O((n/max_mem) * (max_mem) log(max_mem))) = O(n log(max_mem))
• Abra todos los fragmentos como flujos de elementos
• Combine todas las secuencias seleccionando el elemento más bajo en cada paso.
  • esto es O(n log(n/max_mem)) usando un minHeap o O(n^2/max_mem) trivialmente (puede ser más rápido en la práctica)
• Eliminar los trozos

Con respecto al cálculo, esto es O(n (log(max_mem)+log(n/max_mem))) = O(n log(n))

Con respecto a la E / S de disco, si toda la fusión se realiza en una sola pasada, esto es 2*n lee y 2*n escribe solamente . De manera más general, es (1+[depth of the merge tree])*n

Todas las escrituras son secuenciales. La primera lectura es secuencial, la segunda es secuencial, intercalada de 10 archivos.

Si hubiera muchos más datos, necesitaría fusión repetida o recursiva (100 por porción, luego escoja N pedazos repetidamente). En este punto, vale la pena reemplazar el paso de división + clasificación con Reemplazo / Selección como se describe en la respuesta de @ amit, especialmente cuando los datos ya están casi ordenados (puede evadir por completo el paso de fusión).

Tenga en cuenta que una mayor N puede aumentar el cálculo (muy levemente, si usa las estructuras correctas), pero reduce significativamente la cantidad de E / S del disco (hasta una cierta cantidad; si combina demasiados fragmentos a la vez, puede quedarse sin memoria para los búferes de lectura, lo que provoca lecturas innecesarias). La E / S de disco es costosa, los ciclos de CPU no lo son.

Answer 3

Tal vez el entrevistador esperaba que preguntaras: ¿Son esos números los números únicos de siete dígitos mencionados por J. Bentley ( Cracking the Oyster )?