Python：匹配列表和匹配字典，哪个更快？

Question

我有两个很大的列表。每个列表里面又包含了其他列表：

list_1 = [[1, "BMW", "Boston", "01Jan2013"], [37, "Chevrolet", "Denver", "05Jan2013"],
[854, "BMW", "Boston", "01Jan2013"],...]

list_2 = [[1, "Mercedes", "Boston", "01Jan2013"], [37, "Chevrolet", "Denver", "05Jan2013"],
[854, "Toyota", "Boston", "01Jan2013"],...]

这些内部列表里的元素类型总是一样的。

现在我想把list_1中的每个内部列表和list_2中的一个内部列表进行匹配，匹配的依据是内部列表中的第1个、第3个和第4个元素。也就是说：序列号、城市和日期。这些关键元素在list_2中也是一样的。list_1中的一个内部列表在list_2中最多只能找到0个或1个匹配。

那么，最符合Python风格且最快的做法是什么呢？我是否应该把列表转换成字典？

Answer 1

你可以定义一个关键函数，来指定比较的字段：

def item_key(item):
    return tuple(item[i] for i in [0, 2, 3])

这个字段应该是可哈希的，这样你才能把它当作字典的键。然后你可以创建一个从项目键到项目本身的映射，或者如果不同的项目可以共享同一个键的话，也可以创建一个项目列表。

key_to_item2 = dict((item_key(item), item) for item in list2)

现在你可以把list1中的每个项目和字典进行测试。

for item1 in list1:
    item2 = key_to_item2.get(item_key(item1))
    if item2 is None:
        # no match found
    else:
        # item2 in list2 matches item1 in list1

这种方法可以很容易地调整，以便使用其他字段进行匹配，并支持多个匹配。

Answer 2

假设你的 list_1 里不能有重复的元素（根据你的评论），你可以把它转换成一个包含 tuple 的 set，而不是用列表来存放列表。这样的话，你就可以很方便地用 in 操作符来检查某个元素是否在这个集合里。

你需要用元组（tuple）而不是列表（list），因为列表是可变的（也就是说它的内容可以改变），所以它不能放进集合（set）里。而如果你用字典（dict

Answer 3

从速度上来说，你可能会想用字典。无论如何，你都需要遍历一个列表。字典的速度比遍历列表要快，所以你可以把至少一个列表转换成字典。我测试过一个解决方案，处理了20万个条目，和你的一样，分成两个列表，平均花了0.109999秒完成。而用列表的话，速度就慢多了。如果你只是用列表或元组，可能达不到这个速度，除非你的条目顺序能让你用像zip这样的工具。你的序列号似乎是唯一的，所以可以这样做（遍历一个列表，然后比较位置0、2和3的项与字典中的值）：

list_1 = [[1, "BMW", "Boston", "01Jan2013"], [37, "Chevrolet", "Denver", "05Jan2013"],
[854, "BMW", "Boston", "01Jan2013"]]

list_2 = [[1, "Mercedes", "Boston", "01Jan2013"], [37, "Chevrolet", "Denver", "05Jan2013"],
[854, "Toyota", "Boston", "01Jan2013"]]


dict_2 = dict()

for elem in list_2:
    dict_2[elem[0]] = elem[1:]

for item in list_1:
    if dict_2[item[0]][1:] == item[2:]:    # Have to offset the index since dict list only has three elements
        print item


[1, 'BMW', 'Boston', '01Jan2013']
[37, 'Chevrolet', 'Denver', '05Jan2013']
[854, 'BMW', 'Boston', '01Jan2013']

一旦你把第二个列表转换成字典，你只需要遍历一个列表就能得到结果。这个解决方案会返回list_1中每个匹配项的完整子列表，这正是你想要的。如果你想要两个列表中完全匹配的子列表，可以这样做：

for item in list_1:
    if dict_2[item[0]][1:] == item[2:]:
        print item, [item[0]] + dict_2[item[0]]


[1, 'BMW', 'Boston', '01Jan2013'] [1, 'Mercedes', 'Boston', '01Jan2013']
[37, 'Chevrolet', 'Denver', '05Jan2013'] [37, 'Chevrolet', 'Denver', '05Jan2013']
[854, 'BMW', 'Boston', '01Jan2013'] [854, 'Toyota', 'Boston', '01Jan2013']