ruby - 如何内存一个多维数组的生成方法

Question

我有一个table_data 方法，用于为乘法表构建多维数组。表格的第一行和第一列相同，每个单元格包含相应行和列的产品。这是它最终打印的内容:

    2   3   4 . . n

2   4   6   8

3   6   9  12

4   8  12  16
.
.
n

如您所见，有很多可以内存的重复项。下面是生成多维数组的代码:

def table_data(n)
  table_header(n).map do |x|
    table_header(n).map do |y|
      x*y
    end
  end
end

def table_header(n)
  @header_data ||= (1..n).to_a
end

table_data 方法需要二次时间；它正在做双倍的必要工作(对于 x*y 和 y*x)。我如何内存和/或更改此方法以减少运行时间？

Answer 1

就减少运行时间而言，这取决于您是否将x*y 视为可忽略的操作。如果您将其替换为某种 SQL 查询或具有更实际成本的东西，那么缓存它就有意义了。但就大 O 复杂性而言，这里的动态变量是表格的宽度/高度，例如我认为没有减少的好方法的迭代次数。

无论如何，要缓存x*y，你可以像这样制作一个辅助类

class MultiplicationCache
  def initialize
    @cache = {}
  end
  def multiply(a,b)
    @cache[[a,b].sort] ||= a * b
  end
end

# usage
cache = MultiplicationCache.new
puts cache.multiply(1,2) # => 2

同样，除非您将 x*y 替换为计算成本非常高的东西，否则这样做没有任何意义。