Ruby 3.2前Enumerator::Product最优实现对比及更优方案探究

Ruby 3.2 及以上版本的核心库已内置 Enumerator::Product 类，专门用于实现枚举器的笛卡尔积。但在更早的版本中，我们需要手动实现该功能，下面从性能、内存开销等维度，对比两种递归实现方案，并介绍更简洁高效的替代写法。

一、左右递归实现对比 #

1. 左递归实现 #

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

2. 右递归实现 #

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

性能与内存开销对比 #

• 内存层面：两者均基于枚举器（Enumerator）实现，按需生成元素而非一次性产出所有结果，内存占用可控。但左递归的(*f, e)参数解构会产生更多数组拆分操作，带来细微额外内存开销；右递归的(e, *f)解构更直接，参数拆分开销略低。
• 性能层面：右递归执行效率通常略高于左递归。左递归需先递归处理前n-1个枚举器，再追加当前元素；右递归先遍历当前枚举器元素，再递归处理剩余部分，元素拼接顺序更贴合Ruby数组操作优化，减少了部分数组展开的额外开销。
• 边界兼容性：左递归的参数写法要求必须传入至少一个参数，否则会报错；右递归在空参数时e会被设为nil，能正常返回空数组的枚举器，兼容性更好。

二、更简洁低开销的实现方案 #

迭代式基础实现（简洁优先） #

借助inject方法实现迭代式笛卡尔积，避免递归栈开销：

def cartesian_product(enumerables)
  enumerables.inject([[]]) do |acc, enum|
    acc.product(enum)
  end.to_enum
end

注意：该方案会生成中间数组，若枚举器元素数量庞大，内存占用会显著上升。

枚举器链式优化（性能与内存兼顾） #

完全基于枚举器按需生成元素，避免中间数组的大量占用：

def cartesian_product(enumerables)
  return [[]].to_enum if enumerables.empty?
  enumerables.reduce do |acc, enum|
    Enumerator.new do |y|
      acc.each { |a| enum.each { |b| y << a + [b] } }
    end
  end
end

方案优势 #

• 迭代式实现避免了递归栈开销，处理大量枚举器参数时更稳定。
• 链式优化版内存占用与递归实现相当，但性能更优，减少了递归调用的额外开销。
• 参数处理灵活，空参数时可正常返回空数组的枚举器。

使用示例 #

# 左递归实现调用
left_cartesian_product(['a'..'h', 1..8]).each { |c, r| puts "%s%d" % [c, r] }

# 右递归实现调用
right_cartesian_product(['a'..'h', 1..8]).each { |c, r| puts "%s%d" % [c, r] }

# 迭代优化版调用
cartesian_product(['a'..'h', 1..8]).each { |c, r| puts "%s%d" % [c, r] }

内容的提问来源于stack exchange，提问作者Ugur Kurnaz