Pythoncollections.Counter效率
Python collections.Counter efficiency
我正在使用以下代码实现一个函数，该函数在字符串 s 中查找字符串 p 的所有变位词。
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 时，在线代码测试系统中出现 "time exceeds limit" 错误。但是，以下代码将不会出现此类问题：
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)?
的计数器
要了解为什么某些代码 运行 比其他代码快，您应该分析它。在 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}
最初阅读的输出可能有点难运行ge，但我们对 tottime 专栏非常感兴趣。这告诉我们在特定函数中花费了多少时间。
如您所见，脚本几乎所有时间都在 {built-in method _collections._count_elements} 内。这是 Counter 使用的内部方法，我们可以推断每次创建计数器时都会调用它（如 collections.Counter(p)）。
为了使代码更快，您应该使用更短的字符串调用 collections.Counter(...) 更少的次数 and/or。在慢速版本中，您正在计算 len(p) 个字符 len(s) 次。这有一个 运行 的 O(sp) 时间，它是二次方的，解释了为什么它在大输入时如此缓慢。
另一方面，更快的解决方案对 s 的每个字符精确计数一次，这给它一个 运行 时间 O(s + p)。这要快得多，并且会随着更大的输入而扩展。
有关 Python 中分析的更多信息，请参阅 How can you profile a python script?
创建、计数和比较 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
我正在使用以下代码实现一个函数，该函数在字符串 s 中查找字符串 p 的所有变位词。
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 时，在线代码测试系统中出现 "time exceeds limit" 错误。但是，以下代码将不会出现此类问题：
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)?
的计数器要了解为什么某些代码 运行 比其他代码快，您应该分析它。在 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}
最初阅读的输出可能有点难运行ge，但我们对 tottime 专栏非常感兴趣。这告诉我们在特定函数中花费了多少时间。
如您所见，脚本几乎所有时间都在 {built-in method _collections._count_elements} 内。这是 Counter 使用的内部方法，我们可以推断每次创建计数器时都会调用它（如 collections.Counter(p)）。
为了使代码更快，您应该使用更短的字符串调用 collections.Counter(...) 更少的次数 and/or。在慢速版本中，您正在计算 len(p) 个字符 len(s) 次。这有一个 运行 的 O(sp) 时间，它是二次方的，解释了为什么它在大输入时如此缓慢。
另一方面，更快的解决方案对 s 的每个字符精确计数一次，这给它一个 运行 时间 O(s + p)。这要快得多，并且会随着更大的输入而扩展。
有关 Python 中分析的更多信息，请参阅 How can you profile a python script?
创建、计数和比较 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