Librerías para ordenar listas en JavaScript

La ordenación de listas es una tarea compleja, especialmente a medida que crece el tamaño de estas. En JavaScript existe el método nativo sort() que nos permite ordenarlas, pero no muestra un gran rendimiento con listas relativamente grandes. Por eso en NPM existe una interesante colección de librerías para ordenar listas en JavaScript. A continuación, vamos a comparar el rendimiento que ofrecen tres de ellas a la hora de ordenar listas de reales de diferentes longitudes.

Librerías analizadas

En esta entrada se van a comparar el rendimiento de tres librerías para ordenar listas en JavaScript y el método estándar. Las librerías que vamos a analizar y se pueden encontrar fácilmente en NPM son

• array-sort (versión 1.0.0)
• fast-sort (versión 2.2.0)
• timsort (versión 0.3.0)

Proceso de comparación

Para comparar el rendimiento de cada una de las librerías se va a crear una lista con números aleatorios de diferentes longitudes. En concreto de 10, 100, 1.000, 10.000, 100.000, 1.000.000, 10.000.000 y 20.000.000 elementos. Una copia de estos vectores (para evitar así que los métodos que ordenan la lista en lugar de una copia la simplifique el trabajo al siguiente) se va a inyectar a una función en la que ordenará la lista y medirá el tiempo de ejecución con la función process.hrtime(). Finalmente, los resultados de tiempo se guardarán una lista y el proceso se repetirá varias veces para reducir los errores en la medida. El código que se va a utilizar es el siguiente.

const fs = require('fs');
const timsort = require('timsort');
const arraySort = require('array-sort');
const sort = require('fast-sort');

function calculateTime(hrtime) {
    return hrtime[0] + hrtime[1] / 1000000000;
}

function runSort(data) {
    const start = process.hrtime();
    data.sort();
    return calculateTime(process.hrtime(start));
}

function runTimsort(data) {
    const start = process.hrtime();
    timsort.sort(data);
    return calculateTime(process.hrtime(start));
}

function runArraySort(data) {
    const start = process.hrtime();
    arraySort(data);
    return calculateTime(process.hrtime(start));
}

function runFastSort(data) {
    const start = process.hrtime();
    sort(data).asc();
    return calculateTime(process.hrtime(start));
}

const length = [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 20000000];
const results = [...Array(4)].map(() => Array(length.length).fill(0));
const numTry = 5;

length.forEach((value, index) => {
    for (let i = 0; i < numTry; ++i) {
        const data = [...Array(value)].map(() => Math.random());

        results[0][index] += runSort(data.slice()) / numTry;
        results[1][index] += runTimsort(data.slice()) / numTry;
        results[2][index] += runFastSort(data.slice()) / numTry;
        results[3][index] += runArraySort(data.slice()) / numTry;
    }
});

En este archivo se puede en primer lugar se define una función calcular el tiempo en segundos, calculateTime. Posteriormente se crear cuatro funciones runSort, runTimsort, runArraySort y runFastSort con las que ordenar un vector u medir el tiempo de ejecución para cada uno de los métodos analizados. Finalmente se itera para repetir 5 veces el proceso de ordenación y obtener el tiempo medio en cada uno de los casos.

Resultados

Los resultados obtenidos se pueden ver en la siguiente tabla en la que se muestra el tiempo relativo de cada una de las librerías respecto a la función sort().

Lo primero que se observa es que para listas de un único elemento, las funciones no son más eficientes que sort(). Aunque en estos casos hay poco que ordenar. Para elementos entre 10 y 1000, los resultados parecen aleatorios, lo que se puede deber a que los tiempos de ordenación están por debajo de los milisegundos, por ejemplo, sort() solamente tarda 0,7 milisegundos en ordenar el vector de 1000 elementos. Por lo que para vectores por debajo de esta longitud posiblemente no sea necesario cambiar el método nativo de JavaScript. Por lo menos si estamos usando Node.

A partir de los 10.000 elementos se observa que las librerías timsort y fast-sort ofrecen ahorros de tiempo. Lo que, por otro lado, no se observa en array-sort. En la comparación destaca casi siempre fast-sort que reduce tiempo necesario para ordenar la lista en torno a 1/3 de lo que necesita la función nativa de JavaScript. Lo que en el caso de 20 millones de elementos de 153 segundos a solo 45, un ahora de casi dos minutos.

Una vez visto los resultados posiblemente la mejor opción sea fast-sort cuando necesitamos ordenar elementos por encima de los 10.000, por debajo de este volumen el ahorro de tiempo es despreciable, aunque existe.

Conclusiones

En esta entrada se han comparados tres librerías para ordenar listas en JavaScript con la función nativa, observándose una mejora del rendimiento de las librerías cuando hablamos de vectores grandes. Por lo que el uso de estar librería es aconsejable cuando sea necesario ordenar vectores de cientos de miles de registros. En caso de vectores más pequeños agregar una librería posiblemente no compense la mejora de rendimiento, incluso en algunos casos no existe esta mejora.

Es importante tener en cuenta que estas pruebas se han realizado en Node, por lo que el uso en navegadores no tiene porque ser similar. Además de esto, se ha utilizado únicamente vectores reales, pudiendo ofrecer cada uno de los métodos diferentes resultados con otros tipos de datos.

Así vemos que podemos existen recursos para optimizar mejorar el rendimiento a la hora de trabajar con vectores. Algo que ya se ha visto al comparar los métodos para iterar y medir el rendimiento.

Imagen de StockSnap en Pixabay