Python 列表理解优化

Question

我在遇到问题时使用了这段代码来检索列表中每个元素的计数：

nums = [1,1,3,2,3,3,4,1,1,4,2,3,3,2,1,3,4,1,2]
print([nums.count(num) for num in set(nums)])

此代码运行良好，但看起来不如此代码高效：

from collections import Counter
nums = [1,1,3,2,3,3,4,1,1,4,2,3,3,2,1,3,4,1,2]
counter = Counter(nums)
print(counter.values())

有人可以向我解释为什么 collections 库比 vanilla 列表理解更快吗？

Answer 1

带Counter的代码大致相当于：

def counter_v1(seq):
    counts = {}
    for x in seq:
        counts[x] = counts.get(x, 0) + 1
    return counts

带.count的代码大致等同于：

def count(seq, x):
    c = 0
    for y in seq:
        if y == x:
            c += 1
    return c

def counter_v2(seq):
    counts = {}
    for x in set(seq):
        counts[x] = count(seq, x)
    return counts

如您所见，函数 counter_v1 对序列进行一次迭代，其中有一个 for-loop。相比之下，函数 counter_v2 对每个不同的元素遍历序列 一次，在另一个 for-loop.

中有一个 for-loop
counter_v1 的运行时间将大致与 len(seq) 成正比，而 counter_v2 的运行时间将大致与 len(seq) * len(set(seq)) 成正比，通常要大得多。

Python 列表理解优化

Python list comprehension optimization

python

algorithm

python-collections