时间戳

首页 > 解决方案 > Numpy：在另一个二维数组中查找二维数组的对应关系，而不考虑顺序

python - Numpy：在另一个二维数组中查找二维数组的对应关系，而不考虑顺序

问题描述

我有两个形状不同的 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]])

我想将每行的索引链接faces到行，vertices以便计算每个顶点的对应区域。面积计算不在这篇文章中，因为它无关紧要。

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

链接规则：对于 中的每一行vertices，如果一行中存在 2 个或多个元素faces，则这些行是链接的。

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

预期结果：

{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})

标签： pythonnumpymultidimensional-arraycorrespondence

解决方案

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

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

您可以通过对数组进行预排序来加快速度。只要您只关心两个数字匹配，这应该是有效的：

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

faces这是通过对的每一行中的每个元素进行二进制搜索来工作的vertices。由于searchsorted返回插入索引，因此您必须检查哪些位置实际匹配该值。模运算符确保插入索引超过数组末尾的元素不会导致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取决于转换为 之前face和之前的原始值，请修改您的循环以仅在索引上运行，并通过索引访问您需要的内容。vertexset

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

推荐阅读