Есть ли лучший способ сделать частичные суммы элементов массива в JavaScript?

Question

Интересно, есть ли лучший способ создания более эффективного решения для частичных сумм массива.

Учитывая массив, скажем x = [ 0, 1, 2, 3, 4, 5 ], я сгенерировал подмассивы элементов, а затем вычислилсумма каждого массива, которая дает:

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

Итак, полный код:

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

Интересно, будет ли плоская карта или какой-либо другой метод массива иметь решение, которое не требуетрасширяя каждый подмассив.

Answer 1

Многое, сохраняя промежуточный итог:

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(', '));

Линейное время, онлайн. (Вы также можете создать массив напрямую; разверните ниже.)

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 2

Плоская карта не будет полезна в вашем случае, потому что вы не пытаетесь сгладить частичные результаты, поступающие в виде списков, но мы, вероятно, можем попытаться решить вашу проблему за один сокращение :

[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

Он также повторяет массив только один раз, поэтому он может быть немного более производительным, чем решение, создающее фрагменты и затем суммирующее их.

Или версия с array.push, которая использует тот же массив:

[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 3

Ниже scan принимает функцию отображения f и начальный аккумулятор 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 ]

Если вам нужна программа, которая не использует начальный аккумулятор, вместо нее можно использовать первый элемент входного массива. Этот вариант называется 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 ]
// []

---

Возможна оптимизация производительности и исправлены проблемы переполнения стека, если необходимо, все без ущерба для функционального стиля -

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
              )
    )

Теперь давайте запустим его с большим вводом -

// 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 ]

Это зависит от следующих общих функциональных процедур -

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 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 4

Если вы спрашиваете, существует ли более быстрый или более эффективный способ, тогда достаточно других ответов.

Однако я бы сказал, что что-то похожее на ваше текущее решение проще для чтения и более декларативно, если мы сформулируем это как функцию отображения.

В частности, что-то вроде «Сопоставить каждое значение с самим собой и все предыдущие значения в массиве».

Вы могли бы использовать фильтр, как вы сделали в своем вопросе, но я думаю, что срез будет более понятным.

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 5

Вам просто нужно добавлять на каждом шаге текущее значение к предыдущему результату, чтобы вы могли использовать простое уменьшение.

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 6

Вы можете просто использовать цикл for с переменной для отслеживания последней суммы

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))

Вы также можете использовать карту:

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 7

Можно использовать карту напрямую, если вы сохраните переменную внешнего аккумулятора:

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

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

console.log(prefixSum);

Answer 8

Один из вариантов - использовать один .map, который использует .reduce внутри, чтобы суммировать нарезанный частичный массив:

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);

Answer 9

Можно использовать для каждого из них, а затем нарезать массивы, чтобы получить элементы по одному, а затем суммировать их все по array.reduce. Вы можете сделать это как

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)

Мы получаем [0], затем [0,1], затем [0,1,2], затем [0,1,2,3], и через [0,1,2].reduce((a, b) => a + b)) мы получаем 3. Просто отправьте это в новый массив. Какой твой ответ.

Мы можем пойти еще короче, сделав это. Мне кажется, это очень оптимизированное решение.

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

Или с .map, вы можете

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

Answer 10

Вот простой ответ с использованием рекурсивной функции.

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);