How to `accumulate` from right efficiently?

New to Julia
1

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.

1 Like
2

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

3

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

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
1 Like
5

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

6

sorry, misread the question, thanks for the correction

7 
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> reverse(Iterators.reverse(r))
ERROR: MethodError: no method matching reverse(::Base.Iterators.Reverse{Array{Int64,1}})

while this works, of course

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

It seems hard to get these things to compose well.

8

One way that works:

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

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

9

@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?

10

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.

11

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

12

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

13

Very clever.

1 Like
14

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

1 Like
15

~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

z = accumulate(+, x);
z2 = z[end] .- [0; z[1:end-1]];
16 
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)
17

Yeah, that one wasn’t an improvement

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

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

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