¿Algún buen algoritmo de clasificación para datos ordenados en su mayoría que no encajan todos en la memoria?

Question

En caso de que se les da:

• cierta cantidad de datos
• memoria con el tamaño medio del tamaño de los datos
se ordena
• parte de los datos
• usted no sabe el tamaño de la ordenada datos.

¿Qué algoritmo de clasificación elegirías? Estoy debatiendo entre inserción y quicksort. Sé que el mejor caso para la ordenación por inserción es O (n), pero el peor caso es O (n). Además, teniendo en cuenta el hecho de que la memoria es limitada, dividiría los datos en dos partes, y en cada uno de ellos haga una búsqueda rápida, luego combine todo junto. Tomará O (n) tiempo para dividir los datos, O (n) para fusionar los datos, y O (n log n) para ordenar los datos usando quicksort, para un tiempo de ejecución neto de O (n log n).

¿Alguien tiene alguna sugerencia sobre cómo mejorar esto?

Answer 1

Su enfoque tipo mergesort parece muy razonable. Más generalmente, este tipo de algoritmo de clasificación se llama external sorting algorithm. Estos algoritmos a menudo funcionan como usted ha descrito: cargue algún subconjunto de datos en la memoria, oriéntelos y luego vuelva a escribirlos en el disco. Al final, use un algoritmo de fusión para fusionar todo nuevamente. La elección de cuánto cargar y qué algoritmo de ordenamiento usar son usualmente las preocupaciones dominantes. Me centraré principalmente en la elección del algoritmo de clasificación.

Sus preocupaciones sobre el peor de los casos de comportamiento del quicksort son hablando en general nada de qué preocuparse, ya que si elige el pivote aleatoriamente la probabilidad de que obtenga un tiempo de ejecución realmente malo es baja. La estrategia de pivote aleatorio también funciona bien incluso si los datos ya están ordenados, ya que no tiene entradas para el peor de los casos (a menos que alguien conozca su generador de números aleatorios y la semilla). También puede usar una variante de quicksort como introsort, que no tiene el peor de los casos, como algoritmo de clasificación para evitar este peor caso.

Dicho esto, ya que sabe que los datos ya están parcialmente ordenados, es posible que desee consultar un adaptive sorting algorithm para su paso de clasificación. Mencionó la ordenación por inserción para esto, pero hay algoritmos adaptativos mucho mejores. Si la memoria es escasa (como ha descrito), puede intentar buscar en el algoritmo smoothsort, que tiene el tiempo de ejecución del mejor de los casos O (n), el tiempo de ejecución del peor caso O (n log n) y solo utiliza O (1) memoria. No es tan adaptativo como otros algoritmos (como el de Python timsort, natural mergesort o Cartesian tree sort), pero tiene un menor uso de memoria. Tampoco es tan rápido como un buen quicksort, pero si la mayoría de los datos están realmente ordenados, puede funcionar bastante bien.

Espero que esto ayude!

Answer 2

En vista de ello, dividiría & conquer con quicksort y lo llamaría un día. Muchos problemas de algoritmos están sobre pensados.

Ahora, si tiene datos de prueba con los que trabajar y realmente quiere comprender eso, coloque una clase abstracta en el centro y en el punto de referencia. Podemos rodearlo todo el día, pero sabiendo que los datos ya están parcialmente ordenados, tendrá que probar. Los datos ordenados generan el peor de los casos en la mayoría de las implementaciones de quicksort.

Considere que hay many sorting algorithms y algunos se adaptan mejor a los conjuntos ordenados. Además, cuando sabe que un conjunto está ordenado, puede fusionarlo con otro conjunto en n tiempo. Por lo tanto, la identificación de trozos de datos ordenados primero puede ahorrarle mucho tiempo al comparar la suma de un único paso (n) y reduciendo en gran medida las posibilidades de que la línea rápida pase a (n) vez.