python - 查找公共(public)子数组的索引

Question

我有 2 个大型未排序数组(xyz 坐标的结构化集合)，我试图找到所有相同子数组的位置(由 3 个坐标组成的公共(public)点)。示例:

a = array([[0, 1, 2], [3, 4, 5]])
b = array([[3, 4, 5], [6, 7, 8]])

这里正确的子数组应该是[3, 4, 5]，但也可能有多个相同的子数组。 a 的正确索引为 [0,1]，b 的正确索引为 [1,0]。

我已经通过迭代一个数组的所有点并将它们与另一个数组的每个点进行比较来实现了一种纯 python 方法，但这非常慢。

我的问题是，是否有一种有效的方法来查找两个数组的索引(最好是在 numpy 中，因为我需要数组进行进一步计算)？也许是滚动窗口方法？

Answer 1

Python 可迭代的通用解决方案(不特定于 numpy 或数组)，以线性平均时间工作(O(n+m)，n 是子数组的数量，m 是唯一子数组的数量):

a = [[0, 1, 2], [3, 4, 5]]
b = [[3, 4, 5], [6, 7, 8]]

from collections import defaultdict

indexmap = defaultdict(list)

for row, sublist in enumerate((a, b)):
    for column, item in enumerate(sublist):
        indexmap[tuple(item)].append((row, column))

repeats = dict((key, value) for key, value in indexmap.iteritems() if len(value) > 1)

给予

{(3, 4, 5): [(0, 1), (1, 0)]}

如果您不需要双行索引(列表中的索引和存储的索引)，您可以将循环简化为

for row in (a, b):
    for column, item in enumerate(sublist):
        indexmap[tuple(item)].append(column)

由于 a 将在 b 之前处理，任何重复项都会自动按行编号:

{(3, 4, 5): [1, 0]}

repeats[key][rownum] 返回该行的列索引。