# New array from a sum of N values in array A?

**URL:** <https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496>\
**Category:** General Usage\
**Tags:** tullio\
**Created:** [September 12, 2020, 6:10am UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496 "2020-09-12T06:10:29Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![SEnergy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/senergy/32/16625_2.png) [@SEnergy](https://discourse.julialang.org/u/SEnergy)\
**Post date:** [September 12, 2020, 6:10am UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/1 "2020-09-12T06:10:29Z")

</div>

I’m sorry if the title is a little bit misleading, but I’m having trouble explaining it in one sentence

Assume I have an array A

```julia
A = [1, 2, 3, 4, 5];

```

What I want is to create an array B that will contain sums of every N elements, using a standard for loop this would look like:

```julia
B = [];
N = 3;
for i = 1:length(A)-N+1
    push!(B, sum(A[i:i+N-1]));
end

```

which produces

```julia
3-element Array{Any,1}:
  6
  9
 12

```

now, assume the array A contains tens of thousands of values… how to do this efficiently in Julia?

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [September 12, 2020, 6:26am UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/2 "2020-09-12T06:26:52Z")

</div>

I’d do it by adding the next element to the previous sum and subtracting the one that moves out of the window:

```julia
function movingsum(a, width)
    b = Vector{eltype(a)}(undef, length(a)-width+1)
    s = sum(@view a[1:width])
    for i in 1:length(b)-1
        b[i] = s
        s += a[width+i] - a[i]
    end
    b[end] = s
    return b
end

```

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [September 12, 2020, 7:37am UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/3 "2020-09-12T07:37:10Z")

</div>

rolling sum or moving sum?

See [Rolling Sum](https://discourse.julialang.org/t/rolling-sum/30793)

I think Tullio has an interesting solution

```julia
A = rand(100_000_000);

using Tullio

N = 3
res = zeros(eltype(A), length(A))

using Tullio
@time @tullio res[j] = A[j] + A[j+1] + A[j+2]
@time @tullio res[j] = A[j] + A[j+1] + A[j+2] # 0.2s

```

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [September 12, 2020, 8:10am UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/4 "2020-09-12T08:10:37Z")

</div>

You can also write this:

```julia
julia> A = 1:6; N = 3;
julia> using Tullio

julia> @tullio S[i] := A[i+k-1] (k in 1:N)
4-element Array{Int64,1}:
  6
  9
 12
 15

julia> [sum(@view A[i:i+N-1]) for i in 1:length(A)-N+1]
4-element Array{Int64,1}:
  6
  9
 12
 15

```

As the linked “Rolling Sum” thread points out, both of these need to get each element of A about N times, while something like `movingsum` only gets each one once. Conversely I suppose the accumulation in `s` may run out of precision in some cases:

```julia
julia> A32 = Float32.(inv.(1:10^8));

julia> movingsum(A32, 100)[end]
4.390179f-6

julia> sum(A32[end-99:end])
1.0000006f-6

```

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [September 12, 2020, 10:37am UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/5 "2020-09-12T10:37:02Z")

</div>

> [@mcabbott](#):
>
> Conversely I suppose the accumulation in `s` may run out of precision in some cases:

Kahan summation is left as an exercise to the reader 🙂

Still, an N-pass algorithm may be faster for small N due to better memory access pattern. I kinda prematurely optimized for “wide” summation windows.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 12, 2020, 11:23am UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/6 "2020-09-12T11:23:53Z")

</div>

Adding one comment to help: one important feature of the solution proposed by Vasily is that he created vector `b` before the loop instead of using `push!` This will make a big difference relative to the initial proposal.

Of course, that and not having to run over elements repeatedly.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 12, 2020, 12:35pm UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/7 "2020-09-12T12:35:11Z")

</div>

> [@lmiq](#):
>
> he created vector b before the loop instead of using push. This will make a big difference relative to the initial proposal.

Note that repeated `push!` is pretty efficient (amortized linear time) in Julia. (However, in the initial post, `B = []` creates a `Vector{Any}`, which has inefficient abstractly typed elements.)

---

<div class="post-metadata">

**Author:** ![ric.cioffi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ric.cioffi/32/18373_2.png) [@ric.cioffi](https://discourse.julialang.org/u/ric.cioffi)\
**Post date:** [September 12, 2020, 1:16pm UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/8 "2020-09-12T13:16:18Z")

</div>

There’s still quite a huge difference with and without pre-allocation

```julia
using BenchmarkTools

function prealloc_movingsum(a, width)
    b = Vector{eltype(a)}(undef, length(a)-width+1)
    s = sum(@view a[1:width])
    for i in 1:length(b)-1
        b[i] = s
        s += a[width+i] - a[i]
    end
    b[end] = s
    return b
end

function noprealloc_movingsum(a, width)
    b = eltype(a)[]
    s = sum(@view a[1:width])
    push!(b, s)
    for i in 1:length(a)-width
        s += a[width+i] - a[i]
        push!(b, s)
    end
    return b
end

A = rand(100);
@btime prealloc_movingsum($A, 5);
126.246 ns (1 allocation: 896 bytes)

@btime noprealloc_movingsum($A, 5);
742.203 ns (7 allocations: 2.20 KiB)

```

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 12, 2020, 2:24pm UTC](https://discourse.julialang.org/t/new-array-from-a-sum-of-n-values-in-array-a/46496/9 "2020-09-12T14:24:58Z")

</div>

Yes, I was just testing the same thing (not exactly in the same sum):

```julia
using Test
using BenchmarkTools

x = rand(1000)

function f(x)
  y = [x[1] ]
  for i in 2:length(x)
    y = push!(y,x[i] + y[i-1])
  end
  return y
end

function g(x)
  y = Vector{Float64}(undef,length(x))
  y[1] = x[1]
  for i in 2:length(x)
    y[i] = x[i] + y[i-1]
  end
  return y
end

@test sum(f(x)) ≈ sum(g(x))

println("push:")
@btime f($x)

println("vector:")
@btime g($x)

println("end")

```

```julia
push:
  5.666 μs (10 allocations: 16.41 KiB)
vector:
  1.375 μs (1 allocation: 7.94 KiB)
end

```

edit: Just add further information, as pointed by @stevengj, the fact that the vector is of type Any is also extremely detrimental to performance (also for a factor of ~5):

```julia
function h(x)
  y = Vector{Any}(undef,0)
  push!(y,x[1])
  for i in 2:length(x)
    y = push!(y,x[i] + y[i-1])
  end
  return y
end
julia> @btime h($x)
Any:
  24.734 μs (2009 allocations: 47.63 KiB)

```