Эффективный способ запомнить комбинацию из двух чисел

Я работаю над алгоритмом для подсчета количества способов построить 100 центов, используя бесконечное количество пенни, десятицентовика, пятицентовика и четвертака.

В итоге я пришел к вышеизложенному (который работает AFAIK):

def count_ways(amount)
  num_ways(amount, 0)
end

def num_ways(amount, index)
  return 1 if amount == 0
  return 0 if index >= COINS.length || amount < 0
  num_ways(amount - COINS[index], index) +
  num_ways(amount, index + 1)
end

Теперь я хотел бы запомнить этот алгоритм. Эффективный способ, который я нашел для размышления о запоминании, состоит в том, чтобы рассмотреть, какие входные данные мы многократно передаем в эту функцию. В этом случае я хотел бы запомнить комбинацию параметров суммы и индекса.

Обычно, когда у меня есть два параметра, я создаю массив из двух D для запоминания, но здесь это имеет гораздо меньше смысла. Следовательно, как вы можете запомнить эти два параметра? Есть ли смысл делать что-то подобное?

def count_ways(amount)
  memo = Hash.new { |h, k| h[k] = [] }
  num_ways(amount, 0, memo)
end

def num_ways(amount, index, memo)
  return 1 if amount == 0
  return 0 if index >= COINS.length || amount < 0
  memo[amount - COINS[index], index] ||= num_ways(amount - COINS[index], index)
  memo[amount, index + 1] ||= num_ways(amount, index + 1)

  memo[amount - COINS[index], index] +
    memo[amount, index + 1]
end

ruby recursion memoization dynamic-programming
person segue_segway    schedule 12.07.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я считаю, что нет общего способа реализации мемоизации, когда вы решаете задачу алгоритма. Из-за скорости. Способ, который вы должны выбрать, зависит от вашего алгоритма, входных данных и так далее. Несколько императивных правил:

  • избегайте создания множества экземпляров структуры данных: h = {}; h[ [1,2] ] = 3 создаст COINS.size * amount Arrays только для ключей
  • используйте Array для непрерывных данных и Hash для с промежутками.
  • используйте Hash вместо Array, когда вы не можете предсказать размер данных
  • создайте Array с необходимыми значениями, когда вы можете предсказать размер
    непрерывных данных

Используя эти правила, мемоизация (только в вашем случае, где COINS.size ‹‹ amount и оба данных непрерывны) может выглядеть так:

COINS = [25, 10, 5, 1]

def count_ways(amount)
  # memo is just COINS.size + 1 Array instances
  # a[0] = 1 instead of return 1 if amount == 0
  memo = Array.new(COINS.size){ Array.new(amount).tap{ |a| a[0] = 1 } }
  num_ways(amount, 0, memo)
end

def num_ways(amount, index, memo)
  return 0 if index >= COINS.size || amount < 0

  memo[index][amount] ||=
    num_ways(amount - COINS[index], index, memo) +
    num_ways(amount, index + 1, memo)
end

P.S. Тег dynamic-programming не нужен :)

person Pavel Mikhailyuk    schedule 13.07.2017
comment
Таким образом, создание ключа массива в хэше автоматически сгенерирует несколько хеш-ключей? Меня беспокоит использование 2D-массива в том, что он может быть очень расточительным и ненужным для места. - person segue_segway; 18.07.2017
comment
1. memo = {}; ... memo[ [amount, index] ] = num_ways(... создаст огромное количество Array объектов. Плохо, если скорость имеет значение. Вы можете проверить это с помощью Ruby benchmark. - person Pavel Mikhailyuk; 18.07.2017
comment
2. 2D-массив (мой пример) не является расточительным в этом частном случае, и я описал почему. Вы можете осмотреть memo на финише и найти 0(ноль) неиспользуемых слотов 2D-массива. Поэтому я назвал 2D-массив лучшим выбором в этом случае. - person Pavel Mikhailyuk; 18.07.2017
comment
@Sunny Вы можете улучшить свои навыки работы с алгоритмами в Leetcode. Вот я: leetcode.com/p1366 - person Pavel Mikhailyuk; 18.07.2017

arrow_upward
-1
arrow_downward

Поскольку одинаковые массивы имеют разные идентификаторы объектов, нельзя просто поместить значения в виде массива в хэш-ключ. Однако вы можете преобразовать в строку, чтобы создать простую структуру поиска, например, преобразовать в YAML/JSON.

require 'json'

memo = {}
def memoize(*args, &blk)
  memo[args.to_json] ||= blk.call
end
def num_ways(amount, index)
  memoize(amount, index) do
    # original method body
  end
end

изменить

неважно, я думаю, что ошибаюсь в необходимости использовать to_json. Вы можете просто использовать args внутри memoize, а не args.to_json.

person max pleaner    schedule 12.07.2017
comment
также .to_json не является бесплатным. - person Pavel Mikhailyuk; 13.07.2017
comment
Использование массива в качестве ключа запоминания создает огромное количество экземпляров массива. Не только для сохраненных ключей, но и каждый раз, когда вы читаете из памятки. Это нормально для очень маленьких данных в обычном приложении, но не в спортивном алгоритме. Кстати минус не мой. - person Pavel Mikhailyuk; 13.07.2017