Double nested loop but with iterators

I'd like to refactor a code with two loops iterating over an array, effectively working on a triangle of a 2D matrix:

let array = [1, 2, 3, 4];
for i in 0..4 {
    for j in 0..i {
        println!("{}", array[i]*array[j])

Can I replace the code with a standard iterator? I'm aware this can be done with izip from itertools, but I'd prefer a std solution.

Cartesian product is nested map/and_then/for_each, not zip.

1 Like

I like using flat_map to build product iterators

Both answers are great, but do not fit to my specific situation.

I have a list of items where I have to iterate over all pairs (Cartesian product), sometimes I need to check only the triangle, i.e. i>j. On other occasions, I have two lists and need to check all pairwise combinations. In each of these scenarios I have to do heavy computations for every pair. At the moment I treat each of these cases with a separate loop block. I thought it would be better to:

  • produce an iterator for each of my cases
  • process the data e.g. with for_each(); in the future I'd like to use rayon for parallel processing.

In other words, I have let data_i: Vec<MyStruct>; and possibly let data_j: Vec<MyStruct>; I think I'd solve my problem by having an iterator going over (&MyStruct,&MyStruct)

I've tried something like:

let queries: Vec<MyStruct> = vec![];
let other_queries: Vec<MyStruct> = vec![];
let iteration_a = (0..queries.len()).flat_map(|i| (0..i)
        .map(move |j| (&queries[i],&queries[j])));
let other_queries: Vec<MyStruct> = vec![];
let iteration_b = (0..queries.len()).flat_map(|i| (0..i)
        .map(move |j| (&queries[i],&other_queries[j])));

This doesn't work because:

4 |         .map(move |j| (&queries[i],&queries[j])));
   |                     - ^^-------^^^^^^^^^^^^^^^^
   |                     | | |
   |                     | | variable captured here
   |                     | returns a reference to a captured variable which escapes the closure body
   |                     inferred to be a `FnMut` closure
   = note: `FnMut` closures only have access to their captured variables while they are executing...
   = note: ...therefore, they cannot allow references to captured variables to escape

I totally understand the reason, but my problem is still open.

I don't think iterators are a proper solution for this problem, because the iterator interface assumes that you pass through a collection once in one direction. You need to pass twice, for outer and nested loop, which means that the iterator would have to cache a potentially unbounded number of already seen values, which isn't efficient.

Basically, your algorithm only makes sense for working with slices. Any reasonable iterator-based implementation would thus be heavily special-cased in favour of working with slices, e.g. be a method on slices, or rely on them in some other way. This makes it unlikely to be among the standard iterator adapters. std certainly won't help you here. You can look in itertools, but personally I doubt it will be there. The explicit indexing looks like the best approach in your case.

The problem here is that you want to move some variables (i) but you don't want to move some other variables (queries). The most general solution is to create new variables with references to the variables you don't want to move, so you'll only move the references:

let queries: Vec<MyStruct> = vec![];
let other_queries: Vec<MyStruct> = vec![];

let queries_ref = &queries;
let other_queries_ref = &other_queries;

let iteration_a =
    (0..queries.len()).flat_map(|i| (0..i).map(move |j| (&queries_ref[i], &queries_ref[j])));
let iteration_b = (0..queries.len())
    .flat_map(|i| (0..i).map(move |j| (&queries_ref[i], &other_queries_ref[j])));

In this case though you can avoid doing that if you do two map steps, one to create a pair of indexes (which will use move) and another to get the references from queries (which won't use move):

let queries: Vec<MyStruct> = vec![];
let other_queries: Vec<MyStruct> = vec![];

let iteration_a = (0..queries.len())
    .flat_map(|i| (0..i).map(move |j| (i, j)))
    .map(|(i, j)| (&queries[i], &queries[j]));
let iteration_b = (0..queries.len())
    .flat_map(|i| (0..i).map(move |j| (i, j)))
    .map(|(i, j)| (&queries[i], &other_queries[j]));
1 Like

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.