Análisis de rendimiento y estadísticas de la ordenación de vectores.
¿Cuál es el mejor o el más rápido algoritmo de ordenación?, pues depende de lo que queramos ordenar y cómo representemos los resultados en las estadísticas. Normalmente se utiliza el análisis de complejidad asintótica para distinguir entre los distintos tipos de la misma complejidad Ω, O y Θ, pero esto no ayuda a diferenciar algoritmos que estén dentro de una de ellas. Lo más tangible es utilizar una aproximación empírica y esto es lo que se recoge en este artículo.
Cómo se ha hecho.
Los algoritmos se han escrito en lenguaje Java con las instrucciones más elementales posibles. ¿Por qué?, por su mayor implantación, es de libre disposición (que pena que lo tenga una multinacional), en España se presentó en 1.995 evento que disfruté, actualmente es tan rápido como los lenguajes compilados, se actualiza constantemente y tiene muchas herramientas de apoyo, también de libre disposición. Por otro lado, me encuentro cómodo, aunque en otros mundos haya utizado y tenido más experiencia (Bal, Basic, Cobol, C, 4GL, …). Quizás alguno de los algoritmos pueda ser mejorable, si es el caso enviar vuestra aportación.
Volviendo a los algoritmos, al implemetarlos empiezan a depender de las características específicas del propio lenguaje, los resultados también dependen de los valores a ordenar, de la cantidad de elementos, el tamaño de sus valores, rango, ordenación previa, tipo de dato, etc..
Los vectores (Datos numéricos enteros) están agrupados en base a:
- Vectores aleatorios.
- Vectores ordenados
- Los elementos están ordenados en la dirección que trata el algoritmo. “Si nos piden esto, alguien se ha equivocado “.
- Los elementos están ordenados en la dirección contraria que trata el algoritmo. “Otro despiste, ver Lectura inversa de un fichero“.
- Los elementos están ordenados con forma de “dientes de sierra”, los ficheros que lo componen se concatenaron en vez de fusionarse.
- Los elementos están parcialmente ordenados.
- Para las situaciones anteriores.
- Se utilizan distintos tamaños.
- Se utiliza un rango de valores amplios o cortos que provocan repeticiones.
Los identificaremos como:
| 1 -1000 | 100M | Asc. | Des. | Sierra | Parcial |
| Vector generado aletoriamente con valores enteros de 1 a 1.000. | Vector generado aletoriamente con valores enteros de 1 a 100 millones. | Vector ordenado ascendentemente. | Vector ordenado descendentemente. | Vector ordenado en dientes de sierra con cinco cumbres no consecutivas. | Vector ordenado parcialmente en un 40%. |
Todos ellos contienen un número de elementos variable por cada prueba. La ordenación por algoritmo se realiza 6 veces (vectores distintos) y se obtiene una media aritmética. Para todas las pruebas el criterio que se ha elegido es el de ordenamiento ascendente.
El equipo, un I5-2540M con 8GB de RAM, disco SSD, S.O. de 64 bits y paciencia con los vectores grandes. En pocos años los resultados estarán obsoletos, es obvio pero ese no es el interés, la proporcionalidad de los resultados es lo que nos interesa, si ahora un resultado respecto a otro está en un 20% de diferencia, seguro que dentro de unos años, con mejores medios técnicos, la diferencia será del mismo 20%.
Los tiempos sólo se corresponden con la ejecución del algoritmo, el vector está en memoria (ordenación interna), la generación, comprobación de la ordenación, obtención de asimetrías, aleatoriedad, etc. están fuera del cómputo. El equipo no tiene conexión a red y no se ejecuta ningún otro proceso que no sea del S.O.
La elección del volumen de elementos para procesos “normales”, ahora no existe. La normalidad a partir del siglo XXI y a este respecto, es muy relativa, la que he elegido es de 10 elementos y hasta 50 millones.
Condicionantes.
Aleatoriedad.
La inmensa mayoría de las pruebas que se publican están realizas con datos obtenidos de forma aleatoria. La posible repetición de valores y su proporción modifican los resultados, cuanto mayor sea el rango (máximo en las pruebas de este artículo,100 millones), menor es su incidencia para algunos algoritmos. Por otro lado, la aleatoriedad puede darnos pistas de cuál es el algoritmo que más nos interesa, cuanto mayor es la fluctuación mayor será la incertidumbre. Para los siguientes gráficos, recordamos, se han realizado varias ejecuciones por algoritmo con vectores aleatorios independientes, se tomó el promedio. Las diferencias que se muestran indican que el tamaño (cantidad de elementos) para algunos sí importa.
Asimetría.
En la generación de los vectores se producen sesgos (Asimetrías) que influencian los resutados obtenidos. Los valores de la asimetría, en la distribución de los valores, nos proporcionan una visión de cuál puede ser el cambio en el rendimiento del algoritmo. Los valores de los elementos sesgados hacia la derecha (valores más altos) tienen un sesgo negativo, mientras que los datos sesgados hacia la izquierda (valores más bajos) tienen sesgo positivo. Con estos datos no sólo tenemos la asimetría, sino en cuál dirección están sesgados los datos. 
Entropía.
También podemos estudiar los valores de la entropía. Si la entropía es pequeña, entonces el conjunto esta muy ordenado. Si la entropía es grande, entonces el conjunto esta muy desordenado.
Los gráficos de asimetría se corresponden directamente con los vectores utilizados en las pruebas.
? Pulsar sobre los gráficos para verlos a tamaño real.
Gráficos de Rendimiento.
Desde 10 a 1.000.000 de elementos.
? Pulsar sobre los gráficos para verlos a tamaño real.
Desde 10.000.000 a 50.000.000 de elementos.
? Pulsar sobre los gráficos para verlos a tamaño real.
Observaciones finales.
Sorpresivamente, muchos de los algoritmos que han sido recomendados a lo largo del tiempo son más lentos que otros expuestos en este artículo. Le he estado dando vueltas y me estraña que nadie se haya fijado en la diversidad de condiciones y se fuera por el camino más fácil, “seguir la corriente”. A partir de ahora la frase que debería seguir a cualquier comparación sería: “depende de lo que estemos buscando, nos interesará este u otro”. Me he encontrado expresiones como estas:
“Cuando la entrada es aleatoria, el ordenamiento Quicksort es el mejor algoritmo”. Pues no exactamente, Flashsort mejora sus resultados en 4 de las 6 pruebas, para grandes cantidades Bucket, Casillero o Countig lo devoran.
“Timsort es el que se tomará como estándar”. A mí me ha defraudado, puede que esté como algoritmo base de ordenación en algún lenguaje, pero los resultados no son tan óptimos. Uno poco nombrado es Shellsort y ofrece el mismo rendimiento que él.
Quizás lo mejor será que cada uno evalue los algoritmos y resultados que ve, o espera en función de sus necesidades, más que lo cuente desde mi perspectiva. Los datos son los que son, los algoritmos ahí están y no existe predilección por ninguno.