Java.util.ArrayList.sort() algoritmo de ordenación

Question

Estaba buscando el código fuente del método sort() del java.util.ArrayList en grepcode. Parecen usar ordenación por inserción en arreglos pequeños (del tamaño < 7) y fusionar ordenación en arreglos grandes. Me preguntaba si eso hace una gran diferencia, ya que utilizan la ordenación por inserción solo para matrices de tamaño < 7. La diferencia en el tiempo de ejecución apenas se notará en las máquinas modernas.

He leído esto en Cormen:

Aunque ordenamiento por mezcla se ejecuta en O (n * log n) peor de los casos tiempo y ordenación por inserción se ejecuta en O (n * n) tiempo en el peor de los casos, la constante los factores en la ordenación por inserción pueden hacerlo más rápido en la práctica para tamaños de problema pequeños en muchas máquinas. Por lo tanto, tiene sentido engrosar las hojas de la recursión mediante el uso de ordenación de inserción dentro del tipo de combinación cuando los subproblemas son lo suficientemente pequeños.

Si hubiera diseñado algoritmo de ordenación por algún componente que requiero, entonces me gustaría considerar el uso de inserción de clasificación para mayores tamaños (quizá upto tamaño < 100) antes de que la diferencia en tiempo de ejecución, en comparación con el ordenamiento por mezcla , se vuelve evidente

Mi pregunta es ¿cuál es el análisis detrás de llegar al tamaño < 7?

Answer 1

La diferencia en el tiempo de funcionamiento apenas se notará en las máquinas modernas.

El tiempo que tarda para ordenar arreglos pequeños se vuelve muy importante cuando se da cuenta de que el algoritmo de clasificación general es recursiva, y el pequeño conjunto de clasificación es efectivamente el caso base de que la recursividad.

No tengo ninguna información interna sobre cómo se eligió el número siete. Sin embargo, me sorprendería mucho que eso no se haya hecho como resultado de comparar los algoritmos de la competencia en matrices pequeñas y elegir el algoritmo óptimo y el umbral en función de eso.

P.S. Vale la pena señalar que Java7 usa Timsort de forma predeterminada.

Answer 2

http://en.wikipedia.org/wiki/Timsort

"Timsort es un algoritmo de ordenación híbrido, derivado de la combinación de clasificación y ordenación por inserción, diseñado para funcionar bien en muchos tipos de datos del mundo real ... El algoritmo encuentra subconjuntos de los datos que ya están ordenado, y usa los subconjuntos para ordenar los datos de manera más eficiente. Esto se hace fusionando un subconjunto identificado, llamado ejecución, con ejecuciones existentes hasta que se cumplan ciertos criterios ".

Sobre el número 7:.

" ... Además, se ve que al galope es beneficioso sólo cuando el elemento inicial no es uno de los primeros siete elementos de la otra carrera Esto también se traduce en MIN_GALLOP está estableciendo a 7. Para evitar los inconvenientes del modo galopante, las funciones de fusión ajustan el valor de min-gallop. Si el elemento pertenece a la matriz actualmente en consideración (es decir, la matriz que ha estado devolviendo los elementos consecutivamente por un tiempo), el valor de min-gallop se reduce en uno. De lo contrario, el valor se incrementa en uno, lo que desalienta la entrada al modo galopante. Cuando se hace esto, en el caso de datos aleatorios, el valor de min-gallop es tan grande, que la entrada de vuelta al modo de galopamiento nunca se lleva a cabo.

En el caso en que se utiliza merge-hi (es decir, la fusión se realiza de derecha a izquierda), el galopante debe comenzar desde el extremo derecho de los datos, que es el último elemento. Galopar desde el principio también da los resultados requeridos, pero hace más comparaciones de las requeridas. Por lo tanto, el algoritmo para galopar incluye el uso de una variable que proporciona el índice en el que debe comenzar el galope. Por lo tanto, el algoritmo puede entrar en modo galopante en cualquier índice y continuar sobre él como se mencionó anteriormente, como en, comprobará en el siguiente índice que está desplazado por 1, 3, 7, ...., (2k - 1) .. y etc. del índice actual. En el caso de merge-hi, las compensaciones para el índice serán -1, -3, -7, .... "

Answer 3

Estoy publicando esto para las personas que visitan este hilo en el futuro y que documentan mi propia investigación . me encontré con este excelente enlace en mi búsqueda para encontrar la respuesta al misterio de la elección. 7:

Tim Peters’s description of the algorithm

usted debe leer la sección titulada "minrun Computing"

para dar una esencia, minrun es el tamaño de corte de la matriz debajo de la cual el algoritmo debería comenzar a usar la ordenación de inserción. Por lo tanto, siempre tendremos matrices ordenadas de tamaño "minrun" en el que necesitaremos ejecutar la operación de fusión para ordenar toda la matriz.

En java.util.ArrayList.sort(), "minrun" se elige para ser 7, pero según mi comprensión del documento anterior, se rompe ese mito y muestra que debe estar cerca de los poderes de 2 y menos de 256 y más de 8. Citando del documento:

En 256, el costo del movimiento de datos en la ordenación de inserción binaria duele claramente, y en 8 el aumento en el número de llamadas a la función duele claramente. Escoger algunos potencia de 2 es importante aquí, de modo que las fusiones terminen perfectamente equilibradas (ver la siguiente sección).

El punto que estoy haciendo es que "minrun" puede ser cualquier potencia de 2 (o cerca de la potencia de 2) menos de 64, sin obstaculizar el rendimiento de TimSort.