首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >为什么这些动态规划解决方案中的一种比另一种更快?

为什么这些动态规划解决方案中的一种比另一种更快?
EN

Stack Overflow用户
提问于 2019-06-15 00:05:37
回答 3查看 94关注 0票数 1

问题

“在网格的左上角有一个机器人。机器人只能向右移动或向下移动。网格可以包含机器人无法踩到的无效/阻塞的单元格。验证是否有从左上角到右下角单元格的路径。”

的解决方案

我有两种解决方案,这两种解决方案都使用回忆录,以防止重复您在天真的实现中可能做的相同的工作。

解决方案1:

代码语言:javascript
运行
复制
 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:

代码语言:javascript
运行
复制
 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次运行的平均运行时间(秒)为:

代码语言:javascript
运行
复制
Solution 1: 0.004197101092338562
Solution 2: 0.0036973851680755614

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

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

有人能帮助我理解为什么解决方案2运行得更快吗?

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2019-06-15 16:36:11

原因其实很简单:当函数返回True时,没有必要缓存结果,因为缓存的结果永远不会被读取,因为在此之后不会发生更多的函数调用,因为当递归调用返回True (意思是“我找到了通向(dstR,dstC)的路径”)时,整个调用堆栈会迅速展开,每个调用都会立即返回True (仍然意味着“我找到了通向(dstR,dstC)的路径”)。

所以这条思路:

…我认为解决方案1比解决方案2更好,因为它缓存每个结果,而不仅仅是失败路径…。

不起作用,因为这些额外的缓存只是无用的写,永远不会被读取(除了立即,因为正如罗伯梅奥夫所指出的,你在解决方案#1中使用了return cache[currentRow][currentColumn],但这当然可以很容易地更改为只返回一个局部变量)。

这部分是由于or的短路行为;在如下表达式中

代码语言:javascript
运行
复制
findPathCached( cache, grid, dstR, dstC, currentRow, currentColumn+1 ) or \
findPathCached( cache, grid, dstR, dstC, currentRow+1, currentColumn )

如果第一个函数调用返回True,则不会发生第二个函数调用。

如果您希望解决方案1的额外缓存是有用的,您可能会考虑这样的短路是不可能的问题;例如,不只是返回TrueFalse来指示路径是否可能,而是尝试返回多少个路径是可能的-所以,0而不是False,一个正数而不是True,以及+而不是or。您会突然发现解决方案#1的速度要快得多,因为它可以按网格大小的时间比例覆盖整个网格,而解决方案#2将重复大量调用并花费更长的时间。

顺便说一句,您可以只使用O(min(m,n))额外的空间来解决这个问题,而不是使用O(mn)额外的空间,使用一种稍微不同的方法,它仍然只需要O(mn)时间。具体而言:您可以迭代网格中的行,并为每个行创建一个列表,列出行中哪些单元格可以从(0,0)中访问。给定行的列表仅依赖于前一行的列表,因此在迭代时不需要保留所有旧的列表。(这实际上是O(n)额外的空间,但我说您可以在O(min(m,n))额外的空间中这样做,因为您可以首先检查哪个维度更大,如果结果显示行比列长,可以迭代列而不是行。

票数 1
EN

Stack Overflow用户

发布于 2019-06-15 00:19:17

正确的解决方法是在分析器下运行它(尽管我不知道是否有好的Python分析器)。

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

  1. 在解决方案1中,首先检查是否已到达右下角单元格,如果是,则提前返回。如果尚未到达右下角单元格,则检查缓存并可能跳过一些工作。由于大多数单元格不是右下角单元格,所以右下角的测试通常会导致而不是的早期返回。 在解决方案2中,首先检查缓存并可能提前返回。如果缓存检查失败,则检查是否已到达右下角单元格.因此,如果缓存检查经常命中,则跳过许多在解决方案1中执行的右下角检查。
  2. 在解决方案1中,在第9行和第14行获取cache[currentRow][currentColumn],在解决方案2中,只在第6行获取它,所以解决方案1的执行顺序是解决方案2的两倍。
票数 3
EN

Stack Overflow用户

发布于 2019-06-15 01:41:50

这更快

代码语言:javascript
运行
复制
 6     if cache[currentRow][currentColumn]:
 7         return False

代码语言:javascript
运行
复制
 6     if currentRow == dstR and currentColumn == dstC:
 7         return True

我认为它只检查对象是否存在。我看不出比较价值。我还认为它返回得更快,并且阻止了代码的其他部分。

我还认为,从解'1‘的这一行也应该比'2’更快,在'2‘中有2个比较和4个布尔运算

代码语言:javascript
运行
复制
 9     if cache[currentRow][currentColumn] is None:

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

请记住,有些解决方案可以更快地调用“返回”。

如果没有分析器,我将简单地在一些基本的exmaple上测试一个又一个特性:)

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56606322

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档