Ruby 3.2 より前の Enumerator::Product の実装
概要
enumerator のデカルト積は、バージョン 3.2 以降、クラス Enumerator::Product で最新の Ruby コアに含まれています。
私の質問は、Ruby の以前のリリースでの最良の (パフォーマンス、メモリ、オーバーヘッドなど) 実装を再検討することです。
より正確に言うと、私の質問は基本的に、左と右の再帰バージョンの比較に関するものです。
def left_cartesian_product((*f, e))
Enumerator.new do |y|
if e.nil?
y << []
else
left_cartesian_product(f).each { |u|
e.each { |x|
y << [*u, x]
}
}
end
end
end
def right_cartesian_product((e, *f))
Enumerator.new do |y|
if e.nil?
y << []
else
e.each { |x|
right_cartesian_product(f).each { |u|
y << [x, *u]
}
}
end
end
end
# usage sample
xxxx_cartesian_product(['a'..'h', 1..8]).each { |c, r| puts "%s%d" % [c,r] }
より少ないオーバーヘッドとより少ないコードでそれを実装するより賢い方法があれば、私も興味があります… 左の場合は (*f, e= nil) では適切に動作せず、少なくとも 1 つのパラメーターを要求し続けるため、両方の場合の配列をパラメーター リストに保持しました。
解決策
右のものは、より多くの Enumerator オブジェクトを初期化しているため、時間がかかります。
def recursive_right((e, *f))
Enumerator.new do |y|
puts "right - new enumerator"
if e.nil?
y << []
else
e.each { |x|
recursive_right(f).each { |u|
y << [x, *u]
}
}
end
end
end
def recursive_left((*f, e))
Enumerator.new do |y|
puts "left - new enumerator"
if e.nil?
y << []
else
recursive_left(f).each { |u|
e.each { |x|
y << [*u, x]
}
}
end
end
end
input = ["a".."c", [1, 2, 3]]
recursive_left(input).to_a
recursive_right(input).to_a
# =>
# left - new enumerator
# left - new enumerator
# left - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
# right - new enumerator
理想的には、1 つだけを初期化する必要があります。
def enum_product(args, m = [], &)
first, *rest = args
unless first
yield m
return
end
first.each do |i|
enum_product(rest, m + [i], &)
end
end
def product(*args)
Enumerator.new do |y|
puts "product - new enumerator"
enum_product(args) do |enum|
y << enum
end
end
end
input = ["a".."c", [1, 2, 3]]
product(*input).to_a
# =>
# product - new enumerator
# [["a", 1], ["a", 2], ["a", 3], ["b", 1], ["b", 2], ["b", 3], ["c", 1], ["c", 2], ["c", 3]]
または、Enumerable を使用します。
class Product
include Enumerable
def initialize(*args)
@args = args
end
def each
enum_product(@args) do |enum|
yield enum
end
end
private
def enum_product(args, m = [], &)
first, *rest = args
unless first
yield m
return
end
first.each do |i|
enum_product(rest, m + [i], &)
end
end
end
ここに小さなベンチマークがあります:
input = ["a".."c", [1, 2, 3], :x..:z]
expected = Enumerator::Product.new(*input).to_a
puts "Test:"
p recursive_left(input).to_a == expected
p recursive_right(input).to_a == expected
p product(*input).to_a == expected
p Product.new(*input).to_a == expected
require "benchmark"
n = 100_000
Benchmark.bmbm(10) do |x|
x.report(:right) { n.times { recursive_right(input).to_a } }
x.report(:left) { n.times { recursive_left(input).to_a } }
x.report(:product) { n.times { product(*input).to_a } }
x.report(:Product) { n.times { Product.new(*input).to_a } }
end
Test:
true
true
true
true
Rehearsal ----------------------------------------------
right 16.247681 0.044432 16.292113 ( 16.301701)
left 4.062121 0.004015 4.066136 ( 4.068666)
product 3.086748 0.012002 3.098750 ( 3.100267)
Product 2.399628 0.004009 2.403637 ( 2.404921)
------------------------------------ total: 25.860636sec
user system total real
right 16.419361 0.039966 16.459327 ( 16.470319)
left 3.988729 0.011989 4.000718 ( 4.002679)
product 3.098028 0.003985 3.102013 ( 3.104423)
Product 2.364256 0.007983 2.372239 ( 2.373399)