Sum all values in a matrix

I've got a DP: Vec<Vec<u32>> matrix.

I'm trying to get the sum of all the values inside.

The code below works totally fine for me:

let res: Vec = DP.iter().map(|x : &Vec| -> i32 { x.iter().sum() }).collect();
res.iter().sum()

However, I'd like to have a shorter version. Something like:

DP.iter().map(|x : &Vec| -> i32 { x.iter().sum() }).collect().iter().sum()

Here I'm getting an error:

> Line 14, Char 66: type annotations needed (solution.rs)
>    |
> 14 |         DP.iter().map(|x : &Vec<i32>| -> i32 { x.iter().sum() }).collect().iter().sum()
>    |                                                                  ^^^^^^^ cannot infer type for `B`
>    |

Is there any way I can specify a type for collect?

What about using https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.flat_map ? With that you can pull the inner iterator and sum all values without the need to collect.

DP.iter().flat_map(|x: &Vec<_>| x.iter()).sum()

I'm currently on the phone so I can't compile the statement right now.

1 Like

Better yet, you dont need the collect. You can just do

let sum: i32 = DP.iter().map(|x| -> i32 { x.iter().sum() }).sum();
2 Likes

Awesome.

Could some kind soul explain what is going on in there? I can't help thinking a couple of nested loops would be clearer and perform better.

Thank you guys! flat_map worked just fine!

Doc says that iterator in rust are pretty much the same as loops in terms of performance: https://doc.rust-lang.org/book/ch13-04-performance.html

And it's a bit easier for people with JS or Py background to use iterators. At least for me.

Hi shirokoff,

I am often assured iterators do not have a performance hit. However in all my attempts to understand them so far there has been a significant performance penalty. Discussion with and suggestions from experts on the forum did not produce any improvement. In the last such case, which involved iterating over large 2D arrays, it was finally conceded that nested loops was the way to go: https://github.com/ZiCog/loop_blocking

In the last six years I have used JS a lot. Almost never using iterators. I find it really hard to relate all that .map. zip. collect stuff to what I actually want to do. There is too much conceptual baggage there for what is simple loop and addition (in this case)

Your 2d array summation seems like such a common situation that I think it calls for some bench marking. My experience so far with such 2d arrays, for example see above, shows that using a Vec of Vecs to store them is already halving the speed over using a proper 2d array in contiguous memory.

Of course, whether any of that is significant depends on ones use case.

All the best.

I feel that in your posts here and in other threads, you are hating on iterators for no good reason. In the thread I'm aware of, you had an experience where Clippy, frankly, misled you to use iterators in a place where they were inappropriate, because you were doing random access, which is the opposite of an appropriate use for iterators, but that's a different rant, and from this experience you seem to have drawn the conclusion that iterators are just always slow.

When you use iterators for iterating over slices, they omit bounds checks, which lets you write code that is as fast or faster than index-based iteration with the guarantee of safety. You don't have to rely on the optimizer or unsafe to elide bounds checks when using iterators. This is the case whether or not you "like" the resulting code. Yes, there are examples in this forum of taking a three-line loop and, under the guise of making it "more idiomatic", writing a 10-line quasi-"functional" monstrosity with control flow that bounces back and forth three times, and I agree that we shouldn't encourage that. But "avoid iterators" is at least equally wrong.

Iterators are a tool like any other: they have appropriate and inappropriate uses. The other thread I linked was clearly an inappropriate use for an iterator. This one is clearly appropriate; in fact, it's basically the ideal iterator:

  • It moves through the data structure in a systematic manner, visiting each element only once.

  • It has no need for bounds checks because there is no direct indexing.

  • It's concise:

    DP.iter().flatten().sum()
    

    (not sure why nobody mentioned flatten() yet. Maybe it hasn't been in the stdlib long enough to soak into the collective consciousness)

That said, you have a really good point here:

Although you can only use a 2D array when the dimensions are known at compile-time, which is not most of the time in my experience, you can still normally get performance wins, for non-jagged arrays, by using a flat Vec and indexing into it with something like i*width + j.

3 Likes

It's actually mentioned in the docs for flat_map, didn't think about it as usually I'm mapping the inner iterator before flattening.

Point taken, trentj.

Believe it or not, I try not to hate on things on purely emotive grounds. I'm still persisting with getting used to using, and reading, iterators. Sadly after my 9 months of intermittent Rust use they still stall my mind when I read them. Like coming across the output of a hash function pasted into the source. It takes a good long while for me to decode them. After which I feel, ah it's a loop over this doing that, grief why did you not just say that in the first place and save me all that time?

You must admit that there is a lot of conceptual overhead in using iterators over a simple for loop over an assignment statement.

Having said that, when you boil it down to:

DP.iter().flatten().sum()

I start to warm up to the idea!

I'm hearten to hear you say that using iterators is not always appropriate.

2 Likes