0

多くのリストを含む辞書があります。たとえば、

  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

しかし、このアルゴリズムは非効率的です。このタスクを実行するためのより良いアルゴリズムを知りたいです

4

3 に答える 3

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)) 操作であるためです。これは安価ですが、必要な回数の 2 倍の回数を実行すると合計できます。

于 2013-01-29T13:44:18.253 に答える
3 
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}})
于 2013-01-29T13:48:01.300 に答える
0

リストに重複した数字が含まれていても構わない場合は、 set() タイプでそれを行うことができます

>>> s1 = set([1,2,3,4,5])
>>> s2 = set([3,4,5,6,7,8])
>>> s1 & s2
{3, 4, 5}
于 2013-01-29T13:49:50.583 に答える