Solo me pregunto por qué Javay .NET Frameworkutiliza diferentes algoritmos de clasificación por defecto.
En Java Array.Sort() usa el algoritmo Merge Sort por defecto y como dice Wikipedia.com :
En Java, los métodos Arrays.sort () usan una combinación de ordenación o una ordenación rápida ajustada dependiendo de los tipos de datos y, para la eficiencia de implementación, cambie a la ordenación por inserción cuando se ordenan menos de siete elementos de la matriz
En .NET Framework Array.Sort/List.Sort() usa la clasificación rápida como algoritmo de clasificación predeterminado ( MSDN ):
List.Sort () usa Array.Sort, que usa el algoritmo QuickSort. Esta implementación realiza una ordenación inestable; es decir, si dos elementos son iguales, su orden podría no conservarse. Por el contrario, una ordenación estable conserva el orden de los elementos que son iguales.
Al observar la gran tabla "Comparación de algoritmos" , podemos ver que ambos algoritmos tienen un comportamiento bastante diferente de las perspectivas de uso de la memoria y el caso más desfavorable:
Ambos Javay .NETson excelentes marcos para el desarrollo de soluciones empresariales, ambos tienen plataformas para el desarrollo integrado. Entonces, ¿por qué están usando diferentes algoritmos de clasificación por defecto, alguna idea?
Respuestas:
A pesar de lo deterministas que son las computadoras, la ingeniería informática no es una ciencia exacta. Dos personas, dado el mismo dominio del problema, realizarán un análisis y desarrollarán dos soluciones diferentes que satisfagan todas las limitaciones del problema. Puede ser difícil o imposible determinar empíricamente cuál de estos es "mejor" en el caso general.
Supongo que .NET QuickSort se superpone a algo en los MFC o la API de Windows, y probablemente se hereda de versiones mucho más antiguas de Windows, donde la ventaja de múltiples subprocesos de MergeSort ni siquiera se habría considerado para las computadoras de El dia. ( EDITAR: no lo es, aunque los desarrolladores de Microsoft han sido fanáticos de QuickSort durante mucho tiempo, como lo demuestra esta elección de implementación de clasificación desde MS-DOS).
Java, que no puede usar ninguna implementación específica de la plataforma porque Java fue diseñado desde cero para ser completamente independiente de la plataforma, fue de otra manera. Quién sabe por qué MergeSort salió en la cima; Mi conjetura es que la implementación ganó algún tipo de competencia de rendimiento en comparación con otros tipos que se les ocurrió a los desarrolladores, o que un MergeSort de espacio O (n) se veía mejor en papel en términos del mejor y el peor de los casos. (MergeSort no tiene el talón de Aquiles relacionado con la selección de elementos como QuickSort, y su mejor caso es una lista casi ordenada, mientras que a menudo eso es lo peor de QuickSort). Dudo que los beneficios de subprocesos múltiples se consideraron inicialmente, pero la implementación actual bien puede ser multiproceso.
fuente
List<T>.Sorten .NET usa un método nativo implementado en el CLR (si no usa un comparador personalizado), pero no tiene dependencias en las bibliotecas del sistema operativo.Diferentes equipos de desarrollo en dos compañías diferentes llegaron a conclusiones diferentes con respecto al caso de uso habitual para sus marcos y componentes y han decidido implementar en consecuencia.
Esencialmente, cada compañía hizo su análisis, miró a su base de clientes y tomó diferentes decisiones en consecuencia.
No puede esperar el análisis de diferentes compañías y equipos, utilizando diferentes suposiciones y datos sin procesar para llegar a la misma conclusión.
fuente
Esta pregunta está un poco desactualizada, ya que Java ahora usa Timsort (a partir de Java 7)
De los algoritmos específicos mencionados:
Quicksort tiene un rendimiento desfavorable en el peor de los casos en O (n ^ 2), pero es un poco más liviano / consume menos memoria, por lo que ofrece un mejor rendimiento en un caso típico.
Mergesort ha garantizado el rendimiento en el peor de los casos en O (n log n), pero conlleva un poco más de sobrecarga y requisitos de memoria. También es automáticamente estable (es decir, mantiene elementos iguales en el mismo orden).
En general, los diseñadores de Java parecen ser un poco más conservadores / centrados en lo "correcto", por lo que no es sorprendente que hayan elegido Mergesort entre los dos, ya que ofrece mejores garantías.
No estoy seguro de por qué Microsoft eligió Quicksort, ¿tal vez pensaron que los haría lucir mejor en algunos micro benchmarks?
fuente