C: Clasificación Métodos de Análisis

Question

Tengo un montón de diferentes algoritmos de ordenación que todos tienen la siguiente firma:

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH); 

¿Hay suites de pruebas de clasificación que podría utilizar para el propósito de hacer comparaciones empíricas?

Answer 1

sortperf.py tiene una suite bien seleccionada de casos de prueba de referencia y se utilizó para apoyar el ensayo encontró here y crea timsort la clase en Python lo que hace muchos años. Tenga en cuenta que, por fin, Java también puede estar cambiando a timsort, gracias a Josh Block (consulte here), así que me imagino que han escrito su propia versión de los casos de prueba de referencia; sin embargo, no puedo encontrar fácilmente una referencia lo. (timsort, una variante de mergesort natural estable, adaptativa e iterativa, es especialmente adecuada para lenguajes con semántica de referencia a objetos como Python y Java, donde el "movimiento de datos" es relativamente barato [ya que todo lo que se mueve son referencias, punteros, etc. , no blobs de tamaño ilimitado ;-)]], pero las comparaciones pueden ser relativamente costosas [[ya que no existe un límite superior a la complejidad de una función de comparación, pero esto se aplica a cualquier idioma en el que la clasificación se pueda personalizar a través de un método personalizado función de comparación o extracción de teclas]]).

Answer 2

El estudio definitivo de la clasificación es la disertación doctoral Bob Sedgewick. Pero hay mucha información buena en sus libros de texto de algoritmos, y esos son los dos primeros lugares en los que buscaría suite de pruebas y metodología. Si has tenido un curso reciente sabrás más que yo; La última vez que tuve un curso, el mejor método fue usar quicksort en particiones de tamaño 12, luego ejecutar la ordenación de inserción en toda la matriz. Pero las respuestas cambian tan rápido como el hardware.

Los libros Programming Perls de Jon Bentley tienen alguna otra información sobre clasificación.

Usted puede azotar rápidamente un conjunto de pruebas que contiene

• enteros aleatorios

• enteros Ordenado

• inversa ordenados enteros

• enteros organizados, ligeramente perturbado

Si la memoria sirve, estos son los casos más importantes para un algoritmo de ordenación.

Si está buscando ordenar matrices que no caben en la memoria caché, necesitará medir los efectos de la memoria caché. valgrind es efectivo si es lento.

Answer 3

Este sitio muestra los diversos algoritmos de ordenación por medio de cuatro grupos: http://www.sorting-algorithms.com/

Además de los cuatro grupos en la respuesta de Norman que desea comprobar los algoritmos de ordenación con la colección de números que tienen algunas similitudes en los números:

• Todos los números enteros son únicos
• el mismo entero en toda la colección
• pocas teclas únicos

Cambiar el número de elementos en la colección también es una buena práctica verificar cada algoritmo con 1K, 1M, 1G etc. para ver cuáles son las implicaciones de memoria de ese algoritmo.

Answer 4

This detailed discussion, además de vincular a un gran número de páginas web relacionadas que probablemente le resulten útiles, también describe un conjunto útil de datos de entrada para probar algoritmos de clasificación (consulte la página vinculada por razones).Resumiendo:

1. completamente reorganizado al azar array
2. Ya ordenados array
3. ya ordenados en array orden inverso
4. motosierra array
5. matriz de elementos idénticos
6. matriz ya ordenados con N permutaciones (con N del 0.1 al 10% del tamaño)
7. Matriz ordenada ya en orden inverso con N permutaciones
8. de datos que tienen distribución normal con duplicados de las llaves (o cerrar) (para la clasificación estable sólo)
9. datos pseudoaleatorios (valores diarios de S & P500 u otro índice para una década podría ser una buena prueba establecido aquí; Están disponibles en Yahoo.com)