检查值是否在列表的列表中并检索元素的索引的有效算法

Question

我的目标是有效地在一个大的list of list(我们以1 MLN个条目为例，每个条目是一个由3个元素组成的列表)中查找包含某个值的元素的索引:

e。g我们取列表a

a = [[0,1,2],[0,5,6],[7,8,9]]

我想检索包含值0的元素的索引，因此我的函数将返回0,1

我的第一次尝试是这样的:

def any_identical_value(elements,index):
for el in elements:
if el == index:
return True
return False

def get_dual_points(compliant_cells, index ):
compliant = [i for i,e in enumerate(compliant_cells) if any_identical_value(e,index)]
return compliant

result = get_dual_points(a,0)

解决方案可以正常工作，但对于大列表的列表来说效率非常低。特别是，我的目标是执行一些查询，这些查询是主列表中值的总数，因此在上面的例子9中使用n_queries = len(a)*3。

有两个问题:

• 列表是实现此任务的良好数据结构吗?
• 有没有更有效的算法解决方案?

Answer 1

您可以一次散列所有索引(单个O(N)传递)，这将允许您在O(1)时间内回答查询。

from collections import defaultdict
d = defaultdict(list)
a = [[0,1,2],[0,5,6],[7,8,9]]
queries = [0,1]
for i in range(len(a)):
for element in a[i]:
d[element].append(i)
for x in queries:
print(d[x])
# prints
# [0, 1]
# [0]

Answer 2

这是一个建议的算法:在列表的列表上迭代一次，以构建一个映射每个的字典。所有的唯一元素所属子列表的索引。

使用这种方法，字典构建所需的时间与列表的列表中的元素总数成正比。那么每个查询都是常量时间。

这需要一个列表字典:

def dict_of_indices(a):
d = {}
for i,l in enumerate(a):
for e in l:
d.setdefault(e, []).append(i)
return d
a = [[0,1,2],[0,5,6],[7,8,9]]
d = dict_of_indices(a)
print( d[0] )
# [0, 1]

Answer 3

您可以创建一个字典，将一个值映射到一组行索引。然后，对于每个查询，您可以简单地查找值，如果它在2D列表中不存在，则返回一个空集:

from itertools import product
a = [[0,1,2],[0,5,6],[7,8,9]]
values = {}
for row, col in product(range(len(a)), range(len(a[0]))):
value_at_index = a[row][col]
values.setdefault(value_at_index, set()).add(row)

print(values.get(0, set()))

这个输出:

{0, 1}

---

如果事先知道每个子列表中的元素是唯一的，那么可以将字典更新行更改为:

values.setdefault(value_at_index, []).append(row)

并将.get()调用改为:

values.get(0, [])

保持输出中索引的顺序。