Блог

Формулировка проблемы :

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

Каждый ключ словаря связан со списком значений. Например :

 498 : {1299,45,78}
875 :{45,104,200,300,456}
  

Количество ключей в словаре равно 30 000

элементы = [45,65,65,…,104,…, 875] # Elements состоит из примерно 900 000 целых значений

Что делает алгоритм?

Ищет каждый элемент в словаре и возвращает индексы ключей, к которым он принадлежит.

Например :

45 принадлежит ключам с номерами 498 и 875

Что я пробовал?

 for elt in elements:
        Keys_indices_elt = [key for key, list in dictionary.items() if elt in list]
  

В чем проблема?

Использование вложенных циклов неэффективно, и для возврата сопоставления между 30 000 ключей и 900 000 элементов требуется около 9 часов.

Есть ли какой-либо эффективный способ решить эту проблему?

Что вы хотите, так это создать обратный индекс перед обработкой цикла.

Это должно выглядеть примерно так:

 {
    1299: {498},
    45: {498, 875},
    78: {498},
    104: {875},
    # etc.
}
  

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

 rev_idx = {}
for k, v in my_dict.items():
    for e in v:
        if e in rev_idx:
            rev_idx[e].add(k)
        else:
            rev_idx[e] = {k}
  

Это, конечно, потребует некоторой памяти и времени обработки, но тогда вы сможете получить ответ для каждого из 900 000 элементов почти мгновенно. Я ожидаю, что при таком подходе ваша программа будет работать около двух секунд вместо 9 часов.