El autor del material, cuya traducción publicamos hoy, dice que confía en que muchos desarrolladores de JavaScript usan principalmente tipos de datos como
Number ,
String ,
Object ,
Array y
Boolean . En la mayoría de los casos, esto es suficiente. Pero si necesita hacer que el código sea lo más rápido y escalable posible, el uso de estos tipos de datos no siempre está justificado.
En este artículo, hablaremos sobre cómo, utilizando el tipo de datos
Set , que proporciona la capacidad de trabajar con colecciones de valores únicos, hacer que el código sea más rápido. Esto es especialmente cierto para el código de proyectos a gran escala. Los tipos
Array y
Set tienen mucho en común, pero el uso del tipo de datos
Set puede dar al programador características que se manifiestan claramente durante la ejecución de programas que el tipo
Array no tiene.
¿Cuál es la diferencia entre los tipos de datos Array y Set?
La característica principal del tipo de datos
Array (llamaremos a los objetos de este tipo "arrays") es que los arrays son colecciones indexadas de valores. Esto significa que los datos en las matrices se almacenan mediante índices.
const arr = [A, B, C, D]; console.log(arr.indexOf(A));
A diferencia de las matrices, los objetos del tipo
Set (los llamaremos "colecciones") son colecciones que contienen datos en el formato clave / valor. En lugar de utilizar índices, las colecciones almacenan elementos utilizando claves. Los elementos almacenados en la colección se pueden ordenar en el orden en que se agregaron a la colección, mientras que la colección no puede almacenar los mismos elementos. En otras palabras, todos los elementos de la colección deben ser únicos.
¿Cuáles son las principales fortalezas de las colecciones?
Si compara colecciones y matrices, puede encontrar algunas ventajas sobre las colecciones sobre las matrices, especialmente notables en situaciones en las que el rendimiento del programa es importante:
- Busca artículos. Los métodos de matriz
indexOf() e includes() , utilizados para buscar elementos y verificar si un elemento tiene un elemento, funcionan lentamente. - Retirar artículos. Un elemento se puede eliminar de la colección en función de su valor. En una matriz, el equivalente de tal acción sería usar el método
splice() , basado en el índice del elemento. Al igual que con la búsqueda de elementos, eliminar elementos mediante índices es una operación lenta. - Insertar un artículo. Es mucho más rápido agregar un elemento a la colección que usar métodos como
push() y unshift() en una matriz. - Trabajar con valor
NaN . El método indexOf() no puede usarse para encontrar el valor de NaN en una matriz, mientras que usando el método de colección has() , puede determinar si tiene NaN . - Eliminar elementos duplicados.
Set objetos solo almacena valores únicos. Si necesita evitar guardar elementos duplicados en alguna estructura de datos, esta es su ventaja significativa sobre las matrices. Al trabajar con matrices para eliminar elementos duplicados tendría que escribir código adicional.
Aquí se puede encontrar una lista completa de los métodos integrados de objetos de tipo
Set .
Sobre la complejidad temporal de los algoritmos
Los métodos que utilizan las matrices para buscar elementos tienen una complejidad lineal de tiempo: O (N). En otras palabras, el tiempo de búsqueda del elemento es proporcional al tamaño de la matriz.
A diferencia de las matrices, los métodos utilizados por las colecciones para buscar, eliminar y agregar elementos tienen una complejidad de tiempo O (1). Esto significa que el tamaño de la colección prácticamente no tiene ningún efecto sobre el tiempo de trabajo de dichos métodos.
Aquí puede leer más sobre la complejidad temporal de los algoritmos.
¿Cuánto más rápido son las colecciones que las matrices?
Aunque los indicadores de rendimiento del código JavaScript están fuertemente influenciados por una variedad de factores, en particular, dependen del sistema en el que se ejecuta el código, del tiempo de ejecución del código utilizado, del tamaño de los datos procesados, espero que los resultados de mis pruebas le den la oportunidad de comparar matrices y colecciones desde un punto de vista práctico, y comprender cómo las colecciones son más rápidas que las matrices. Ahora consideraremos tres pruebas simples y analizaremos sus resultados.
▍ Preparación de la prueba
Antes de hacer cualquier prueba, creemos una matriz con un millón de elementos y la misma colección. En aras de la simplicidad, utilizaremos un ciclo, cuyo primer valor de contador será 0 y el último - 999999:
let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); }
▍ Prueba No. 1: verificar la presencia de un elemento en una matriz y en una colección
Primero, verificaremos la presencia del elemento
123123 en la matriz y en la colección, sabiendo de antemano que dicho elemento existe en estas estructuras de datos.
let result; console.time('Array'); result = arr.indexOf(123123) !== -1; console.timeEnd('Array'); console.time('Set'); result = set.has(123123); console.timeEnd('Set');
Aquí están los resultados de esta prueba:
Array: 0.173ms Set: 0.023ms
La colección es 7.54 veces más rápida que la matriz.
▍ Prueba No. 2: inserción de un elemento
Ahora intentemos agregar elementos a matrices y colecciones.
console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set');
Esto es lo que sucedió:
Array: 0.018ms Set: 0.003ms
La colección es 6.73 veces más rápida que la matriz.
▍ Prueba 3: eliminar un elemento
Ahora eliminemos el elemento de cada estructura de datos (por ejemplo, el que se agregó en la prueba anterior). Las matrices no tienen un método incorporado para eliminar elementos, por lo que crearemos una función auxiliar para mantener nuestro código en buenas condiciones:
const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); };
Y aquí está el código de prueba:
console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set');
El resultado es el siguiente:
Array: 1.122ms Set: 0.015ms
¡En este caso, la colección fue 74.13 veces más rápida que la matriz!
En general, se puede observar que el rendimiento del código se puede aumentar significativamente mediante el uso de colecciones en lugar de matrices. Considere algunos ejemplos prácticos.
Ejemplo # 1: eliminar valores duplicados de una matriz
Si necesita eliminar rápidamente valores duplicados de una matriz, puede convertirlo en una colección. Esta es quizás la forma más fácil de deshacerse de los valores duplicados:
const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
Ejemplo 2: tarea de entrevista en Google
En uno de mis
materiales, examiné cuatro opciones para responder la pregunta que hizo un entrevistador de Google. La entrevista se realizó usando C ++, pero si se usara JavaScript en lugar de este lenguaje, la estructura de datos
Set se usaría necesariamente para resolver el problema.
Si desea comprender la respuesta a esta pregunta más profundamente, lea el artículo anterior. Aquí solo muestro una solución preparada.
▍ Tarea
Dado un conjunto no ordenado de enteros y un valor de
sum . Escriba una función que devuelva
true si, como resultado de agregar dos elementos de esta matriz, obtenemos el valor de la
sum . Si no hay tales elementos en la matriz, la función debería devolver
false .
Resulta, por ejemplo, que si se nos da una matriz
[3, 5, 1, 4] y el valor de la
sum es
9 , entonces la función debería devolver
true , ya que
4+5=9 .
▍Solución
Puede abordar este problema utilizando la siguiente idea: necesita iterar sobre la matriz, creando la estructura de datos
Set medida que avanza, en la que se agregarán valores que complementan los valores encontrados al valor de
sum .
Analicemos esta idea usando el ejemplo de la matriz anterior. Cuando nos encontramos con
3 , podemos agregar el número
6 a la colección, ya que sabemos que necesitamos encontrar dos números que sumen
9 . Luego, cada vez que encontramos un nuevo valor de la matriz, podemos verificar la colección y ver si está allí. Cuando encontremos el número
5 , agregaremos
4 a la colección. Y cuando, finalmente, llegamos al número
4 , lo encontramos en la colección y podemos volver
true .
Así es como se vería una solución a este problema:
const findSum = (arr, val) => { let searchValues = new Set(); searchValues.add(val - arr[0]); for (let i = 1, length = arr.length; i < length; i++) { let searchVal = val - arr[i]; if (searchValues.has(arr[i])) { return true; } else { searchValues.add(searchVal); } }; return false; };
Y aquí hay una solución más concisa:
const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
Dado que la complejidad temporal del método
Set.prototype.has() es O (1), el uso de la estructura de datos
Set para almacenar números que complementan los números encontrados en la matriz a un valor dado le permite encontrar una solución en tiempo lineal (O (N)).
Si la solución dependiera del método
Array.prototype.indexOf() o del método
Array.prototype.includes() , la complejidad de tiempo de cada uno de ellos es O (N), entonces la complejidad de tiempo total del algoritmo sería O (N
2 ). Como resultado, se volvería mucho más lento.
Resumen
Si no ha encontrado el tipo de datos
Set en JavaScript antes, esperamos que ahora, al tener una idea, pueda usarlo con beneficio en sus proyectos.
Estimados lectores! ¿Cómo aplicaría la estructura de datos
Set en su código?