Think Julia Exercise 10.1

Hey,
I am fairly new to Julia and coding. Thus, i still struggle on a lot of things in Julia.
I am trying to solve the exercise 10.1 and would like some help on this, at least where to start.

*Write a function called nestedsum that takes an array of arrays of integers and adds up the elements from all of the nested arrays. For example : *
julia> t = [[1, 2], [3], [4, 5, 6]];

julia> nestedsum(t)
21

4 Likes

Start here:

2 Likes

Well, the first question to ask yourself is which approach you would like to take. There are at least three different possible approaches:

  • Use a for loop
  • Use broadcasting (dot syntax)
  • Use the map function
2 Likes
sum(vcat(t...))
1 Like

A solution using mapreduce looks pretty appealing as well! There is also the option of "flatten"ing the array.

1 Like

Nobody should start Julia with this, for two reasons: 1) It is just using some functions without understanding what they do. 2) It is much slower than a simple implementation using loops:

julia> @btime sum(vcat($t...))
  66.714 ns (1 allocation: 128 bytes)
21

julia> @btime nestedsum($t)
  6.242 ns (0 allocations: 0 bytes)
21


5 Likes
sum(sum.(t))
1 Like
julia> @btime sum(sum.($t))
  31.337 ns (1 allocation: 112 bytes)
21

Not yet :slight_smile:

1 Like

Another possible solution: Look at this method of the sum function:

  sum(f, itr)

  Sum the results of calling function f on each element of itr.


  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> sum(abs2, [2; 3; 4])
  29

 
1 Like

@rafael.guerra I think the OP is asking for help in approaching a Julia programming problem as a learning exercise. So it’s better if we provide guidance without directly providing the answer.

7 Likes

Just to add to this, recursion and multiple dispatch is a really nice way to handle things like this (though rarely the most performant).

E.g. to demonstrate a related example, lets find the largest element of an arbitrarily nested set of arrays:

julia> mymaximum(iter) = maximum(mymaximum.(iter))
mymaximum (generic function with 1 method)

julia> mymaximum(x::Number) = x
mymaximum (generic function with 2 methods)

julia> mymaximum(t)
8

A more performant approach would probably be to use

mymaximum(iter) = mapreduce(mymaximum, max, iter)

but things like mapreduce tend to take a little time for new users to understand.

1 Like

Hi everyone and thank you all for your answers, i’m starting to build an answer, yet i am far from understanding everything you said ^^"

for now this is how it looks like for me :

function nestedsum()

for i=1:3
	sum = sum(cumsum(t[i], dims=1))
	println(sum)
end 

end

Yet, i am still getting an error code when i try to run the function.
“MethodError: no method matching nestedsum(::Array{Array{Int64,1},1})”

I think that i have trouble selecting an array in an array of t, like t[1] would be [1,2],… then adding it together

Looks like nestedsum is a function that takes no arguments, as in f(). You are calling it as in nestedsum(t), which is throwing an error. If you defined it with t as an input, it would work.

Note that the use of cumsum is not quite correct (I’ll leave that to you to debug). More egregiously though, you are defining sum on the left hand side when the right hand side… uses the sum function. This is obviously very dire, as on iteration 2 you will get the error “objects of type Int64 are not callable”

1 Like

Forget about sum, cumsum etc. Try to solve that only using loops.

7 Likes

To expand on the previous poster’s comment, if you can build it with lower-level loops code, then you have the tools to build anything from first principles. Later you can make the code more concise with everything else mentioned above.

2 Likes

The concise options are important to learn but, in this particular case, if one actually faces that problem in real life in a performance-critical code, one should write our own function with loops anyway. It is the fastest approach possible and, if the vectors are large, amenable to vectorization, parallelization, etc. Therefore, writing the loops is not a simple exercise, in my opinion is even the way that problem should be tackled if actually faced in a real code.

1 Like

One thing to keep in mind with the sum function, is that it’s more accurate than a naive loop if I’m not mistaken.

Anyway, you don’t necessarily have to avoid functional approaches in favor of for-loops, just to avoid allocations and gain performance:

nestedsum(vec) = sum(sum, vec)

julia> @btime nestedsum($t)
  9.471 ns (0 allocations: 0 bytes)
7 Likes

Just to provoke, the loop version can be loop-vectorized to be 40% faster than that option:

julia> t = [ rand(1:1000,1000), rand(1:1000,500), rand(1:1000,700) ]

julia> @btime sum(sum, $t)
  152.859 ns (0 allocations: 0 bytes)
1094847

julia> @btime nestedsum($t)
  93.723 ns (0 allocations: 0 bytes)
1094847

But of course, there are functional approaches that are very efficient, and many of which normally one would not know how to write something better. This is not one of such cases, though. And the possibility of writing our custom functions with great performance is what makes Julia great in relation to scripting languages.

1 Like

Could you please revise your input t? As is, the result of sum(sum,t) is over 20 million.

2 Likes

done, sorry, wrong line copied

1 Like