Enumerator：：Product for Ruby pre 3.2的实现

枚举数的笛卡尔积已经包含在最新的ruby core中，从3.2版本开始，类为Enumerator::Product。
我的问题是，在以前的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] }

如果有更聪明的方法来实现它，我也很感兴趣，开销更少，代码更少，…我在parameters list中为这两种情况都保留了一个数组，因为left case在（*f，e= nil）中不会表现得很好，并且至少要声明一个参数。

右边的一个很慢，因为它初始化了很多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

个字符
理想情况下，您应该只初始化一个：

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)

的字符串

Enumerator：：Product for Ruby pre 3.2的实现

1条答案

相关问题

热门标签

最新问答