3

Estaba haciendo un problema que dado una entrada de un arreglo arr regresar la suma acumulada de sus elementos en los indices posteriores... Es esto:

Input: arr= [0, 1, 3, 6, 10]

Ouput: arr = [ 20, 20, 19, 16, 10, 0]

porque:

ls = [0, 1, 3, 6, 10] *20

ls = [1, 3, 6, 10] *20

ls = [3, 6, 10] *19

ls = [6, 10] *16

ls = [10] *10

ls = [] *0

Como sabia que el tiempo de ejecución seria importante pensé en una solución O(n) iterando con for() mas rapido para estos casos que forEach() map() for of esta fue mi primera solucion

function partSums(ls) {
    let resp = [0]
    let suma = 0
    let len= ls.length - 1;
    for (let i = len; i >= 0; i--) {
        suma += ls[i]
        resp.unshift(suma)
    }
    return resp
}

console.log(partSums([0, 1, 3, 6, 10]))
console.log(partSums([ 20, 19, 16, 10, 0 ]))

Pense que mas rápido que esto no encontraría una forma y que no tendria problemas... sin embargo no paso el test de velocidad.. De casualidad probando funciones hice esta y para sorpresa pase el test de velocidad...

function partSums(ls) {
    let arr = [0];
    ls.reverse().forEach(v => arr.push(arr[arr.length - 1] + v));
    return arr.reverse();
}

console.log(partSums([0, 1, 3, 6, 10]))
console.log(partSums([11, 1, 3, 6, 10,14,32,1,3]))
console.log(partSums([11, 1, 3, 0, 1, 3, 6, 10, 6, 10,14,32,1,3]))

digo sorpresa porque para mi hacer reverse() 2 veces y utilizando forEach() para iterar(mas lento que el for()) ya seria suficiente para no pasar los test... pero era significativamente mas rapida esta funcion... otra cosa rara es que esta misma función con map() es casi la mitad mas lenta que forEach() cosa que aun no me queda clara...

Comparando estas funciones saque como conclusion que el problema estaba en el unshift()!!!

function partsSums(ls) {
    let resp = [0]
    let acum = 0
    let len= ls.length - 1
    for (let i = len; i >= 0; i--) {
        acum += ls[i]
        resp.push(acum)
    }
    return resp.reverse()
}

console.log(partsSums([0, 1, 3, 6, 10]));

Entonces mi pregunta es como es posible que el unshift() sea tanto mas costoso en tiempo que el push()... que el reverse() (que para mi tenia q hacer algo similar al for() cambiando indices) sea tan rapido.. y como es posible tambien que el forEach() sea casi tan rapido como el for() y mas que el map()?

0

1 respuesta 1

4

Inicialmente me gustaría señalar que podrías ahorrarte el último reverse, si en lugar de hacer push fueses agregando los resultados en resp[i]

Ejemplo:

function partsSums(ls) {
    let acum = 0,
      resp = [];
    for (let i = ls.length - 1; i >= 0; i--) resp[i] = acum += ls[i];
    resp[ls.length] = 0;
    return resp;
}

console.log(partsSums([0, 1, 3, 6, 10]));


Ahora en respuesta a:

Entonces mi pregunta es como es posible que el unshift() sea tanto mas costoso en tiempo que el push()...

Si tenemos en cuenta que unshift(value) significa agregar un elemento al principio del arreglo, es decir, que todos los elementos previamente agregados tienen que ser movidos de n a n+1, entonces tiene sentido que sea más lento hacer unshift que push (agregar al final)

Y en respuesta a:

cómo es posible también que el forEach() sea casi tan rápido como el for() y más que el map()?

Esto depende de la implementación de cada método en cada navegador.
Por ejemplo, map si miramos su polyfill podríamos decir que es mas lento que un for, debido a que en este:

  • se valida el tipo de dato
  • se valida que los parámetros sean del tipo esperado
  • se crea un acumulador (arreglo de resultado)
  • y por cada elemento se ejecuta una función (callback)
3
  • Muchas gracias Marcos.. y optima la funcion... mas otra cosa rara es que el metodo con push es aun mas rapido que este.. sera por mi navegador y los test que veo consisten en un arreglo enorme con numeros pequeños
    – RazerJs
    el 11 nov. 2019 a las 8:48
  • @IsraelGonzález, no se como estas haciendo tus pruebas. Te dejo este simple test para que puedas ver cómo en distintos navegadores vas a obtener resultados diferentes. En mis pruebas Firefox el 100% de las veces resulto ser más rápida mi implementación.
    – Marcos
    el 11 nov. 2019 a las 10:09
  • Tienes toda la razon... la pagina es la que hace los test de velocidad por mi codewars.com/kata/sums-of-parts/train/javascript volvi a comprobar y para la primera ~Completed in 1937ms para la tuya ~Completed in 3230ms.. nada debe ser algunos de los test especificos y mi navegador(estoy usando Chrome y no eh provado en otros)gracias de nuevo Marcos
    – RazerJs
    el 11 nov. 2019 a las 10:28

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.