问题
“在网格的左上角有一个机器人。机器人只能向右移动或向下移动。网格可以包含机器人无法踩到的无效/阻塞的单元格。验证是否有从左上角到右下角单元格的路径。”
的解决方案
我有两种解决方案,这两种解决方案都使用回忆录,以防止重复您在天真的实现中可能做的相同的工作。
解决方案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可靠地运行得更快。在python中使用time.time()对每个函数调用执行一些计时,我可以看到超过10,000次运行的平均运行时间(秒)为:
Solution 1: 0.004197101092338562
Solution 2: 0.0036973851680755614
手工运行它,解决方案2很少比解决方案1花费更多的时间,这两个解决方案都是在同一个网格上运行的。
我知道差别很小,但我认为解决方案1会比解决方案2更好,因为它缓存每个结果,而不仅仅是失败的路径,所以我有点惊讶,解决方案2比1要好得多。
有人能帮助我理解为什么解决方案2运行得更快吗?
发布于 2019-06-15 16:36:11
原因其实很简单:当函数返回True
时,没有必要缓存结果,因为缓存的结果永远不会被读取,因为在此之后不会发生更多的函数调用,因为当递归调用返回True
(意思是“我找到了通向(dstR,dstC)的路径”)时,整个调用堆栈会迅速展开,每个调用都会立即返回True
(仍然意味着“我找到了通向(dstR,dstC)的路径”)。
所以这条思路:
…我认为解决方案1比解决方案2更好,因为它缓存每个结果,而不仅仅是失败路径…。
不起作用,因为这些额外的缓存只是无用的写,永远不会被读取(除了立即,因为正如罗伯梅奥夫所指出的,你在解决方案#1中使用了return cache[currentRow][currentColumn]
,但这当然可以很容易地更改为只返回一个局部变量)。
这部分是由于or
的短路行为;在如下表达式中
findPathCached( cache, grid, dstR, dstC, currentRow, currentColumn+1 ) or \
findPathCached( cache, grid, dstR, dstC, currentRow+1, currentColumn )
如果第一个函数调用返回True
,则不会发生第二个函数调用。
如果您希望解决方案1的额外缓存是有用的,您可能会考虑这样的短路是不可能的问题;例如,不只是返回True
或False
来指示路径是否可能,而是尝试返回多少个路径是可能的-所以,0
而不是False
,一个正数而不是True
,以及+
而不是or
。您会突然发现解决方案#1的速度要快得多,因为它可以按网格大小的时间比例覆盖整个网格,而解决方案#2将重复大量调用并花费更长的时间。
顺便说一句,您可以只使用O(min(m,n))额外的空间来解决这个问题,而不是使用O(mn)额外的空间,使用一种稍微不同的方法,它仍然只需要O(mn)时间。具体而言:您可以迭代网格中的行,并为每个行创建一个列表,列出行中哪些单元格可以从(0,0)中访问。给定行的列表仅依赖于前一行的列表,因此在迭代时不需要保留所有旧的列表。(这实际上是O(n)额外的空间,但我说您可以在O(min(m,n))额外的空间中这样做,因为您可以首先检查哪个维度更大,如果结果显示行比列长,可以迭代列而不是行。
发布于 2019-06-15 00:19:17
正确的解决方法是在分析器下运行它(尽管我不知道是否有好的Python分析器)。
但是,在解决方案1中,我想有些事情可能效率较低:
cache[currentRow][currentColumn]
,在解决方案2中,只在第6行获取它,所以解决方案1的执行顺序是解决方案2的两倍。发布于 2019-06-15 01:41:50
这更快
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:
从技术上讲,您有两种优化方法,但是检查列表(矩阵)上的操作或更正if语句。
请记住,有些解决方案可以更快地调用“返回”。
如果没有分析器,我将简单地在一些基本的exmaple上测试一个又一个特性:)
https://stackoverflow.com/questions/56606322
复制相似问题