在没有for循环的情况下，检查元素是否属于字典中与键关联的列表

Question

问题公式：

检查元素是否属于字典中与键关联的值列表，并返回键的索引。

字典中的每个键都与一个值列表相关联。例如：

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

字典中键的数量为30000

elements=[45,65，…，104，…，875]#元素由大约900000整数值组成

算法的作用是什么

在字典中查找每个元素，并返回它所属的键的索引。

例如：

45属于键编号498和875

我试过什么

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

问题出在哪里

嵌套循环的使用效率不高，返回30000个键和900000个元素之间的映射大约需要9个小时。

有什么有效的方法来解决它吗？

Answer 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}

这当然会占用一些内存和处理时间，但之后您将能够几乎在瞬间得到900000个元素中每一个元素的答案。我希望使用这种方法，您的程序将运行大约两秒，而不是9个小时。