Сравните два больших словаря и создайте списки значений для ключей, которые у них есть общего.

У меня есть два словаря типа:

dict1 = { (1,2) : 2, (2,3): 3, (1,3): 3}
dict2 = { (1,2) : 1, (1,3): 2}

В качестве вывода я хочу получить два списка значений для элементов, которые существуют в обоих словарях:

[2,3]
[1,2]

То, что я делаю прямо сейчас, выглядит примерно так:

list1 = []
list2 = []

for key in dict1.keys():
    if key in dict2.keys():
        list1.append(dict1.get(key))
        list2.append(dict2.get(key))

Этот код работает слишком долго, и это не то, что я с нетерпением жду. Мне было интересно, может ли быть более эффективный способ сделать это?

Ответы

Ответ 1

commons = set(dict1).intersection(set(dict2))
list1 = [dict1[k] for k in commons]
list2 = [dict2[k] for k in commons]

Ответ 2

Не используйте dict.keys. На python2.x он создает новый список каждый раз, когда он вызывается (что является операцией O(N) - и list.__contains__ - это еще одна операция O(N) в среднем). Просто полагайтесь на то, что словари являются итерируемыми контейнерами напрямую (с поиском O(1)):

list1 = []
list2 = []

for key in dict1:
    if key in dict2:
        list1.append(dict1.get(key))
        list2.append(dict2.get(key))

Обратите внимание, что на python2.7 вы можете использовать viewkeys для прямого пересечения:

>>> a = {'foo': 'bar', 'baz': 'qux'}
>>> b = {'foo': 'bar'}
>>> a.viewkeys() & b
set(['foo'])

(на python3.x вы можете использовать keys здесь вместо viewkeys)

for key in dict1.viewkeys() & dict2:
    list1.append(dict1[key]))
    list2.append(dict2[key]))

Ответ 3

Вы можете использовать понимание списка в функции zip():

>>> vals1, vals2 = zip(*[(dict1[k], v) for k, v in dict2.items() if k in dict1])
>>> 
>>> vals1
(2, 3)
>>> vals2
(1, 2)

Или как более функциональный подход с использованием объекта просмотра и operator.itemgetter() вы можете сделать:

>>> from operator import itemgetter
>>> intersect = dict1.viewkeys() & dict2.viewkeys()
>>> itemgetter(*intersect)(dict1)
(2, 3)
>>> itemgetter(*intersect)(dict2)
(1, 2)

Контрольная точка с принятым ответом:

from timeit import timeit


inp1 = """
commons = set(dict1).intersection(set(dict2))
list1 = [dict1[k] for k in commons]
list2 = [dict2[k] for k in commons]
   """

inp2 = """
zip(*[(dict1[k], v) for k, v in dict2.items() if k in dict1])
   """
inp3 = """
intersect = dict1.viewkeys() & dict2.viewkeys()
itemgetter(*intersect)(dict1)
itemgetter(*intersect)(dict2)
"""
dict1 = {(1, 2): 2, (2, 3): 3, (1, 3): 3}
dict2 = {(1, 2): 1, (1, 3): 2}
print 'inp1 ->', timeit(stmt=inp1,
                        number=1000000,
                        setup="dict1 = {}; dict2 = {}".format(dict1, dict2))
print 'inp2 ->', timeit(stmt=inp2,
                        number=1000000,
                        setup="dict1 = {}; dict2 = {}".format(dict1, dict2))
print 'inp3 ->', timeit(stmt=inp3,
                        number=1000000,
                        setup="dict1 = {}; dict2 = {};from operator import itemgetter".format(dict1, dict2))

Вывод:

inp1 -> 0.000132083892822
inp2 -> 0.000128984451294
inp3 -> 0.000160932540894

Для словарей длиной 10000 и случайных сгенерированных элементов в 100 циклах с помощью:

inp1 -> 1.18336105347
inp2 -> 1.00519990921
inp3 -> 1.52266311646

Изменить:

Как упоминалось в комментарии @Davidmh в комментарии об отказе в создании исключения для второго подхода, вы можете обернуть код в выражении try-except:

try:
    intersect = dict1.viewkeys() & dict2.viewkeys()
    vals1 = itemgetter(*intersect)(dict1)
    vals2 = itemgetter(*intersect)(dict2)
except TypeError:
    vals1 = vals2 = []

Ответ 4

Это нужно сделать с помощью keys в python3 и viewkeys в python2. Это объекты просмотра, которые ведут себя как наборы, и не требуют дополнительных усилий для их создания... они являются просто "представлениями" основных ключей словаря. Таким образом вы сохраняете конструкцию объектов set.

common = dict1.viewkeys() & dict2.viewkeys()
list1 = [dict1[k] for k in common]
list2 = [dict2[k] for k in common]

dict_views объекты могут пересекаться непосредственно со словарями, поэтому работает следующий код. Я бы предпочел предыдущий образец.

common = dict1.viewkeys() & dict2