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

Question

我的目标是高效在一个大列表列表中找到索引（让我们以 100 万个条目为例，每个条目是由 3 个元素组成的列表）索引包含特定值的元素：

例如让我们列出列表 a

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

我想检索包含值 0 的元素的索引，因此我的函数将 return 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)

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

这里有2个问题：

列表是完成此任务的良好数据结构吗？
有没有更高效的算法解决方案？

Answer 1

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

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, [])

保持输出中索引的顺序。

Answer 2

您可以一次对所有索引进行哈希处理（单次 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 3

这是一个建议的算法：在列表的列表上迭代一次，以构建一个将 every 唯一元素映射到 all 的字典它所属的子列表的索引。

使用此方法，dict-building 花费的时间与列表列表中的元素总数成正比。那么每个查询都是constant-time.

这需要列表字典：

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]

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

Efficient algorithm to check if a value is in a list of list and retreive the index of the element

python

algorithm

list