Numpy：在不考虑顺序的情况下在另一个二维数组中查找二维数组的对应关系

Question

我有两个不同形状的 numpy 矩阵：

vertices = np.array([[ 100, 101, 102, 103,  -1],
                     [ 200, 201, 202, 203, 204],
                     [ 300, 301, 302, 303, 104],
                     [ 505, 506, 507,  -1,  -1]])

faces = np.array([[ 104, 102,  100],
                  [1202, 203, 2000],
                  [ 303, 505,  104],
                  [ 101, 102,  104]])

我想 link faces 中每一行的索引到 vertices 中的行，以便计算每个顶点的相应区域。面积计算不在此post中，因为它无关紧要。

每个顶点可以对应任意数量的面。每个面只能附加到一个顶点。

Link 规则：对于 vertices 中的每一行，如果 faces 行中存在 2 个或更多元素，则这些行被 linked。

预期结果是一个字典，其键是 vertices 的索引，值是相应顶点的 linked 面的计数。

预期结果：

{0: 2.0, 2: 1.0}

我写了一个可行的算法，但我正在寻找一个性能更高的实现：

def area(faces, corresponding_vertices_id):
    skeleton_node_corresponding_area = defaultdict(lambda: 0.)
    for face in faces:
        for skeleton_node, vectex_id in enumerate(corresponding_vertices_id):
            if np.count_nonzero(np.in1d(face, vectice_id)) >=2 :
                area = 1 # Mock action. real area will be compute later
                skeleton_node_corresponding_area[skeleton_node] = skeleton_node_corresponding_area[skeleton_node] + area
                break
    return skeleton_node_corresponding_area

area(faces, vertices)

defaultdict(<function __main__.area.<locals>.<lambda>()>, {0: 2.0, 2: 1.0})

Answer 1

in1d(a, b) 本质上是这样做的（但可能没有中间数组和一些短路）：

(a == b[:, None]).any(axis=0)

您可以通过 pre-sorting 数组加快速度。只要您只关心两个数字匹配，这就应该有效：

vertices.sort(axis=1)

现在你可以做类似的事情

result = defaultdict(float)
for face in faces:
    for i, vertex in enumerate(vertices):
        n = vertex[np.searchsorted(vertex, face) % vertices.shape[1]] == face).sum()
        if n > 2:
            result[i] += 1.
            break

这是通过在 vertices 的每一行中对 faces 的每个元素进行二进制搜索来实现的。由于 searchsorted returns 插入索引，您必须检查哪些位置实际匹配该值。模运算符确保插入索引超过数组末尾的元素不会导致 IndexError。处理该问题的正确方法是有条件的，但是将它们的索引设置为零会更快，并且可以正常工作，因为它们都不匹配。 break 加快了速度，因为你提到每个面只能属于一个顶点。

这仍然不是很快。假设一对形状为 (M, N) 的数组，你的算法是 O(M^2 * N^2)。这一个执行 O(M * N * log(N)) 排序，然后是 O(M * M * N * log(N)) 的嵌套循环（每次搜索都是 O(log(N))，但必须对行的每个元素执行），总共O(M^2 * N * log(N)).

一种更高效的方法（一旦你超过了额外开销很重要的点）将使用 python sets，因为搜索单个元素是 O(1) :

vertices = [set(vertex) for vertex in vertices]
faces = [set(face) for face in faces]
result = defaultdict(float)

for face in faces:
    for i, vertex in enumerate(vertices):
        if len(face & vertex) > 2:
            result[face] += 1
            break

如果 area 在转换为 set 之前取决于 face 和 vertex 的原始值，请将循环修改为仅在索引上运行 , 并通过索引访问您需要的内容。

这是 O(M * M * N) 因为 face & vertex 是一个 O(N) 操作。如果您有 non-random 值分布，您可能可以做一些事情来降低外循环的复杂性，例如，通过对行进行排序。

Numpy：在不考虑顺序的情况下在另一个二维数组中查找二维数组的对应关系

Numpy: Finding correspondences of 2D Array in another 2D array, without taking order in account

python

numpy

multidimensional-array

correspondence