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

Question

问题

“在网格的左上角有一个机器人。机器人只能向右或向下移动。网格可以包含机器人无法踏入的无效/阻塞单元格。验证是否有通往底部的路径网格中从左上角开始的右侧单元格。”

解决方案

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

解决方案一:

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

Solution 1: 0.004197101092338562
Solution 2: 0.0036973851680755614

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

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

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

Answer 1

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

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

1. 在解决方案 1 中，您首先检查是否到达了右下角的单元格，如果是，则提前返回。如果您还没有到达右下角的单元格，那么您将检查缓存并可能跳过一些工作。由于大多数单元格不是右下角的单元格，因此右下角的测试通常不会导致提前返回。

   在解决方案 2 中，您首先检查缓存并可能提前返回。如果缓存检查失败，则检查是否已到达右下角的单元格。因此，如果缓存检查经常命中，您将跳过在解决方案 1 中执行的大量右下角检查。

2. 在解决方案 1 中，您在第 9 行和第 14 行获取 cache[currentRow][currentColumn]。在解决方案 2 中，您仅在第 6 行获取它。因此解决方案 1 执行这些提取的数量大约是解决方案 2 的两倍。