Optimizando la función Sums of Parts para Code Wars

30 Jul, 2023 Programación 0

Estoy revisando el problema “Sums of Parts” en CodeWars:

Consideremos este ejemplo (arreglo escrito en formato general):
ls = [0, 1, 3, 6, 10]
Sus partes son las siguientes:
ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []
Las sumas correspondientes son (unidas en una lista): [20, 20, 19, 16, 10, 0]

La función parts_sums (u otras variantes en otros lenguajes) toma como parámetro una lista ls y devuelve una lista con las sumas de sus partes según se define arriba.

El objetivo de la función es sumar los elementos del arreglo y luego desplazar el primer elemento del arreglo cada vez hasta que la longitud del arreglo sea 0.

Tengo esta solución para ello:

function partsSums(ls) {
    let len = ls.length;
    let arr = [];
    for (let i = 0; i < len +1; i++) {
        arr.push(summation(ls));
        ls.shift();
    }

    function summation(a) {
        let sum = 0;
        for (let i = 0; i < a.length; i++) {
            sum += a[i];
        }
        return sum;
    }
    return arr;
}

Funciona cuando lo ejecuto en mi editor: todos los casos de prueba en CodeWars que se completan correctamente pasan, pero cuando intento enviarlo, obtengo este error:

El proceso fue terminado. Se tardó más de 12000ms en completarse.

Soy nuevo en algoritmos y no puedo entender dónde está el error. ¿Se aceptan sugerencias?

function partsSums(ls) { let len = ls.length; let total = ls.reduce((acc, val) => acc + val, 0); let result = [total]; for (let i = len - 1; i >= 0; i--) { total -= ls[i]; result.push(total); } return result.reverse(); }

Answer

davy.ai

July 30, 2023 at 3:26 pm
Hay algunos problemas con la implementación actual que podrían causar el error de tiempo de espera en CodeWars:
1. El uso del método shift() dentro de un bucle no es muy eficiente, ya que causa que el arreglo se reindexe después de cada operación, lo que lleva a un rendimiento más lento a medida que el arreglo crece.
2. La función summation() se llama en cada iteración del bucle, lo que significa que las mismas sumas se calculan varias veces.
Para mejorar el rendimiento de la implementación, podemos utilizar una variable de suma acumulada y recorrer el arreglo de fin a principio, actualizando la suma acumulada a medida que avanzamos. Aquí tienes una implementación actualizada:
```
function partsSums(ls) {
  let len = ls.length;
  let total = ls.reduce((acc, val) => acc + val, 0);
  let result = [total];

  for (let i = len - 1; i >= 0; i--) {
    total -= ls[i];
    result.push(total);
  }

  return result.reverse();
}
```
En esta implementación, primero calculamos la suma total del arreglo de entrada utilizando reduce(), luego recorremos el arreglo de fin a principio, restando cada elemento de la suma acumulada y agregándolo al arreglo de resultados. Finalmente, invertimos el orden del arreglo de resultados y lo devolvemos.

Esta implementación debería ser más eficiente y evitar el error de tiempo de espera en CodeWars.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Optimizando la función Sums of Parts para Code Wars

Answer

davy.ai