Пересечение множества значений, соответствующих заданным ключам из нескольких словарей

Question

Я создаю переменную, которая измеряет размер подвыборки значений для данного ключа в 3 разных словарях.Например, я хочу, чтобы набор значений соответствовал ключу A1 в словаре dict_a, ключу b2 в словаре dict_b и ключу c5 в словаре dict_c (то есть пересечению набора значений, соответствующих заданным ключам из 3 словарей).

Я написал код, который делает это с помощью цикла, следующим образом:

import numpy as np


dict_a = {'a1':[1,3,4], 'a2':[1,5,6,7,8,9,13]} 
dict_b = {'b1':[85,7,25], 'b2':[1,8,10,70], 'b3':[1,5,69,13], 'b4':[1,75,15,30]} 
dict_c = {'c1':[1,3,4], 'c2':[725,58,2,89], 'c3':[5,684,6,8,2], 'c4':[4,8,88,55,75,2,8], 'c5':[8,5,6,28,24,6], 'c6':[8,52,3,58,26,2]} 

keys_a =  list(dict_a.keys())
keys_b =  list(dict_b.keys())
keys_c =  list(dict_c.keys())


a= []
b= []
c= []
size = []
for y in keys_a:
    for u in keys_b:
        for w in keys_c:
            a.append(u)
            b.append(w)
            c.append(y)

            # Define subsample
            subsample = np.intersect1d(dict_a[y],dict_b[u],dict_c[w])
            size.append(len(subsample))

Проблема в том, что мои словари намного больше, чем в примере, и это занимает много времени для запуска,

Есть ли способ сделать это более эффективным?

Answer 1

Я собираюсь нарезать это на несколько кусочков. Сначала создайте списки a, b и c, а затем основной список size, используя numpy, и, наконец, сделайте то же самое со списками Python.

Получение списков ключей

Итак, если мы посмотрим, то c на самом деле список ключей от dict_a и так далее. Я собираюсь предположить, что это специально, но если это не так, замените y на key_a, и вы поймете, что я имею в виду.

Мы можем легко вычислить это заранее, не входя в основной цикл. Каждый элемент просто повторяется произведением количества ключей в двух других списках. Мы можем сделать это с чем-то вроде:

from itertools import repeat, chain


def key_summary(dict_1, dict_2, dict_3):
    count = len(dict_2) * len(dict_3)
    return chain(*(repeat(k, count) for k in dict_1.keys()))


a = list(key_summary(dict_b, dict_a, dict_c))
b = list(key_summary(dict_c, dict_a, dict_b))
c = list(key_summary(dict_a, dict_b, dict_c))

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

Получение списка размеров

Не думаю, что вы правильно используете функцию intersect1d(). В документах говорится, что третий аргумент - assume_unique, что, как я думаю, вы не пытаетесь сделать. Я предполагаю, что вы хотите, чтобы элементы, которые появляются во всех списках, можно сделать одним из способов:

np.intersect1d(np.intersect1d(val_a, val_b), val_c))

Это предлагает способ оптимизации цикла. Вместо того, чтобы вычислять пересечение val_a и val_b внутри каждого цикла, мы можем вместо этого сделать это один раз и использовать его снова.

for val_a in dict_a.values():
    for val_b in dict_b.values():
        # Get the intersection of a and b first
        cache = np.intersect1d(val_a, val_b)

        if not len(cache):
            # Our first two sets have nothing in common, we know that we are
            # just going to add a bunch of zeros for everything in dict_c
            size.extend(repeat(0, len(dict_c)))
        else:
            size.extend(
                len(np.intersect1d(cache, val_c)) for val_c in dict_c.values())

Это также позволяет нам применить еще одну оптимизацию, которая вообще пропускает цикл по dict_c, если в пересечении val_a и val_b ничего нет. Мы также можем сделать что-то подобное, если val_a когда-либо будет пустым.

В качестве окончательной оптимизации у вас всегда должно быть dict_a быть самым маленьким и dict_c самым большим, поскольку это дает нам лучший шанс пропустить шаги.

Выполнение вышеизложенного позволило мне увеличить скорость примерно на 200% (1.493 мс -> 0,8 мс в данном примере).

Получение списка размеров (с использованием наборов Python)

Я предполагаю, что вы используете веские функции по уважительной причине, но если они не являются необходимыми, вы можете преобразовать свои списки в наборы, которые очень быстрые для выполнения пересечений в Python. Мы можем следовать довольно похожему подходу, как указано выше:

dset_a = {k: set(v) for k, v in dict_a.items()}
dset_b = {k: set(v) for k, v in dict_b.items()}
dset_c = {k: set(v) for k, v in dict_c.items()}

size = []
for val_a in dset_a.values():
    for val_b in dset_b.values():
        cache = val_a & val_b

        if not cache:
            size.extend(repeat(0, len(dict_c)))
        else:
            size.extend(len(cache & val_c) for val_c in dset_c.values())

Это значительно быстрее в данном примере. Это заняло 0,019 мс против 1,493 мс для оригинала (примерно в 80 раз быстрее!).

Answer 2

Как насчет использования наборов?

size = []
for y in keys_a:
    for u in keys_b:
        for w in keys_c:
            common = set.intersection(set(dict_a[y]),
                                      set(dict_b[u]),
                                      set(dict_c[w]))
            size.append(len(common))

Вычисление пересечения множеств также должно выполняться намного быстрее, чем сначала преобразовывать список чисел в массивы и затем использовать np.intersection.

Вы можете использовать этот подход с любыми типами хэширования в ваших списках.