¿Hay una mejor manera de hacer sumas parciales de elementos de matriz en JavaScript?

arrays functional-programming

Question

Me pregunto si hay una mejor manera de generar una solución de mejor rendimiento para sumas parciales de una matriz.

Dada una matriz, por ejemplo, x = [ 0, 1, 2, 3, 4, 5 ] , generé subarreglas de los elementos y luego calculé la suma de cada matriz que da:

[ 0, 1, 3, 6, 10, 15 ]

Entonces el código completo es:

x.map((y,i)=>x.filter((t,j)=>j<=i))
 .map(ii=>ii.reduce((x,y)=>x+y,0))

Me pregunto si el mapa plano o algún otro método de matriz tendrá una solución que no requiera expandir cada subconjunto.

Answer 1

A continuación, el scan toma una función de mapeo f un acumulador inicial r -

const scan = (f, r, [ x, ...xs ]) =>
  x === undefined
    ? [ r ]
    : [ r, ...scan (f, f (r, x), xs) ]
  
const add = (x, y) =>
  x + y

const print = (...vs) =>
  vs .forEach (v => console .log (v))

const data =
  [ 0, 1, 2, 3, 4, 5 ]
  
print
  ( scan (add, 0, data)
  , scan (Math.max, 3, data)
  , scan (add, 0, [])
  )

// [ 0, 0, 1, 3, 6, 10, 15 ]
// [ 3, 3, 3, 3, 3, 4, 5 ]
// [ 0 ]

Si necesita un programa que no tome un acumulador inicial, se puede usar el primer elemento de la matriz de entrada. Esta variación se llama scan1 -

const scan = (f, r, [ x, ...xs ]) =>
  x === undefined
    ? [ r ]
    : [ r, ...scan (f, f (r, x), xs) ]
    
const scan1 = (f, [ x, ...xs ]) =>
  x === undefined
    ? []
    : scan (f, x, xs)

const add = (x, y) =>
  x + y
  
const print = (...vs) =>
  vs .forEach (v => console .log (v))

const data =
  [ 0, 1, 2, 3, 4, 5 ]

print
  ( scan1 (add, data)
  , scan1 (Math.max, data)
  , scan1 (Math.min, data)
  , scan1 (add, [])
  )
  
// [ 0, 1, 3, 6, 10, 15 ]
// [ 0, 1, 2, 3, 4, 5 ]
// [ 0, 0, 0, 0, 0, 0 ]
// []

Se pueden hacer optimizaciones de rendimiento y los problemas de desbordamiento de pila pueden remediarse, si es necesario, todo sin sacrificar el estilo funcional.

const scan = (f, init, xs) =>
  loop
    ( ( r = []
      , a = init
      , i = 0
      ) =>
        i >= xs.length
          ? push (a, r)
          : recur
              ( push (a, r)
              , f (a, xs[i])
              , i + 1
              )
    )

Ahora vamos a ejecutarlo con una gran entrada -

// BIG data!
const data =
  Array .from (Array (10000), (_, x) => x)

// fast and stack-safe
console .time ("scan")
const result = scan (add, 0, data)
console .timeEnd ("scan")
// scan: 8.07 ms

console .log (result)
// [ 0, 0, 1, 3, 6, 10, 15, ..., 49985001 ]

Esto depende de los siguientes procedimientos funcionales genéricos:

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const push = (x, xs) =>
  ( xs .push (x)
  , xs
  )

Expanda el fragmento a continuación para verificar los resultados en su propio navegador:

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const push = (x, xs) =>
  ( xs .push (x)
  , xs
  )

const scan = (f, init, xs) =>
  loop
    ( ( r = []
      , a = init
      , i = 0
      ) =>
        i >= xs.length
          ? push (a, r)
          : recur
              ( push (a, r)
              , f (a, xs[i])
              , i + 1
              )
    )

const add = (x, y) =>
  x + y

const data =
  Array .from (Array (10000), (_, x) => x)
  
console .time ("scan")
const result = scan (add, 0, data)
console .timeEnd ("scan")

console .log (result)
// [ 0, 0, 1, 3, 6, 10, 15, ..., 49995000 ]

Answer 2

Aquí hay una respuesta simple usando una función recursiva.

var array = [ 0, 1, 2, 3, 4, 5 ];

function sumArray(arrayToSum, index){
    if(index < arrayToSum.length-1){
        arrayToSum[index+1] = arrayToSum[index] + arrayToSum[index+1];
        return sumArray(arrayToSum, index+1);
  }else
    return arrayToSum;

}
sumArray(array, 0);

console.log(array);

Answer 3

El mapa plano no será útil en su caso, ya que no está tratando de aplanar sus resultados parciales como listas, pero probablemente podamos tratar de resolver su problema en una única reducción :

