Quicksort solo no es práctico para la ordenación externa , es decir, la ordenación de datos (generalmente, grandes volúmenes de datos) almacenados en el disco en lugar de la memoria principal. Quicksort requiere que todos los datos estén disponibles a la vez en la memoria, lo cual es imposible en este caso.
Las estrategias de clasificación externas suelen funcionar cargando (relativamente) pequeños fragmentos de datos en la memoria principal. Luego, estos fragmentos se ordenan de forma independiente (Quicksort es una buena opción para esto, ya que supera a otros algoritmos en prácticamente todos los casos). Luego, estos fragmentos ordenados se fusionan y se vuelven a escribir en el disco. Si no fusionamos todos los fragmentos a la vez, estos fragmentos se pueden combinar para obtener un fragmento ordenado más grande, y así sucesivamente, hasta que el archivo esté completamente ordenado. En lugar de la fusión bidireccional habitual (dos listas ordenadas se fusionan en una sola lista) que asociamos con la ordenación por fusión, podemos extender la idea a la fusión por vías k (por ejemplo, con k = 10).
Una idea crucial es que la fusión de k fragmentos no requiere que los datos completos de los fragmentos se carguen en la memoria. Podemos comenzar con los primeros 50 MB de registros en cada fragmento, por ejemplo, y comenzar a fusionarlos. Podemos cargar el resto de un fragmento, pieza por pieza, cuando se consuman los 50 MB de datos que hemos cargado (escritos en la lista combinada). Esto funcionará ya que la operación de merge siempre accede a las sublistas (fragmentos) secuencialmente.
- ¿Cuáles son algunas buenas implementaciones de un algoritmo evolutivo / genético en C / C ++?
- ¿Sigue siendo necesario convertir una solución dp memorable en una iterativa?
- Cómo escribir una matriz de distancia para el algoritmo Bellman Ford
- ¿Las empresas comerciales de algo funcionan mejor que las empresas comerciales que no son algo?
- ¿Obtendría algún beneficio resolviendo los problemas del Proyecto Euler por la fuerza bruta?
