<p>要了解为什么某些代码比其他代码运行得更快,您应该对其进行分析。在Python中,开始分析的最简单方法是运行:</p>
<pre><code>python -m cProfile <script.py>
</code></pre>
<p>在我的例子中,我编写了一个简单的脚本来调用慢解决方案或快解决方案:</p>
^{pr2}$
<p>然后我使用<code>SlowSolution</code>和<code>FastSolution</code>运行脚本。以下是使用<code>SlowSolution</code>生成的探查器结果:</p>
<pre><code>$ 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}
</code></pre>
<p>和<code>FastSolution</code>:</p>
<pre><code>$ 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}
</code></pre>
<p>一开始看输出可能有点奇怪,但是我们真正感兴趣的是<code>tottime</code>列。它告诉我们我们在一个特定函数内花费了多少时间。在</p>
<p>如您所见,脚本几乎所有的时间都在<code>{built-in method _collections._count_elements}</code>内。这是<code>Counter</code>使用的一个内部方法,我们可以推断每次创建计数器时都会调用该方法(比如<code>collections.Counter(p)</code>)。在</p>
<p>为了使代码更快,您应该少调用<code>collections.Counter(...)</code>次数和/或使用更短的字符串。在慢版本中,您要计算<code>len(p)</code>个字符<code>len(s)</code>次。这有一个<code>O(sp)</code>的运行时,它是二次的,可以解释为什么它在大的输入上如此慢。在</p>
<p>另一方面,更快的解决方案只对<code>s</code>的每个字符计数一次,这就给了它一个<code>O(s + p)</code>的运行时。这是更快的,并将扩大到更大的投入。在</p>
<p>有关Python评测的更多信息,请参见<a href="https://stackoverflow.com/questions/582336/how-can-you-profile-a-script">How can you profile a python script?</a></p>