python - 使用 __contains__ 对 numpy 数组进行非常缓慢的迭代

Question

我有一个 Nx3 numpy 数组，其中列出了一个曲面的 N 个三角形面的 3 个顶点，以及一个 Nx1 数组，其中包含与每个面对应的值。

我想(尽可能最好地)将这些“面”值转换为“顶点”值，例如通过查找与顶点关联的所有面的平均值。

我当前的解决方案适用于较小的 N 值，但会随着 no 的变化而缩放。面 x 数顶点，这很快变得不切实际:

def face2vertVal(faces, facesVals, verts):
    # INPUT:
    # faces:     Nx3 array of N vertex IDs for N faces
    # facesVals: Nx1 array of some parameter for each face

    # OUTPUT:
    # vertsVals: Px1 array of the mean value in "facesVals" that corresponds
    #            to each vertex

    import numpy as np

    vertsVals = np.zeros(faces.max()+1)

    for vertex in range(0, faces.max()+1):       
        tmpVals = np.zeros(1)
        for row in range(0, faces.shape[0]):
                if faces[row].__contains__(vertex):
                    tmpVals = np.append(tmpVals, facesVals[row])
        vertsVals[vertex] = tmpVals[1:].mean()
        del tmpVals

    return vertsVals

提前致谢。

编辑:矢量化方法非常快，但需要太多内存来容纳 700k 个面和 350k 个顶点。

Answer 1

编辑:

如果内存有问题，您还可以使用该算法的“批处理”版本，它一次只处理有限数量的人脸:

将 numpy 导入为 np

def face2vertVal(faces, faces_values, batch_size=None):
    batch_size = batch_size or len(faces)
    faces = np.asarray(faces)
    faces_values = np.asarray(faces_values)
    vert_idx = np.arange(faces.max() + 1)
    vertex_values = np.zeros(len(vert_idx))
    vertex_counts = np.zeros(len(vert_idx))
    for i in range(0, len(faces), batch_size):
        faces_batch = faces[i:i + batch_size]
        faces_values_batch = faces_values[i:i + batch_size]
        vertex_faces = np.any(faces_batch == vert_idx[:, np.newaxis, np.newaxis], axis=-1)
        vertex_values += np.sum(vertex_faces * faces_values_batch, axis=1)
        vertex_counts += np.count_nonzero(vertex_faces, axis=1)
    return vertex_values / np.maximum(vertex_counts, 0)

# All at once
vertex_values = face2vertVal([[0, 1, 2], [1, 2, 3], [2, 3, 0]], [1, 2, 3])
print(*vertex_values, sep=', ')
# 2.0, 1.5, 2.0, 2.5

# In batches of two
vertex_values_1b = face2vertVal([[0, 1, 2], [1, 2, 3], [2, 3, 0]], [1, 2, 3], 2)
print(*vertex_values_1b, sep=', ')
# 2.0, 1.5, 2.0, 2.5

您可以手动选择 batch_size(或使用一些公式，具体取决于您要使用的内存或其他东西)来平衡速度和内存之间的权衡。

---

你应该以矢量化的方式进行计算，否则会慢很多。这是一种方式:

import numpy as np

def face2vertVal(faces, faces_values):
    faces = np.asarray(faces)
    faces_values = np.asarray(faces_values)
    vert_idx = np.arange(faces.max() + 1)
    vertex_faces = np.any(faces == vert_idx[:, np.newaxis, np.newaxis], axis=-1)
    vertex_values = np.sum(vertex_faces * faces_values, axis=1) / np.maximum(np.count_nonzero(vertex_faces, axis=1), 0)
    return vertex_values

vertex_values = face2vertVal([[0, 1, 2], [1, 2, 3], [2, 3, 0]], [1, 2, 3])
print(*vertex_values, sep=', ')
# 2.0, 1.5, 2.0, 2.5

请注意，这种方法的缺点是，给定 N 面和 P 顶点，它需要 O(N*P) 内存，而非矢量化算法使用 O(max(N, P)) 内存。