为什么寻路机器人的这些动态规划解决方案中的一个比另一个更快？

Question

问题

"There's a robot in the top left corner of the grid. The robot can only move right, or down. The grid can contain invalid/blocked cells that the robot cannot step onto. Verify if there is a path to the bottom right cell in the grid from the top left."

解决方案

我有两个解决方案，它们都使用记忆来防止重新做您在天真的实现中可能做的相同工作。

解决方案 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 快运行s。在 python 中使用 time.time() 对每个函数调用进行一些计时，我可以看到超过 10,000 运行s 两者的平均运行时间（以秒为单位）是：

Solution 1: 0.004197101092338562
Solution 2: 0.0036973851680755614

运行手动，解决方案 2 很少比解决方案 1 花费更多的时间。这两个解决方案都是运行针对同一个网格。

我知道差异很小，但我认为解决方案 1 会比解决方案 2 好，因为它缓存了每个结果，而不仅仅是失败的路径，所以我有点惊讶解决方案 2 比 1 可靠得多.

谁能帮我理解为什么解决方案 2 运行更快？

Answer 1

解决这个问题的正确方法是运行它在分析器下（虽然我不知道是否有好的 Python 分析器）。

但我认为在解决方案 1 中有些事情可能效率较低：

在解决方案 1 中，您首先检查是否已到达 bottom-right 单元格，如果是，则您提前 return。如果您还没有到达 bottom-right 单元格，那么您将检查缓存并可能跳过一些工作。由于大多数细胞不是 bottom-right 细胞，bottom-right 测试通常 而不是 导致早期 return.

在解决方案 2 中，您首先检查缓存，并可能 return 尽早检查。如果缓存检查失败，则检查是否已到达 bottom-right 单元格。因此，如果缓存检查经常命中，您将跳过在解决方案 1 中执行的很多 bottom-right 检查。
解决方案1中，你在第9行和第14行获取cache[currentRow][currentColumn]。在解决方案2中，你只在第6行获取它。所以解决方案1执行了两次的顺序这些提取与解决方案 2 一样多。

Answer 2

这样更快

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

比

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

我认为它只检查对象是否存在。我没有看到比较值。我也认为它 returns 更快，并停止执行其余代码。

我还认为，解决方案“1”中的这一行也应该比“2”快，在“2”中你有 2 次比较和 4 次布尔运算

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

从技术上讲，您有两种优化方法，但检查列表（矩阵）上的操作或只是更正 if 语句。

请记住，某些解决方案可以更快地调用 'return'。

没有 profiler，我会简单地在一些基本的例子上测试一个又一个的特性 :)

Answer 3

原因其实很简单：当函数returns True时，缓存结果是没有意义的，因为缓存的结果永远不会被读取，因为no在那之后会发生更多函数调用，因为当递归调用returns True（意思是"I've found a path to (dstR, dstC)"）时，整个调用堆栈会迅速展开，每个调用都会立即returning True（仍然表示 "I've found a path to (dstR, dstC)"）。

所以这个思路：

[…] I had thought that Solution 1 would be better than Solution 2 since it caches every result, not just failed paths […]

不起作用，因为那些额外的缓存只是无用的写入，永远不会被读取（除了立即，因为正如 rob mayoff 指出的那样，您使用 return cache[currentRow][currentColumn] 在解决方案 #1 中，但当然可以很容易地将其更改为 return 一个局部变量）。

部分原因是 or 的 short-circuiting 行为；在像

这样的表达式中

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

如果第一个 returned True.

，则不会发生第二个函数调用

如果您希望解决方案 #1 的额外缓存有用，您可能会考虑一个 short-circuiting 不可能的问题；例如，不只是 returning True 或 False 来指示路径是否可行，尝试 returning how many路径是可能的——因此，0 而不是 False，正数而不是 True，+ 而不是 or。你会突然发现解决方案 #1 快得多，因为它可以在与网格大小成比例的时间内覆盖整个网格，而解决方案 #2 将重复大量调用并花费更长的时间。

顺便说一句，您可以仅使用 O(min(m, n)) extra space，而不是 O(mn) extra space，方法略有不同只需要 O(mn) 时间。具体来说：您可以遍历网格的行，并为每一行创建一个列表，列出行中的哪些单元格可以从 (0, 0) 到达。给定行的列表仅取决于前一行的列表，因此您不需要在迭代时保留所有旧列表。（这实际上是 O(n) 额外的 space，但我说你可以在 O(min(m, n)) extra space 因为您可以从检查哪个维度更大并迭代开始如果事实证明行比列长，则列而不是行。）

为什么寻路机器人的这些动态规划解决方案中的一个比另一个更快？

Why is one of these dynamic programming solutions to a pathfinding robot faster than the other?

python

algorithm

dynamic-programming

memoization

问题

解决方案