从集合模块重新发明 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 多次，不包括我在字典中花费的任何时间）下注是恒定的。）

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