Python collections.Counter效率

我使用下面的代码来实现一个函数，该函数可以查找字符串s中所有字符串p的字符串。Python collections.Counter效率

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

大长度的输入字符串s运行时

，它给了我“时间超过限制”在网上的代码测试系统错误。但是，以下代码将不会发生此类问题：

class Solution(object): 
    def findAnagrams(self, s, p): 
     """ 
     :type s: str 
     :type p: str 
     :rtype: List[int] 
     """ 
     ls, lp = len(s), len(p) 
     cp = collections.Counter(p) 
     cs = collections.Counter() 
     ans = [] 
     for i in range(ls): 
      cs[s[i]] += 1 
      if i >= lp: 
       cs[s[i - lp]] -= 1 
       if cs[s[i - lp]] == 0: 
        del cs[s[i - lp]] 
      if cs == cp: 
       ans.append(i - lp + 1) 
     return ans

我知道为什么吗？看来这两个解决方案都使用两个len（p）最大大小的计数器？

来源

2017-04-19 yuhengd

第一个使用远比两个计数器多。它会在每个循环迭代中创建一个新的计数器，然后将其丢弃。不确定这是否是速度差异的原因，但它可能是。 – BrenBarn

要了解为什么某些代码的运行速度比其他代码快，您应该对其进行配置。在Python，上手纹最简单的方法是运行：

python -m cProfile <script.py>

在我的情况，我写了一个简单的脚本，调用要么慢溶液或快速的解决方案：

# Pasted code from original question. 
# Also renamed the slow version to `SlowSolution` and the fast version to `FastSolution`. 
... 

# solution = FastSolution() 
solution = SlowSolution() 

print(solution.findAnagrams('abcdefg' + 'a' * 10000, 'gfedcba' + 'a' * 10000))

然后我只用SlowSolution和FastSolution来运行脚本。下面是我的探查结果使用SlowSolution输出：

