Почему одно из этих динамических программных решений для робота с поиском пути быстрее, чем другое?

Question

Проблема

"В левом верхнем углу сетки находится робот. Робот может двигаться только вправо или вниз. Сетка может содержать недопустимые / заблокированные ячейки, на которые робот не может ступить. Проверьте, есть ли путь к нижней части. правая ячейка в сетке сверху слева. "

Решения

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

Решение 1:

 1  def findPathCached( cache, grid, dstR, dstC, currentRow, currentColumn ):
 2     if currentRow > dstR or currentColumn > dstC or \
 3        grid[currentRow][currentColumn] == 1:
 4         return False
 5
 6     if currentRow == dstR and currentColumn == dstC:
 7         return True
 8
 9     if cache[currentRow][currentColumn] is None:
 10         cache[currentRow][currentColumn] = \
 11             findPathCached( cache, grid, dstR, dstC, currentRow, currentColumn+1 ) or \
 12             findPathCached( cache, grid, dstR, dstC, currentRow+1, currentColumn )
 13
 14     return cache[currentRow][currentColumn]

Решение 2:

 1 def findPathCachedFailed( cache, grid, dstR, dstC, currentRow, currentColumn ):
 2     if currentRow > dstR or currentColumn > dstC or \
 3        grid[currentRow][currentColumn] == 1:
 4         return False
 5
 6     if cache[currentRow][currentColumn]:
 7         return False
 8
 9     if ( currentRow == dstR and currentColumn == dstC ) or \
 10        findPathCachedFailed( cache, grid, dstR, dstC, currentRow, currentColumn+1 ) or \
 11        findPathCachedFailed( cache, grid, dstR, dstC, currentRow+1, currentColumn ):
 12         return True
 13
 14     cache[currentRow][currentColumn] = True
 15     return False

Решение 2 надежно работает быстрее, чем Решение 1. При некоторой синхронизации каждого вызова функции с помощью time.time () в python я вижу более 10000 запусков, среднее время выполнения в секундах для обоих:

Solution 1: 0.004197101092338562
Solution 2: 0.0036973851680755614

Запуская его вручную, Решение 2 очень редко отнимает больше времени, чем Решение 1. Оба решения работают на одной и той же сетке.

Я знаю, что разница невелика, но я думал, что Решение 1 будет лучше, чем Решение 2, поскольку оно кэширует каждый результат, а не только ошибочные пути, поэтому я немного удивлен, что Решение 2 настолько надежно, чем 1.

Может кто-нибудь помочь мне понять, почему Solution 2 работает быстрее?

Answer 1

Правильный способ выяснить это - запустить его под профилировщиком (хотя я не знаю, есть ли хороший профилировщик Python).

Но вот некоторые вещи, которые, я думаю, менее эффективны в решении 1:

1. В решении 1 вы сначала проверяете, достигли ли вы правую нижнюю ячейку, и, если это так, возвращаетесь рано. Если вы не достигли нижней правой ячейки, вы проверяете кеш и, возможно, пропускаете какую-то работу. Поскольку большинство ячеек не являются правыми нижними ячейками, нижний правый тест обычно , а не вызывает ранний возврат.

   В решении 2 вы сначала проверяете кеш и, возможно, возвращаетесь рано. Если проверка кеша не удалась, вы проверяете, достигли ли вы правую нижнюю ячейку. Поэтому, если проверка кеша часто выполняется, вы пропускаете множество проверок в правом нижнем углу, которые вы выполняете в решении 1.

2. В решении 1 вы получаете cache[currentRow][currentColumn] в строке 9 и в строке 14. В решении 2 вы выбираете его только в строке 6. Таким образом, решение 1 выполняет в два раза больше этих выборок, чем решение 2.

Answer 2

Причина на самом деле очень проста: когда функция возвращает True, нет смысла кэшировать результат, потому что этот кэшированный результат никогда не будет прочитан, потому что после этого больше не будет вызовов функции, потому что когда рекурсивный вызов возвращает True (что означает «я нашел путь к ( dstR , dstC )»), весь стек вызовов быстро раскручивается при каждом вызове немедленно возвращает True (все еще означает "Я нашел путь к ( dstR , dstC )").

Итак, это направление мысли:

[& hellip;] Я думал, что Решение 1 будет лучше, чем Решение 2, поскольку оно кэширует каждый результат, а не только ошибочные пути [& hellip;]

не работает, потому что эти дополнительные кеши - это просто бесполезные записи, которые никогда не будут прочитаны (кроме сразу , поскольку, как указывает Роб Майофф, вы используете return cache[currentRow][currentColumn] в решении № 1, но конечно, это можно легко изменить, просто вернув локальную переменную).

Это частично из-за короткого замыкания or; в выражении вроде

findPathCached( cache, grid, dstR, dstC, currentRow, currentColumn+1 ) or \
findPathCached( cache, grid, dstR, dstC, currentRow+1, currentColumn )

второй вызов функции не произойдет, если первый вернет True.

Если вы хотите, чтобы дополнительное кэширование в решении № 1 было полезным, вы можете подумать о проблеме, когда это короткое замыкание невозможно; например, вместо того, чтобы просто возвращать True или False, чтобы указать, возможен ли путь, попробуйте вернуть , сколько путей возможно & mdash; Итак, 0 вместо False, положительное число вместо True и + вместо or. Вы внезапно обнаружите, что Решение № 1 намного быстрее, потому что оно может охватывать всю сетку во времени пропорционально размеру сетки, тогда как Решение № 2 будет повторять огромное количество вызовов и займет гораздо больше времени.

---

Кстати, вы можете решить эту проблему, используя только O (мин ( m , n )) дополнительное пространство вместо O ( mn ) дополнительное пространство, с немного другим подходом, который все еще требует только O ( mn ) времени. В частности: вы можете выполнять итерацию по строкам сетки, и для каждой из них создать список, из которых ячейки в строке доступны из (0, 0). Список для данной строки зависит только от списка из предыдущей строки, поэтому вам не нужно сохранять все старые списки во время итерации. (Это на самом деле O ( n ) дополнительное пространство, но я говорю, что вы можете сделать это в O (мин ( м , * 1068) * n )) дополнительное пространство, потому что вы можете начать с проверки, какое измерение больше, и перебирать столбцы вместо строк, если выясняется, что строки длиннее столбцов.)

Answer 3

Это быстрее

 6     if cache[currentRow][currentColumn]:
 7         return False

чем

 6     if currentRow == dstR and currentColumn == dstC:
 7         return True

Это только проверяет, существует ли объект, я думаю. Я не вижу сравнения ценностей. Я также думаю, что он быстрее возвращается и останавливает остальной код от исключения.

Я также думаю, что эта строка из решения '1' должна быть также быстрее, чем '2', в '2' вы получаете 2 сравнения и 4 логических операции

 9     if cache[currentRow][currentColumn] is None:

Технически говоря, у вас есть 2 способа оптимизировать это, но проверять операции со списком (матрицами) или просто корректировать операторы if.

Имейте в виду, что некоторые решения могут вызывать «возврат» быстрее.

Без профилировщика я бы просто протестировал одну функцию за другой на некоторых базовых примерах:)