Python集合。计数器效率 [英] Python collections.Counter efficiency
问题描述
我正在使用以下代码来实现一个函数，该函数查找字符串s中所有字符串p的字谜。
I am using the following code to implement a function which finds all anagrams of string p in a string 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
s，它使我在在线代码测试系统中出现时间超出限制错误。但是，以下代码将不会出现此类问题：
when running on large length input string s, it gives me "time exceeds limit" error in the online code testing system. However the following code will work with no such issue:
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）的计数器？
Can I know why? It seems both solution uses two Counters of maximum size of len(p)?
推荐答案
看看为什么某些代码比其他代码运行得更快代码，您应该对其进行分析。在Python中，最简单的分析开始就是运行：
To see why some code runs faster than other code, you should profile it. In Python, the easiest way to get started with profiling is to run:
python -m cProfile <script.py>
在我的情况下，我编写了一个简单的脚本来调用慢速解决方案或快速解决方案： / p>
In my case, I wrote a simple script that calls either the slow solution or the fast solution:
# 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 的探查器结果的输出：
Then I just ran the script using SlowSolution and FastSolution. Here's the output of my profiler results using 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 列确实很感兴趣。这就告诉我们在一个特定函数内花了多少时间。
The output can be a little strange to read at first, but we're really interested in the tottime column. That tells us how much total time we spent inside of a particular function.
如您所见，脚本几乎将所有时间都花费在 Counter 使用的内部方法，我们可以推断每次创建计数器时都会调用该方法（例如 collections.Counter（p））。
As you can see, the script spends almost all of its time inside of {built-in method _collections._count_elements}. That's an internal method used by a Counter which we can infer gets called every time you create a counter (like collections.Counter(p)).
要使代码更快，您应该调用 collections.Counter（...）更少的时间和/或较短的字符串。在慢速版本中，您要计算 len（p）个字符 len 次。该程序的运行时间为 O（sp），它是二次方的，并解释了为什么在大型输入时它是如此之慢。
To make the code faster, you should call collections.Counter(...) fewer times and/or with shorter strings. In the slow version, you're counting len(p) characters len(s) times. This has a runtime of O(sp) which is quadratic and explainswhy it's so slow on large inputs.
On另一方面，更快的解决方案只对 s 个字符进行一次计数，因此其运行时间为 O（s + p）。
On the other hand, the faster solution counts each character of s exactly once which gives it a runtime of O(s + p). This is much faster and will scale with much larger inputs.
有关在Python中进行概要分析的更多信息，请参见如何剖析python脚本？
For more info on profiling in Python, see How can you profile a python script?
这篇关于Python集合。计数器效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