$ python -m cProfile counter.py 
[0] 
     100204 function calls (100192 primitive calls) in 2.557 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
    10008 0.015 0.000 2.538 0.000 __init__.py:516(__init__) 
    10008 0.009 0.000 2.522 0.000 __init__.py:585(update) 
     7 0.000 0.000 0.000 0.000 _collections_abc.py:392(__subclasshook__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:16(__init__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:20(__enter__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:26(__exit__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:36(__init__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:52(_commit_removals) 
     9 0.000 0.000 0.000 0.000 _weakrefset.py:58(__iter__) 
    20022 0.007 0.000 0.007 0.000 _weakrefset.py:70(__contains__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:81(add) 
    10008 0.010 0.000 0.017 0.000 abc.py:178(__instancecheck__) 
     7/1 0.000 0.000 0.000 0.000 abc.py:194(__subclasscheck__) 
     1 0.000 0.000 2.557 2.557 counter.py:1(<module>) 
     1 0.000 0.000 0.000 0.000 counter.py:17(FastSolution) 
     1 0.000 0.000 0.000 0.000 counter.py:3(SlowSolution) 
     1 0.017 0.017 2.556 2.556 counter.py:4(findAnagrams) 
    10008 2.490 0.000 2.490 0.000 {built-in method _collections._count_elements} 
     2 0.000 0.000 0.000 0.000 {built-in method builtins.__build_class__} 
     1 0.000 0.000 2.557 2.557 {built-in method builtins.exec} 
     7 0.000 0.000 0.000 0.000 {built-in method builtins.getattr} 
    10008 0.005 0.000 0.022 0.000 {built-in method builtins.isinstance} 
     8/2 0.000 0.000 0.000 0.000 {built-in method builtins.issubclass} 
    30024 0.003 0.000 0.003 0.000 {built-in method builtins.len} 
     1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 
     7 0.000 0.000 0.000 0.000 {method '__subclasses__' of 'type' objects} 
     14 0.000 0.000 0.000 0.000 {method 'add' of 'set' objects} 
     1 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects} 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     7 0.000 0.000 0.000 0.000 {method 'remove' of 'set' objects}

和FastSolution：

$ python -m cProfile counter.py 
[0] 
     146 function calls (134 primitive calls) in 0.005 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     2 0.000 0.000 0.001 0.000 __init__.py:516(__init__) 
     7 0.000 0.000 0.000 0.000 __init__.py:536(__missing__) 
     2 0.000 0.000 0.001 0.000 __init__.py:585(update) 
     7 0.000 0.000 0.000 0.000 _collections_abc.py:392(__subclasshook__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:16(__init__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:20(__enter__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:26(__exit__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:36(__init__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:52(_commit_removals) 
     9 0.000 0.000 0.000 0.000 _weakrefset.py:58(__iter__) 
     8 0.000 0.000 0.000 0.000 _weakrefset.py:70(__contains__) 
     7 0.000 0.000 0.000 0.000 _weakrefset.py:81(add) 
     1 0.000 0.000 0.000 0.000 abc.py:178(__instancecheck__) 
     7/1 0.000 0.000 0.000 0.000 abc.py:194(__subclasscheck__) 
     1 0.000 0.000 0.005 0.005 counter.py:1(<module>) 
     1 0.000 0.000 0.000 0.000 counter.py:17(FastSolution) 
     1 0.004 0.004 0.005 0.005 counter.py:18(findAnagrams) 
     1 0.000 0.000 0.000 0.000 counter.py:3(SlowSolution) 
     1 0.001 0.001 0.001 0.001 {built-in method _collections._count_elements} 
     2 0.000 0.000 0.000 0.000 {built-in method builtins.__build_class__} 
     1 0.000 0.000 0.005 0.005 {built-in method builtins.exec} 
     7 0.000 0.000 0.000 0.000 {built-in method builtins.getattr} 
     1 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance} 
     8/2 0.000 0.000 0.000 0.000 {built-in method builtins.issubclass} 
     6 0.000 0.000 0.000 0.000 {built-in method builtins.len} 
     1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 
     7 0.000 0.000 0.000 0.000 {method '__subclasses__' of 'type' objects} 
     14 0.000 0.000 0.000 0.000 {method 'add' of 'set' objects} 
     1 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects} 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     7 0.000 0.000 0.000 0.000 {method 'remove' of 'set' objects}

输出可以是一个有点陌生，在第一次阅读，但我们在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?

来源

2017-04-19 03:01:00 supersam654

谢谢，这真的很有帮助，这正是我需要学习的东西！ – yuhengd

有创造，计数和比较比列表Counter对象更多的开销。这是你所看到的本质。如果你还想要一个更快的方法，你可以通过将p作为一个元组进行排列，然后根据元组检查s片来完成字典查找器。

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 

    def findAnagrams2(self, s, p): 
     ls, lp = len(s), len(p) 
     cp = collections.Counter(p) 
     cs = collections.Counter() 
     ans = [] 
     for i in range(ls): 
      cs[s[i]] += 1 
      if i >= lp: 
       cs[s[i - lp]] -= 1 
       if cs[s[i - lp]] == 0: 
        del cs[s[i - lp]] 
      if cs == cp: 
       ans.append(i - lp + 1) 
     return ans 

    def findAnagrams3(self, s, p): 
     p_all = tuple(''.join(x) for x in permutations(p,len(p))) 
     return [i for i in range(len(s)) if s[i:i+len(p)] in p_all]

下面是在IPython的使用timeit 3种方法很短的比较：

In [33]: %%timeit 
    ...: sol.findAnagrams('hello world he said eh', 'he') 
    ...: 
1000 loops, best of 3: 259 µs per loop 

In [34]: %%timeit 
    ...: sol.findAnagrams2('hello world he said eh', 'he') 
    ...: 
10000 loops, best of 3: 102 µs per loop 

In [35]: %%timeit 
    ...: sol.findAnagrams3('hello world he said eh', 'he') 
    ...: 
100000 loops, best of 3: 15.5 µs per loop

来源

2017-04-19 03:10:57 James

谢谢！这很有趣。一个可能的问题是当p很大时，p的排列会占用大量的内存空间？ – yuhengd

我们在谈论多大的p？ – James

Python collections.Counter效率

回答

相关问题