Double iterator

1

Say there are two arrays a and b having the same length.

How do you collect the sum of all a[i] * b[i] using

  1. normal iterators?
  2. parallel iterators?

Edit - multiple solutions below.

1 Like
2

Here's a code example, if you have any questions on how it works, ask away:

// Normal iterators

let sum: type = a.iter()
    .zip(b.iter())
    .map(|(x, y)| x * y)
    .sum();

Playground
Note that when using that expression, you usually end up needing to specify the type, because the generic constraints on which iterators you can call .sum may confuse rust if you omit the type.

// Parallel iterators
let sum: type = a.par_iter()
    .zip(b.par_iter())
    .map(|(x, y)| x * y)
    .sum();

Playground

All that needs to be changed is to make sure you have rayon as a dependency, rayon's traits in scope (usually through a use rayon::prelude). After that, usually just replacing .iter with .par_iter will work.

1 Like
3

I really love how you used parallel iterators here.

  1. Can you tell me what to add if a and b are ndarrays (as opposed to regular arrays)?
  2. Does the sum take O(n)/linear time or O(logn)/logarithmic time (where n is the size of the arrays)?
4

Hi, I think I can answer those even though I’ve never used rayon or ndarray myself personally.

  • ndarray’s Array type implements the IntoParallelIterator trait from rayon, so the drop-in-replacement approach of replacing the .iter() with .par_iter() ought to just work for those, too, as long as you activate the rayon feature for your ndarray dependency (in your Cargo.toml).
  • Summation of an array always needs (at least) 𝑂(𝑛) time, simply because of the fact that at least 𝑛−1 addition operations need to be carried out. Parallelization can always only give you a constant factor of speed-up which is potentially very relevant in practice but makes no difference in terms of big-𝑂-notation computational complexity.
4 Likes
5

for ndarray:

1 Like
6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.