• Ir al contenido principal
  • Skip to secondary menu
  • Ir a la barra lateral primaria
  • Ir al pie de página
  • Inicio
  • Secciones
    • Ciencia de datos
    • Criptografía
    • Herramientas
    • Noticias
    • Opinión
  • Programación
    • JavaScript
    • Julia
    • Matlab
    • Python
    • R
  • Boletín
  • Contacto
  • Acerca de Analytics Lane
  • Tienda
    • Libros
    • Equipamiento de oficina
    • Equipamiento en movilidad
    • Tiendas afiliadas
      • AliExpress
      • Amazon
      • GearBest
      • GeekBuying
      • JoyBuy

Analytics Lane

Ciencia e ingeniería de datos aplicada

  • Ciencia de datos
  • Criptografía
  • Python
  • Matlab
  • R
  • Julia
  • JavaScript
  • Herramientas
  • Opinión
  • Noticias

Librerías para ordenar listas en JavaScript

octubre 7, 2020 Por Daniel Rodríguez Dejar un comentario

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().

Elementossorttimsortfast sortarray sort
115,656,363,09
1010,870,460,05
100112,880,970,48
1.00015,000,710,80
10.00011,340,280,92
100.00011,270,250,96
1.000.00010,800,330,88
10.000.00010,830,260,99
20.000.00010,800,301,08
Tiempo relativo respecto a la función nativa que ha necesitado cada una de las librerías para ordenar una lista de la longitud indicada.

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

¿Te ha parecido de utilidad el contenido?

¡Puntúalo entre una y cinco estrellas!

Puntuación promedio 0 / 5. Votos emitidos: 0

Ya que has encontrado útil este contenido...

¡Síguenos en redes sociales!

¡Siento que este contenido no te haya sido útil!

¡Déjame mejorar este contenido!

Dime, ¿cómo puedo mejorar este contenido?

Contenido relacionado

Archivado en:JavaScript Etiquetado con:node

Interacciones con los lectores

Deja una respuesta Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

I accept the Terms and Conditions and the Privacy Policy

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Publicidad


Barra lateral primaria

Suscríbete a nuestro boletín

Suscríbete al boletín semanal para estar al día de todas las publicaciones.

Política de Privacidad

¡Síguenos en redes sociales!

  • facebook
  • github
  • telegram
  • pinterest
  • rss
  • tumblr
  • twitter
  • youtube

Publicidad

Tiendas afiliadas

Ayúdanos realizando tus compras sin coste adicional con los enlaces de la tienda. ¡Gracias!

Entradas recientes

Creación de un certificado Let’s Encrypt en Windows con Win-Acme

enero 22, 2021 Por Daniel Rodríguez Dejar un comentario

Aplicaciones de Node en producción con PM2

enero 20, 2021 Por Daniel Rodríguez Dejar un comentario

SQLite en Python

enero 18, 2021 Por Daniel Rodríguez Dejar un comentario

Publicidad

Es tendencia

  • ¿Cómo eliminar columnas y filas en un dataframe pandas? bajo Python
  • Seleccionar filas y columnas en Pandas con iloc y loc bajo Python
  • Excel en Python Guardar y leer archivos Excel en Python bajo Python
  • Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas bajo Python
  • Unir y combinar dataframes con pandas en Python bajo Python

Publicidad

Lo mejor valorado

5 (3)

Ordenar una matriz en Matlab en base a una fila o columna

5 (3)

Automatizar el análisis de datos con Pandas-Profiling

5 (5)

Diferencias entre var y let en JavaScript

5 (6)

Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas

5 (3)

Unir y combinar dataframes con pandas en Python

Publicidad

Comentarios recientes

  • Daniel Rodríguez en Calculadora de probabilidades de ganar a la lotería
  • abel en Calculadora de probabilidades de ganar a la lotería
  • David Arias en Diferencias entre regresión y clasificación en aprendizaje automático
  • Juan Aguilar en Archivos JSON con Python: lectura y escritura
  • Camilo en Contar palabras en una celda Excel

Publicidad

Footer

Secciones

  • Ciencia de datos
  • Criptografía
  • Herramientas
  • Noticias
  • Opinión

Programación

  • JavaScript
  • Julia
  • Matlab
  • Python
  • R

Analytics Lane

  • Acerca de Analytics Lane
  • Boletín de noticias
  • Contacto
  • Lo más popular
  • Tienda

Tiendas Afiliadas

  • AliExpress
  • Amazon
  • BangGood
  • GearBest
  • Geekbuying
  • JoyBuy

Sobre de Analytics Lane

En Analytics Lane tratamos de explicar los principales conceptos de la ciencia e ingeniería de datos con un enfoque práctico. Los principales temas tratados son ciencia de datos, ingeniería de datos, inteligencia artificial, machine learning, deep learning y criptografía. Además, también se habla de los principales lenguajes de programación y herramientas utilizadas por los científicos e ingenieros de datos.

Tiendas afiliadas

Ayúdanos realizando tus compras sin coste adicional con los enlaces de la tienda. ¡Gracias!

Amazon

2018-2020 Analytics Lane · Términos y condiciones · Política de Cookies · Política de Privacidad · Herramientas de privacidad · Contacto