#python-3.x #dictionary #itertools
#python-3.x #словарь #python-itertools
Вопрос:
Формулировка проблемы :
Проверьте, принадлежит ли элемент списку значений, связанных с ключом в словаре, и возвращает индексы ключей.
Каждый ключ словаря связан со списком значений. Например :
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 часов.
Есть ли какой-либо эффективный способ решить эту проблему?
Ответ №1:
Что вы хотите, так это создать обратный индекс перед обработкой цикла.
Это должно выглядеть примерно так:
{
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 часов.
Комментарии:
1. Спасибо за ваш ответ. Однако я не уверен, что мне все ясно и как создать этот словарь, изменив индексы ключей и значений
2. Время обработки для построения обратного индекса составляет порядка секунд / минут / часов?
3. Я обновил свой ответ, но на самом деле вам решать, как это сделать. Время обработки для построения обратного индекса включено в мою оценку.