# How to \`accumulate\` from right efficiently?

**URL:** <https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490>\
**Category:** New to Julia\
**Created:** [September 25, 2018, 10:04pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490 "2018-09-25T22:04:07Z")\
**Posts on this page:** 17\
**Page:** 1

<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 25, 2018, 10:04pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/1 "2018-09-25T22:04:07Z")

</div>

I know that one can do

`x=1:3; accumulate(+, x) `  
To make a cumulative sum from left which yields `[1,3,6]`.

But how I accumulatr from right efficiently? I know I can do  
`x=1:3; reverse(accumulate(+,reverse(x)))`  
But i think reverse would make this inefficient for large arrays eg with 1 billion elements. Looking through the doc I couldn’t find any mention of accumulate from right.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [September 25, 2018, 10:08pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/2 "2018-09-25T22:08:07Z")

</div>

`Iterators.reverse` gives an iterator which iterates things backwards. Might work.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [September 26, 2018, 3:57am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/3 "2018-09-26T03:57:25Z")

</div>

This works but is probably not the most efficient because of views.

```julia
julia> r = 1:3; acc = zeros(3);

julia> @views accumulate!(+, acc[end:-1:1], r[end:-1:1]);

julia> acc
3-element Array{Float64,1}:
 6.0
 5.0
 3.0

```

---

<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 26, 2018, 12:10pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/5 "2018-09-26T12:10:07Z")

</div>

> [@Tamas\_Papp](#):
>
> foldr(+, x)

Pretty sure this just sums up all the number. It doesn’t produce a cumulative sum as required.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 26, 2018, 12:31pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/6 "2018-09-26T12:31:52Z")

</div>

sorry, misread the question, thanks for the correction

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 26, 2018, 12:42pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/7 "2018-09-26T12:42:34Z")

</div>

```julia
julia> accumulate(+, Iterators.reverse(x))
ERROR: MethodError: no method matching similar(::Base.Iterators.Reverse{Array{Int64,1}}, ::Type{Int64})

```

Hmm. This seems a bit unfortunate. Is it a general problem that operations on wrapped arrays sometimes to try to allocate a `similar(::WrapperType{Array{...}})` and failing?

Also, this fails,

```julia
julia> reverse(Iterators.reverse(r))
ERROR: MethodError: no method matching reverse(::Base.Iterators.Reverse{Array{Int64,1}})

```

while this works, of course

```julia
julia> Iterators.reverse(Iterators.reverse(x))

```

It seems hard to get these things to compose well.

---

<div class="post-metadata">

**Author:** ![Adriel](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Adriel](https://discourse.julialang.org/u/Adriel)\
**Post date:** [September 26, 2018, 10:47pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/8 "2018-09-26T22:47:39Z")

</div>

One way that works:

```julia
foldl((x,y)->vcat(x.+y,y), 1:10)

```

Surely a simple loop in a function is the way to go for performance.

---

<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 26, 2018, 11:08pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/9 "2018-09-26T23:08:19Z")

</div>

@Adriel i dont mean to be rude but doubt it’s efficient as it’s vcating and summing alot more then necessary. I guess i would write a loop. But then the same can be said of accumulate? It can be done with a loop, the curious thing is that it can loop from left but not from right. You have foldl and foldr so why not an accumulater that is efficient?

---

<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 26, 2018, 11:14pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/10 "2018-09-26T23:14:07Z")

</div>

cumsum of arrays in Julia has the advantages of being much more accurate than a straightforward loop for floating point data. That algorithm requires a random access array, such as a view, not an iterator, however.

---

<div class="post-metadata">

**Author:** ![Adriel](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Adriel](https://discourse.julialang.org/u/Adriel)\
**Post date:** [September 26, 2018, 11:15pm UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/11 "2018-09-26T23:15:32Z")

</div>

Not rude at all, I agree. Just thought it was cool.

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [September 27, 2018, 2:05am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/12 "2018-09-27T02:05:32Z")

</div>

You can rearrange fairly easily  
`accumulate(-, [0; x[1:end-1]], init = sum(x));`

---

<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 27, 2018, 2:14am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/13 "2018-09-27T02:14:18Z")

</div>

Very clever.

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [September 27, 2018, 2:50am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/14 "2018-09-27T02:50:36Z")

</div>

This does twice the work though, first sum then subtract, also twice the error, not to mention allocates another vector.

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [September 27, 2018, 3:21am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/15 "2018-09-27T03:21:16Z")

</div>

~2.2 sec for 100,000,000 elements v ~ 0.9 sec for the left-to-right version, so a bit average  
May be able to use the end result of accsum for the sum(), and vector subtract

```julia
z = accumulate(+, x);
z2 = z[end] .- [0; z[1:end-1]];

```

---

<div class="post-metadata">

**Author:** ![mohamed82008](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mohamed82008/32/18171_2.png) [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)\
**Post date:** [September 27, 2018, 3:48am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/16 "2018-09-27T03:48:33Z")

</div>

```julia
julia> f(acc, r) = (@views accumulate!(+, acc[end:-1:1], r[end:-1:1]); acc)
f (generic function with 2 methods)

julia> function g(acc, x)
           z = accumulate(+, x);
           acc .= z[end] .- [0; z[1:end-1]];
           acc
       end
g (generic function with 2 methods)

julia> r = rand(100_000_000); acc = similar(r);

julia> @time f(acc, r); @time f(acc, r);
  0.382288 seconds (19.28 k allocations: 898.729 KiB)
  0.149744 seconds (6 allocations: 288 bytes)

julia> @time g(acc, r); @time g(acc, r);
  1.325407 seconds (58.03 k allocations: 2.238 GiB, 13.99% gc time)
  1.205521 seconds (32 allocations: 2.235 GiB, 17.82% gc time)

```

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [September 27, 2018, 4:11am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/17 "2018-09-27T04:11:08Z")

</div>

Yeah, that one wasn’t an improvement

```julia
function revacc3(x)
  pushfirst!(x, 0);
  accumulate!(-, x,x, init = sum(x));
  pop!(x); 
  x;
  end;

@time revacc3(x)
0.328 sec (4 alloc, 160 bytes)

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 27, 2018, 6:38am UTC](https://discourse.julialang.org/t/how-to-accumulate-from-right-efficiently/15490/18 "2018-09-27T06:38:49Z")

</div>

Shouldn’t the focus be on making this work with `Iterators.reverse`?

```julia
julia> accumulate(+, Iterators.reverse(r))
ERROR: MethodError: no method matching similar(::Base.Iterators.Reverse{Array{Int64,1}}, ::Type{Int64})

```

Apparently, there’s a `similar` method missing. I tried implementing it, but it seems I need a debugger to figure out what’s going on. (Time to learn Rebugger.jl!)