Feature #18685
closedEnumerator.product: Cartesian product of enumerables
Description
I'd like to add a new Enumerator class method for generating the Cartesian product of given enumerators.
A product here does not mean an accumulated array of arrays, but an enumerator to enumerate all combinations.
product = Enumerator.product(1..3, ["A", "B"])
p product.class #=> Enumerator
product.each do |i, c|
puts "#{i}-#{c}"
end
=begin output
1-A
1-B
2-A
2-B
3-A
3-B
=end
This can be used to reduce nested blocks and allows for iterating over an indefinite number of enumerable objects.
Implementation notes¶
-
It should internally use
each_entry
instead ofeach
on enumerable objects to make sure to capture all yielded arguments. -
If no enumerable object is given, the block is called once with no argument.
-
It should reject a keyword-style hash argument so we can add keyword arguments in the future without breaking existing code.
-
Here's an example implementation:
# call-seq: # Enumerator.product(*enums) -> enum # Enumerator.product(*enums) { |*args| block } -> return value of args[0].each_entry {} def Enumerator.product(*enums, **nil, &block) # TODO: size should be calculated if possible return to_enum(__method__, *enums) if block.nil? enums.reverse.reduce(block) { |inner, enum| ->(*values) { enum.each_entry { |value| inner.call(*values, value) } } }.call() end
-
Not to be confused with
Enumerator.produce
. 😝
Prior case¶
Updated by Eregon (Benoit Daloze) 10 months ago
- Subject changed from Enumerator.product: Cartesian product of enumerators to Enumerator.product: Cartesian product of enumerables
Updated by Eregon (Benoit Daloze) 10 months ago
Isn't it significantly slower than doing it manually due to all these extra block and method calls etc in between?
Updated by matz (Yukihiro Matsumoto) 9 months ago
Looping class method is an unusual pattern in Enumerable. So I first hesitated, but actually it's the only way to go if we want to introduce `product'.
And the method seems to be convenient. Thus, I accept.
@Eregon (Benoit Daloze) If the performance matters, we can re-implement it in C.
Matz.
Updated by knu (Akinori MUSHA) 9 months ago
Thanks. Performance monsters can also special-case arrays and ranges and omit calls to each_entry to boost performance. 😂
Updated by Eregon (Benoit Daloze) 9 months ago
My performance concern was not about Ruby vs C, writing in C would have the same issues.
What I'm saying is this:
(1..3).each do |i|
["A", "B"].each do |c|
puts "#{i}-#{c}"
end
end
will always be faster than:
Enumerator.product(1..3, ["A", "B"]).each do |i, c|
puts "#{i}-#{c}"
end
because the second has a generic/cannot-do-sensible-inline-cache loop and lots of array allocation and splatting.
So Enumerator.product makes sense when one doesn't know how many enums
to combine, or a large number of them, but for 2-3 it's better performance-wise (and maybe also for clarity) to just use nested each
.
Updated by Eregon (Benoit Daloze) 9 months ago
And between writing Enumerator.product
in Ruby or C I'd prefer a lot in Ruby because it's a million times more readable, and it can be reused by other Ruby implementations :)
Updated by shan (Shannon Skipper) 9 months ago
It might also be nice to require at least one enum
argument, since Enumerator.product #=> [nil]
seems a bit odd. Here's a stab at lazy size:
def Enumerator.product(*enums, **nil, &block)
raise ArgumentError, 'wrong number of arguments (given 0, expected 1..)' if enums.empty?
unless block_given?
return to_enum(__method__, *enums) do
enums.reduce(1) do |acc, enum|
enum_size = enum.size
break unless enum_size
acc * enum_size
end
end
end
enums.reverse.reduce(block) do |inner, enum|
lambda do |*values|
enum.each_entry do |value|
inner.call(*values, value)
end
end
end.call
end
Updated by knu (Akinori MUSHA) 9 months ago
That's actually not a mathematical idea. The 0-ary Cartesian product of sets should be defined as a singleton set for theoretical and practical reasons. It's just like 2^0 equals to 1.
Python's itertools.product aligns with this theory.
import itertools
for i in itertools.product(range(3), range(3)):
print("2-ary: " + repr(i))
for i in itertools.product(range(3)):
print("1-ary: " + repr(i))
for i in itertools.product():
print("0-ary: " + repr(i))
Output:
2-ary: (0, 0)
2-ary: (0, 1)
2-ary: (0, 2)
2-ary: (1, 0)
2-ary: (1, 1)
2-ary: (1, 2)
2-ary: (2, 0)
2-ary: (2, 1)
2-ary: (2, 2)
1-ary: (0,)
1-ary: (1,)
1-ary: (2,)
0-ary: ()
Updated by sawa (Tsuyoshi Sawada) 9 months ago
Updated by knu (Akinori MUSHA) 6 months ago
Updated by marcandre (Marc-Andre Lafortune) 5 months ago
- Is duplicate of Feature #7444: Array#product_set added
Updated by hsbt (Hiroshi SHIBATA) 2 months ago
- Status changed from Open to Closed
https://github.com/ruby/ruby/pull/6197 has been merged for Ruby 3.2