3

Estoy resolviendo algunos ejercicios y comparando mis resultados con los de otros. Me encontré dos lineas muy similares que resuelven el problema pero quisiera saber cual de ellos esta mejor optimizado.

Estas son las lineas:

return a1.filter(a => a2.some(b => b.includes(a))).sort();
return  a1.filter(x=> a2.join(' ').includes(x)).sort()

Ambas lineas resuelven el problema pero, como saber cual de las dos es mas eficiente?


+INFO

En general lo que hace el código es tomar dos arreglos. El arreglo a1 debe retornar solo palabras que sean subcadenas de cualquier integrante de a2

1
  • para saber cual es más optimo debes ponerlo a prueba en tiempo de ejecución, recursos del sistema... Commented el 17 ene. 2020 a las 22:50

1 respuesta 1

4

Haciendo una prueba rápida en JSPerf, el segundo algoritmo es un 50% más lento que el primero:

resultados de JSPerf

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:
    1. 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ó.
    2. El array resultante se ordenará.
  • En el segundo algoritmo:
    1. 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().
    2. 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):

introducir la descripción de la imagen aquí

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.
4
  • 1
    Esta excelente. Me tome la libertad de agregar una muestra real del ejercicio a la prueba que realizaste. Y las pruebas dan un resultado similar. Muchas gracias. Solo no me queda claro que significa ~ este símbolo.
    – Legna
    Commented el 17 ene. 2020 a las 23:29
  • @Angel Al calcular el orden de complejidad de un algoritmo, se ignoran los factores constantes. Por eso un orden 2N es equivalente (~) a N.
    – Alvaro Montoro
    Commented el 17 ene. 2020 a las 23:32
  • 1
    Pero, lo dicho en la respuesta, llevo sin ver complejidad algorítmica (en teoría) más de una década. Así que toma esa última parte con prudencia, por si he dicho alguna barbaridad.
    – Alvaro Montoro
    Commented el 17 ene. 2020 a las 23:34
  • Jajaja seré prudente. Muchas gracias por la respuesta.
    – Legna
    Commented el 17 ene. 2020 a las 23:38

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.