我应该使用dict还是list？

Question

我想循环一个大的二维列表:

authors = [["Bob", "Lisa"], ["Alice", "Bob"], ["Molly", "Jim"], ... ]

并获取一个列表,其中包含作者中出现的所有名称.

当我遍历列表时,我需要一个容器来存储我已经看过的名字,我想知道我是否应该使用列表或字典:

列表:

seen = []
for author_list in authors:
    for author in author_list:
        if not author in seen:
            seen.append(author)
result = seen

用词典:

seen = {}
for author_list in authors:
    for author in author_list:
        if not author in seen:
            seen[author] = True
result = seen.keys()

哪一个更快？还是有更好的解决方案？

Answer 1

你真的想要一个set.集合比列表更快,因为它们只能包含唯一元素,这允许它们实现为哈希表.哈希表允许及时进行成员资格测试(if element in my_set)O(1).这与列表形成对比,其中检查元素是否在列表中的唯一方法是依次检查列表中的每个元素(O(n)及时).

A dict类似于a set,两者都仅允许唯一键,并且两者都实现为哈希表.他们都允许O(1)会员资格测试.区别在于set只有键,而a dict有键和值(这是你在这个应用程序中不需要的额外开销.)

使用a set,并使用a 替换嵌套的for循环以itertools.chain()将2D列表展平为1D列表:

import itertools
seen = set()
for author in itertools.chain(*authors):
    seen.add(author)

或更短:

import itertools
seen = set( itertools.chain(*authors) )

编辑(感谢,@ jamylak)大型列表的内存效率更高:

import itertools
seen = set( itertools.chain.from_iterable(authors) )

列表列表中的示例:

>>> a = [[1,2],[1,2],[1,2],[3,4]]
>>> set ( itertools.chain(*a) )
set([1, 2, 3, 4])

PS:如果您不想找到所有独特的作者,而是想要计算每个作者的次数,请使用collections.Counter一种特殊的字典来优化计数.

以下是计算字符串中字符数的示例:

>>> a = "DEADBEEF CAFEBABE"
>>> import collections
>>> collections.Counter(a)
Counter({'E': 5, 'A': 3, 'B': 3, 'D': 2, 'F': 2, ' ': 1, 'C': 1})