从collections模块重新创建Counter类

Question

只是为了好玩，我试着从collections模块重新发明Counter类。

我的意图很简单。给定一个列表，将元素映射到它出现的频率。

我写的是:

>>> l
['a', 'a', 'b', 'c']
>>> d = {}
>>> for a in l:
    d[a] = l.count(a)
>>> d
{'a': 2, 'c': 1, 'b': 1}

只是想知道，这是好是坏?

Answer 1

让我们把注意力集中在唯一相关的部分:

for a in l:
    d[a] = l.count(a)

这很糟糕，它对每个成员调用.count(), .count()遍历每个成员，所以复杂度是O(n^2)。

这是O(n):

l = ['a', 'a', 'b', 'c']
d = {}
for a in l:
    if a in d: # we saw a before
        d[a] += 1
    else:
        d[a] = 1

Answer 2

这可能更快，你在列表上迭代n * n次;其中n是列表的长度。如果你只是遍历列表，并在频率表中每次遇到该元素时都增加该元素的值，你会做更少的工作(n多次这样做，不包括字典所花费的时间，我打赌这是常数。)

另一方面，你的版本在概念上简单明了。