Как запомнить метод генерации многомерного массива

У меня есть метод 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). Как я могу запомнить и/или изменить этот метод, чтобы сократить время выполнения?


ruby optimization algorithm dynamic-programming
person Eric Steen    schedule 13.10.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

С точки зрения сокращения времени выполнения это зависит от того, считаете ли вы 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 чем-то, что действительно требует больших вычислительных ресурсов.

person max pleaner    schedule 13.10.2017