我使用下面的代码来实现一个函数,它在字符串s中查找字符串p的所有anagram
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
ans = list()
pcnt = collections.Counter(p)
for i in range(len(s)):
if collections.Counter(s[i:i+len(p)]) == pcnt:
ans.append(i)
return ans
当运行在大长度的输入字符串上时,在在线代码测试系统中会出现“时间超限”错误。但是,以下代码将不存在此类问题:
^{pr2}$我能知道为什么吗?似乎这两种解决方案都使用两个最大大小为len(p)的计数器?在
要了解为什么某些代码比其他代码运行得更快,您应该对其进行分析。在Python中,开始分析的最简单方法是运行:
在我的例子中,我编写了一个简单的脚本来调用慢解决方案或快解决方案:
^{pr2}$然后我使用
SlowSolution
和FastSolution
运行脚本。以下是使用SlowSolution
生成的探查器结果:和
FastSolution
:一开始看输出可能有点奇怪,但是我们真正感兴趣的是
tottime
列。它告诉我们我们在一个特定函数内花费了多少时间。在如您所见,脚本几乎所有的时间都在
{built-in method _collections._count_elements}
内。这是Counter
使用的一个内部方法,我们可以推断每次创建计数器时都会调用该方法(比如collections.Counter(p)
)。在为了使代码更快,您应该少调用
collections.Counter(...)
次数和/或使用更短的字符串。在慢版本中,您要计算len(p)
个字符len(s)
次。这有一个O(sp)
的运行时,它是二次的,可以解释为什么它在大的输入上如此慢。在另一方面,更快的解决方案只对
s
的每个字符计数一次,这就给了它一个O(s + p)
的运行时。这是更快的,并将扩大到更大的投入。在有关Python评测的更多信息,请参见How can you profile a python script?
创建、计数和比较
Counter
对象的开销比列表的开销大。这就是你所看到的一切的本质。如果您还需要一个更快的方法,您可以通过将p
的排列构建为一个元组,然后对照元组检查s
的片段来完成anagram finder。在下面是IPython中使用
^{pr2}$timeit
的3种方法的简短比较:相关问题 更多 >
编程相关推荐