在 2D python 列表中查找元素索引的最快方法

Question

我在二维列表中搜索元素索引的有效实现方面遇到问题。 例如，有两个列表（其中 list2 具有来自 list1 的置换元素）：

list1 = [[0,1],[2,3],[4,5],[6,7,8],[9,10,11],[12,13,14]]

list2 = [[8,2],[1,9],[6,4],[13,5,0],[14,7,10],[12,11,3]]

最后，我想要 list3，它与上述两个列表的大小和形状相同。我需要 list3 看起来像这样，在这个例子中：

list3 = [[3,1],[0,5],[2,3],[2,4,0],[1,4,5],[5,3,4]]

所以第一个元素'3'是list2中子列表的索引，其中子列表是list1中的元素'0'。我希望这是清楚的。主要问题是基于在 list2 中搜索 list1 中的元素。对于大小为 100 000 的更大列表，这真的很难。

我试过这段代码，其中包含 4 个“for 循环”和另一个基于 np.argwhere 的代码，但是 numpy 实现更耗时。

第一次实施

for index1, sublist1 in enumerate(list1):
    for i in range(len(sublist1)):

        for index2, sublist2 in enumerate(list2):
            for j in range(len(sublist2)):
                if sublist2[j] == sublist[1]:
                    list1[index1][i] = index1
                    list2[index2][j] = index2

第二次实施

for index1, sublist1 in enumerate(list1):
    for i in range(len(sublist1)):
        where = np.argwhere(list2 == sublist1[i])
        list1[index1][i] = where[0, 0]

我希望可以有另一个实现比这两个快得多，特别是对于更大的列表，即 100 000。

Answer 1

您可以从

list2

创建一个临时映射，然后使用它来创建您的输出：

list1 = [[0, 1], [2, 3], [4, 5], [6, 7, 8], [9, 10, 11], [12, 13, 14]]
list2 = [[8, 2], [1, 9], [6, 4], [13, 5, 0], [14, 7, 10], [12, 11, 3]]

m = {v: i for i, t in enumerate(list2) for v in t}
out = [[m[list1[i][j]] for j in range(len(t))] for i, t in enumerate(list2)]

print(out)

印花：

[[3, 1], [0, 5], [2, 3], [2, 4, 0], [1, 4, 5], [5, 3, 4]]

Answer 2

将

list2

转换为dict，其中键是子列表中的每个元素，值是所述子列表的索引。如果有重复项，您将需要格外小心——您现在还不清楚如何处理它们。然后迭代

list1

以创建预期的输出。

list1 = [[0,1],[2,3],[4,5],[6,7,8],[9,10,11],[12,13,14]]
list2 = [[8,2],[1,9],[6,4],[13,5,0],[14,7,10],[12,11,3]]

lookup_dict = {key:idx for idx, sublist in enumerate(list2) for key in sublist}
result = [[lookup_dict.get(key) for key in item] for item in list1]
print(result)

输出

[[3, 1], [0, 5], [2, 3], [2, 4, 0], [1, 4, 5], [5, 3, 4]]

Answer 3

为

list2

中子列表的索引使用映射字典，然后是列表理解：

mapper = {x: i for i, l in enumerate(list2) for x in l}

list3 = [[mapper.get(x, -1) for x in l] for l in list1]

注意。我将

-1

分配给可能缺失的值。此外，如果您在

list2

中有重复项，将使用最后一个索引。

输出：

[[3, 1], [0, 5], [2, 3], [2, 4, 0], [1, 4, 5], [5, 3, 4]]