Nested iterators

General Usage
1

I want to nest a couple of Iterators calls, but am not getting the result I expect.

I want to iterate through the cartesian product of a repeated array, except I don’t know ahead of time how many times the array will be repeated. Here’s a hard-coded example of 3 repetitions:

julia> for ii in Iterators.product([3,7], [3,7], [3,7]); println(ii); end
(3, 3, 3)
(7, 3, 3)
(3, 7, 3)
(7, 7, 3)
(3, 3, 7)
(7, 3, 7)
(3, 7, 7)
(7, 7, 7)

In Python, this can be done using the “repeat” keyword:

In [1]: import itertools as it
In [2]: for ii in it.product([3,7], repeat=3): print(ii)
(3, 3, 3)
(3, 3, 7)
(3, 7, 3)
(3, 7, 7)
(7, 3, 3)
(7, 3, 7)
(7, 7, 3)
(7, 7, 7)

It looks like “repeat” isn’t a keyword in Iterators.product, so I thought I could do the same thing with a nested Iterators.repeated call:

julia> for ii in Iterators.repeated([3,7], 3); println(ii); end
[3, 7]
[3, 7]
[3, 7]

julia> for ii in Iterators.product(Iterators.repeated([3,7], 3)); println(ii); end
([3, 7],)
([3, 7],)
([3, 7],)

That obviously doesn’t do what I expect or want.

Questions:

  1. Why does it do what it does instead of what I expect?
  2. How can I accomplish what I want?

PS - this is Julia 1.5.1

1 Like
2

No time to answer 1, but for 2 you could do something like:

a=[ [ 3, 7 ], [3, 7], [3, 7] ]
for ii in Iterators.product(a...); println(ii); end
1 Like
3

It looks like Iterators.repeated([3,7], 3) gives you a single-index iterable of length 3, whose elements are [3,7]. You can confirm that by calling collect on it. So your product call is the same as doing Iterators.product([a,a,a]), which is just one iterable. That’s why that is doing what it’s doing.

Another suggestion to get what you want would be to use fill and splatting. Probably the best analog to your python syntax would be for ii in Iterators.product(fill([3,7], 3)...) ; println(ii) ; end. The splatting syntax is important here, because that’s exactly what changes the arguments given to product from a single iterator (so a trivial product) to three iterators, which is what you want.

As a disclaimer, that is probably not the fastest or most efficient way to implement that thing. But hopefully it helps to understand what’s going on.

4

Like @cgeoga said Iterators.repeated() gives you an iterator that repeats the value N times. But Iterators.product() wants each iterator as it’s own argument, which is basically what the splat (…) is doing. You could do:

Iterators.product(collect(Iterators.repeated([3, 7], 3))...)

But that’s probably getting silly, it creates a iterator to give you the array 3 times, collects all 3 instances into an array then splats it into product. @cgeoga’s fill example is probably the way to go.

5

That’s basically where I started. As I mentioned, I don’t know ahead of time how many repeats I’m going to need.

6

As per iterator - N-Dimensional Cartesian Product of a set in Julia - Stack Overflow, the most compact way to write your desired iterator might be

Interators.product(ntuple(i->[3,7], 3)...)

Splatting the ntuple instead of the Array produced by fill saves the allocation of a temporary Array (and is probably a meaningless optimization in the grand scheme of things).

2 Likes
7

Splatting…wasn’t something I knew was a thing until now. I figured there had to be something “opposite” to collect but I wasn’t sure what it was.

That solves it; both Iterators.product(fill([3,7], 3)...) and Iterators.product(collect(Iterators.repeated([3, 7], 3))...) do the thing I expect.

Thanks for teaching me something new today!

1 Like
8

Yes, a quick benchmark suggests you’re correct:

With ntuple:

julia> @benchmark a1(1000000)
BenchmarkTools.Trial:
  memory estimate:  274.66 MiB
  allocs estimate:  3000000
  --------------
  minimum time:     79.635 ms (7.19% GC)
  median time:      84.754 ms (7.32% GC)
  mean time:        87.578 ms (7.31% GC)
  maximum time:     144.052 ms (5.13% GC)
  --------------
  samples:          58
  evals/sample:     1

With fill:

julia> @benchmark a2(1000000)
BenchmarkTools.Trial:
  memory estimate:  1.31 GiB
  allocs estimate:  20000000
  --------------
  minimum time:     833.216 ms (7.09% GC)
  median time:      835.067 ms (7.13% GC)
  mean time:        841.229 ms (7.02% GC)
  maximum time:     873.048 ms (6.98% GC)
  --------------
  samples:          6
  evals/sample:     1

With Iterators.repeated():

julia> @benchmark a3(1000000)
BenchmarkTools.Trial:
  memory estimate:  1.31 GiB
  allocs estimate:  20000000
  --------------
  minimum time:     894.701 ms (6.87% GC)
  median time:      935.490 ms (6.90% GC)
  mean time:        933.575 ms (6.95% GC)
  maximum time:     960.498 ms (6.70% GC)
  --------------
  samples:          6
  evals/sample:     1

General form of the function being benched:

function a1(it)
  for jj in 1:it
    kk=0
    for ii in Iterators.product(ntuple(i->[3,7], 3)...)
        kk+=1
    end
  end
end
1 Like