Haciendo una prueba rápida en JSPerf, el segundo algoritmo es un 50% más lento que el primero:
Pero quizás sea por los ejemplos que he usado como muestra (algo simple para ser sincero y además está ordenada):
let a1 = ["a","b","c","d","e","f","g","h","i"];
let a2 = ["a","c","e","g","i","k","m","o","q"];
Lo que hacen los dos algoritmos:
- En el primer código:
some()
devolverá verdadero en cuanto la función pasada como callback devuelva verdadero. Esto quiere decir que no tiene que atravesar todos los elementos del array en cada pasada para ejecutar el includes()
. En cuanto encuentra 1, se acabó.
- El array resultante se ordenará.
- En el segundo algoritmo:
- Para cada elemento del array
a1
, se hace una unión del array a2
(con join()) y se comprueba si el elemento existe en la cadena resultante con includes()
.
- El array resultante se ordenará.
Ignorando el sort
, que sería el mismo, tendría sentido que el primer algoritmo fuese (considerablemente) más rápido porque realiza menos operaciones y operaciones menos costosas:
- No tiene que atravesar el array completo en cada iteración (aunque poniéndonos en el peor de los casos, sí tendría)
- Las manipulaciones de cadenas son más costosa... ¡y se realizan en cada iteración!
Basándonos en esto, y por hacer más pruebas, lo que podrías hacer es mover la creación de la cadena a fuera del filtro. De ese modo sólo se ejecutará una vez (no necesitas que se ejecute más) y te ahorrarás numerosas operaciones:
const cadena = a2.join(' ');
const a3 = a1.filter(x => cadena.includes(x)).sort();
He añadido ese ejemplo al JSPerf y es el que obtiene mejores resultados de los tres (aunque hay que considerar que las cadenas están ordenadas):
Nota: llevo sin hacer esto mucho tiempo y puede que me esté equivocando en algo de lo que pongo
Explicación teórica:
- El orden de complejidad del primer algoritmo es O(N2) porque en el peor de los casos se atraviesa
a2
(de tamaño N) una vez por cada elemento de a1
(de tamaño N), lo que resulta en N * N = N2.
- El orden de complejidad del segundo algoritmo es O(N2) también.
a2
(de tamaño N) se atraviesa entero cada vez que hay que generar la cadena (ignorando que es una operación más costosa) y eso ocurre una vez por cada elemento de a1
(de tamaño N), lo que resulta en N * N = N2.
- El orden de complejidad del tercer algoritmo sería O(N). La cadena se genera una sola vez, por lo que
a1
se atraviesa una sola vez (N) y luego a2
se atraviesa una vez (N) comparando cada elemento con la cadena, lo que deja N + N = 2N ~ N.
¿Por qué el primer algoritmo es entonces mucho más rápido que el segundo incluso cuando tienen el mismo orden de complejidad? Por dos motivos:
- La muestra no era la adecuada: está ordenada lo que favorece el uso de
some
en este caso; y
- Realiza operaciones menos caras: las operaciones de I/O y trabajo con cadenas son generalmente más costosas.