0

我想遍历一个大的二维列表：

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()

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

4

6 回答 6

8

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

Adict与 a 相似set，两者都只允许唯一键，并且都实现为哈希表。它们都允许O(1)成员资格测试。不同之处在于 aset只有键，而 a 同时dict具有键和值（这是您在此应用程序中不需要的额外开销。）

使用set, 并将嵌套的 for 循环替换为 anitertools.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：如果您不想找到所有唯一的作者，而是想计算您看到每个作者的次数，请使用 a collections.Counter，一种为计算事物而优化的特殊字典。

下面是一个对字符串中的字符进行计数的示例：

>>> a = "DEADBEEF CAFEBABE"
>>> import collections
>>> collections.Counter(a)
Counter({'E': 5, 'A': 3, 'B': 3, 'D': 2, 'F': 2, ' ': 1, 'C': 1})
于 2012-05-10T08:16:59.250 回答
3

set应该更快。

>>> authors = [["Bob", "Lisa"], ["Alice", "Bob"], ["Molly", "Jim"]]
>>> from itertools import chain
>>> set(chain(*authors))
set(['Lisa', 'Bob', 'Jim', 'Molly', 'Alice'])
于 2012-05-10T08:15:03.527 回答
3

使用 adict或 aset比使用 a快得多list

import itertools
result = set(itertools.chain.from_iterable(authors))
于 2012-05-10T08:15:59.420 回答
2

您可以使用设置 -

from sets import Set

seen = Set()

for author_list in authors:
    for author in author_list:
        seen.add(author)

result = seen

这样您就可以逃避“if”检查，因此解决方案会更快。

于 2012-05-10T08:13:00.080 回答
1

如果您关心查找的性能，列表中的查找是O(n)，而字典中的查找摊销到O(1)。

您可以在此处找到更多信息。

于 2012-05-10T08:16:19.563 回答
1

列表只是按特定顺序存储一堆项目。把你的作者名单想象成一长串的鸽子箱，在箱子里的几篇论文上写着作者的名字。名字按你输入的顺序排列，你可以很容易地在任何特定的分类中找到作者，但是如果你想知道某个特定的作者是否在任何分类中，那么你必须逐个查看直到找到你要的名字。您也可以在任意数量的鸽笼中使用相同的名称。

字典有点像电话簿。给定作者的姓名，您可以非常快速地查看作者是否在电话簿中，并找到与它一起列出的电话号码。但是您只能将每个作者包括一次（只有一个电话号码），并且您不能按照您喜欢的任何顺序将作者放入其中，它们必须按照电话簿有意义的顺序排列。在真正的电话簿中，该顺序是按字母顺序排列的；在 Python 字典中，顺序是完全不可预测的（当您向字典中添加或删除内容时它会发生变化），但 Python 在字典中查找条目的速度甚至比在电话簿中查找条目的速度还要快。

另一方面，集合就像电话簿，只列出姓名，而不是电话号码。您仍然不能多次包含相同的名称，它要么在集合中，要么不在集合中。而且您仍然不能将名称在集合中的顺序用于任何有用的东西。但是您可以非常快速地检查名称是否在集合中。

鉴于您的用例，一组似乎是显而易见的选择。你不关心你看过作者的顺序，或者你看过每个作者的次数，你只需要快速检查你以前是否看过某个作者。

列表不适合这种情况；他们努力以您指定的任何顺序记住重复项，而且搜索速度很慢。但是您也不需要将键映射到值，这是字典所做的。回到电话簿的类比，你没有任何相当于“电话号码”的东西。在您的字典示例中，您所做的相当于编写电话簿，其中每个人的号码都列为True，那么为什么还要列出电话号码呢？

一套，OTOH，正是你所需要的。

于 2012-05-10T08:35:14.590 回答