如何获取列表的共同元素数量

Question

这里有一个字典，里面包含了很多列表，比如：

  list_dic= {
    q1:[1,2,3,4,5]
    q2:[2,3,5]
    q3:[2,5]
    }

我想要找出每个列表中共同的元素数量，比如说，q1和q2的共同元素数量是3，具体是(2,3,5)。

q1={q2:3, q3:2}
q2={q1:3,q3:2}
q3={q1:2, q2:2}

我为这个任务写的代码是：

result = {}
for name, source_list in list_dic.items():
    for target_name, target_list in list_dic.items():
        count = 0
        for item in source_list:
            if item in target_list:
                count+=1
    result[name][target_name] = count 

但是这个算法效率不高，我想知道有没有更好的算法来完成这个任务。

Answer 1

如果你不在意列表里能不能有重复的数字，你可以用set()这种类型来实现。

>>> s1 = set([1,2,3,4,5])
>>> s2 = set([3,4,5,6,7,8])
>>> s1 & s2
{3, 4, 5}

Answer 2

在编程中，有时候我们需要让程序做一些事情，比如在特定的条件下执行某些代码。这就像给程序设定了一些规则，只有当这些规则满足时，程序才会按照我们的要求去做。

例如，如果你想让程序在用户输入的数字大于10时显示一条消息，你就需要用到条件语句。条件语句就像是一个检查点，程序会在这里停下来，看看条件是否成立。如果成立，程序就会执行你设定的代码；如果不成立，程序就会跳过这些代码，继续执行后面的内容。

这样做的好处是，程序可以根据不同的情况做出不同的反应，让它变得更加灵活和智能。

from collections import defaultdict
#Create a default dict. You don;t have to handle KeyError condition
result = defaultdict(dict)
list_dic= {
    'q1':[1,2,3,4,5],
    'q2':[2,3,5],
    'q3':[2,5],
    }
#Convert the value list to set list
set_dict = {k:set(v) for k,v in list_dic.items()}
# For both way mapping, you need permutation i.e. (q1, q2) and (q2, q1)
for k1, k2 in permutations(set_dict.keys(),2):
    # Now `&` is Set Intersection. The Len will return the length of the common elements
    result[k1][k2] = len(set_dict[k1] & set_dict[k2])


result
defaultdict(<type 'dict'>, {'q1': {'q3': 2, 'q2': 3}, 'q3': {'q1': 2, 'q2': 2}, 'q2': {'q1': 3, 'q3': 2}})

Answer 3

我觉得这样做就可以了：

import itertools
import collections

q1 = 'q1'
q2 = 'q2'
q3 = 'q3'

dic_list = {
     q1:[1,2,3,4,5],
     q2:[2,3,5],
     q3:[2,5]
     }

#sets are much more efficient for this sort of thing.  Create a dict
#of the same structure as the old one, only with `set` as values 
#instead of `list`
dic_set = {k:set(v) for k,v in dic_list.items()}

new_dic = collections.defaultdict(dict)
for k1,k2 in itertools.combinations(dic_set,2):
     #to get the count, we just need to know the size of the intersection
     #of the 2 sets.
     value = len(dic_set[k1] & dic_set[k2]) 
     new_dic[k1][k2] = value
     new_dic[k2][k1] = value

print (new_dic)

如果你看评论的话，会发现 combinations 比 permutations 稍微快一点：

import itertools
import collections

q1 = 'q1'
q2 = 'q2'
q3 = 'q3'


dic_list = {
     q1:[1,2,3,4,5],
     q2:[2,3,5],
     q3:[2,5]
     }

dic_set = {k:set(v) for k,v in dic_list.items()}

def combo_solution():
     new_dic = collections.defaultdict(dict)
     for k1,k2 in itertools.combinations(dic_set,2):
          value = len(dic_set[k1] & dic_set[k2])
          new_dic[k1][k2] = value
          new_dic[k1][k2] = value
     return new_dic

def perm_solution():
     new_dic = collections.defaultdict(dict)
     for k1, k2 in itertools.permutations(dic_set,2):
          new_dic[k1][k2] = len(dic_set[k1] & dic_set[k2])
     return new_dic

import timeit
print timeit.timeit('combo_solution()','from __main__ import combo_solution',number=100000)
print timeit.timeit('perm_solution()','from __main__ import perm_solution',number=100000)

结果是这样的：

0.58366894722    #combinations
0.832300901413   #permutations

这是因为 set.intersection 的操作复杂度是 O(min(N,M))——这个操作本身不贵，但如果你做的次数是需要的两倍，那就会累积起来变得比较慢。