it-swarm-es.com

Quicksort y no te molestes?

Especialmente al escribir aplicaciones de "estándar" (no HPC), ¿considera qué algoritmo de clasificación para elegir, o simplemente conformarse con Quicksort (que es lo que la mayoría de las bibliotecas simplemente llaman a Sort)? Hasta cierto punto, puede ser rentable en situaciones específicas, pero, por otro lado, la optimización adecuada requiere algún tiempo para analizar el problema y hacer puntos de referencia.

9
mbq

En general, utilizando los métodos predeterminados a menos que haya una necesidad específica de hacer algo más exótico, mantiene todo lo que sea mucho más legible/comprensible por la carretera, IMHO.

Si experimenta (o en algunos casos, sospechando firmemente) que tiene un problema de rendimiento que es el momento de agregar complejidad.

Por otro lado, si está utilizando un lenguaje lo suficientemente bajo que no hay un tipo incorporado para el tipo de objetos que necesita para ordenar, intente elegir uno o dos que cubran todas sus bases e implementen aquellas.

12
Bill

Siempre llame a las rutinas de la biblioteca proporcionadas, a menos que tenga mucha, muy buena razón para no hacerlo (y debe hacerlo documento por qué es así).

Esto se debe a que los algoritmos de clasificación son difíciles de obtener absolutamente. Hubo un error en el Java Quicksort con conjuntos de datos muy grandes, que se identificaron, fijaron y entregaron a los clientes por Sun, por lo que no tenía que hacerlo.

También el ordenado predeterminado en Java 7 ha sido actualizado a un nuevo, mejor clasificación. También de forma gratuita.

A menos que el tipo predeterminado sea Profundablemente, no sea lo suficientemente bueno para usted, quédate con él.

6
user1249

En una conferencia una vez escuché una bonita historia sobre esto.

En Microsoft, alguien estaba escribiendo A VB (c. VB 3) y envió un grupo de personas que dicen que tenía una carga de valores y los quería Aparecer en el ComboBox en orden, ¿cómo debe hacerlo?.

Todos se zambullieron por sus antiguos libros de texto de ciencias de la computación, mirando rutinas altamente eficientes y portarlas a lo visual básico y enviarlas por correo. One Guys acaba de enviar por correo "¿Cuántos valores en el Combobox?".

"Alrededor de 50" vino la respuesta.

"Solo ponga la propiedad ordenada en verdadero".

En el 99.9999% de la clasificación de instancias se realiza mejor utilizando una biblioteca, control o en la selección de SQL, ya que la diferencia de rendimiento entre la rutina de la biblioteca y cualquier cosa que escriba será insignificante y el esfuerzo y la sobrecarga de esfuerzo superarán de manera masiva las consecuencias.

3
Jon Hopkins

Este es el momento de eliminar la cita clásica sobre la optimización prematura. En la mayoría de los casos, realmente no importa. Diablos, con la velocidad de las CPUs en estos días, probablemente podría burbujear la mayoría de los conjuntos de datos y no se note mucho. Pero cuando está clasificando conjuntos de datos realmente grandes, y ordena el rendimiento, comienza a convertirse en un problema, entonces definitivamente debería ver otras opciones.

1
Mason Wheeler

Aunque obviamente no importa a los bits y los plazos de tiempo. Encuentro una especie de combinación para ser más fácil de escribir y comprender que QuickSort. Así que si voy a escribir mi propio algoritmo de clasificación, usaría eso.

0
Peter Turner

Al menos en una biblioteca escrita competentemente, espero que la incorporada sort se implemente implementada como introsort en lugar de solo un rápidoSort. La diferencia rara vez importa mucho, pero la introsort elimina el mal y el peor de los casos de Quicksort con un efecto mínimo en los casos más comunes.

Sin embargo, para responder a su pregunta: Sí, es para eso, por lo general, debe comenzar, y hasta que/a menos que tenga resultados de los perfiles que indiquen que es un problema, ahí es donde debe permanecer.

0
Jerry Coffin