[0, 1, 2, 3, 4, 5]
.reduce(
   ([arr, sum], el) => { // We pass along array and running sum
       const next = sum + el
       return [[...arr, next], next]
   },
   [[], 0] // We need to seed our reduce with empty array and accumulator for calculating running sum
)[0] // Array containing array and the last sum is returned, so we need to take only the first element

También itera la matriz solo una vez, por lo que puede tener un poco más de rendimiento, que una solución que crea segmentos y luego los suma.

O una versión con array.push , que reutiliza la misma matriz:

[0, 1, 2, 3, 4, 5]
.reduce(
   ([arr, sum], el) => { // We pass along array and running sum
       const next = sum + el
       arr.push(next)
       return [arr, next]
   },
   [[], 0] // We need to seed our reduce with empty array and accumulator for calculating running sum
)[0] 

Answer 4

Es posible usar el mapa directamente, si mantiene una variable externa del acumulador:

const x = [ 0, 1, 2, 3, 4, 5 ];

let acc = 0;
const prefixSum = x.map(x => acc += x);

console.log(prefixSum);

Answer 5

Mucho, manteniendo un total acumulado:

function* partialSums(iterable) {
    let s = 0;

    for (const x of iterable) {
        s += x;
        yield s;
    }
}

const x = [0, 1, 2, 3, 4, 5];
console.log(Array.from(partialSums(x)).join('', ''));

Tiempo lineal, en línea. (También puede producir una matriz directamente; expanda a continuación.)

const partialSums = arr => {
    let s = 0;
    return arr.map(x => s += x);
};

const x = [0, 1, 2, 3, 4, 5];
console.log(partialSums(x).join('', ''));

Answer 6

Se puede usar una para cada una y luego cortar las matrices para obtener los elementos uno por uno y luego array.reduce todos por array.reduce . Puede hacer esto como

let x = [0, 1, 2, 3, 4, 5]
let sum = []
x.forEach((_, index) => {
  index++;
  sum.push(x.slice(0, index).reduce((a, b) => a + b))
})
console.log(sum)

Estamos obteniendo [0] luego [0,1] luego [0,1,2] luego [0,1,2,3] y vía [0,1,2].reduce((a, b) => a + b)) obtenemos 3. Simplemente empuje eso a una nueva matriz. Cual es tu respuesta

Podemos ir aún más cortos haciendo esto. Para mí, esto parece una solución muy optimizada.

let ar = [0, 1, 2, 3, 4, 5]
let s = 0
let arr = []
ar.forEach((n, i) => arr.push(s += n))
console.log(arr)

Ahora, lo que esto hace es tomar una variable y luego agregarle los valores y luego simplemente enviarla a la matriz.

Answer 7

Si pregunta si hay una manera más rápida o más eficiente , entonces las otras respuestas son suficientes.

Sin embargo, yo diría que algo similar a su solución actual es más fácil de leer y más declarativo si lo expresamos como una función de mapeo.

Específicamente algo como "Asignar cada valor a sí mismo más todos los valores anteriores en la matriz".

Podría usar un filtro, como lo ha hecho en su pregunta, pero creo que una porción es más clara.

const x = [ 0, 1, 2, 3, 4, 5 ];

// A common generic helper function
const sum = (acc, val) => acc + val

const sums = x.map((val, i, self) => val + self.slice(0, i).reduce(sum, 0))

Answer 8

Simplemente puede usar un bucle for con una variable para realizar un seguimiento de la última suma

let x = [ 0, 1, 2, 3, 4, 5 ]

let sum = (arr) => {
  let sum = 0
  let final = []
  for(let i=0; i<arr.length; i++){
    sum+= arr[i]
    final.push(sum)
  }
  return final
}

console.log(sum(x))

También puedes usar el mapa:

let x = [0, 1, 2, 3, 4, 5]

let sum = (arr) => {
  let sum = 0
  return arr.map(current => sum += current )
}

console.log(sum(x))

Answer 9

Solo tiene que agregar en cada paso el valor actual al resultado anterior, por lo que podría usar una reducción simple.

const array = [0, 1, 2, 3, 4, 5, 6];

const sums = array.reduce((acc,current,index) => {
  const prev = acc.length ? acc[index-1] : 0;
  acc.push(prev + current);
  return acc;
},[]);

console.log(sums.toString());

Answer 10

Una opción es usar un único .map que use .reduce para resumir la matriz parcial dividida:

const x = [0, 1, 2, 3, 4, 5];

const sum = (x, y) => x + y;
const partialSums = x.map((_, i, arr) => arr.slice(0, i + 1).reduce(sum));
console.log(partialSums);