查找公共子数组的索引

Question

我有两个很大的、没有排序的数组（里面是一些xyz坐标），我想找到所有相同的子数组的位置（这些子数组是由3个坐标组成的共同点）。举个例子：

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

你能把每个子数组的位置索引放到一个哈希表里吗？简单来说，就是你需要改变一下你的数据结构。这样一来，在一个循环中，你可以在 O(n) 的时间内（这里的 n 是最大的哈希表的大小），以 O(1) 的速度查询每个哈希表，看看是否有相同的子数组出现在两个或多个哈希表里。

Answer 2

我做了一些进一步的实验，发现了一种专门针对numpy的解决方法：

import numpy as np

a = np.arange(24).reshape(2,4,3)
b = np.arange(24, 36).reshape(2,2,3)

数组b从数组a中接收了两个条目：

b[1,0] = a[0,1]
b[0,1] = a[1,1]

找到共同的条目：

c = np.in1d(a, b).reshape(a.shape)
d = np.in1d(b, a).reshape(b.shape)

检查在所有三个坐标中共同条目出现的位置：

indexesC = np.where(c[:,:,0] & c[:,:,1] & c[:,:,2])
indexesD = np.where(d[:,:,0] & d[:,:,1] & d[:,:,2])

Answer 3

这是一个适用于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]可以返回该行的列索引。