1

我有一个函数可以找到两个顶点v1和的共同邻居v2，即那些连接到 v1和的顶点v2：

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh, MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2){
    std::vector<MyMesh::VertexHandle> common_neighbors;

    //iterate over neighbors of v1
    for(MyMesh::VertexVertexIter it1 = mesh.vv_iter(v1); it1.is_valid(); ++it1) {
      //neighbors of v2
      for(MyMesh::VertexVertexIter it2 = mesh.vv_iter(v2); it2.is_valid(); ++it2) {
        if ((*it1)==(*it2)){
            common_neighbors.push_back(*it1);     
        }
      }
    }
    return common_neighbors;

该函数简单地遍历 和 的邻域v1并v2检查是否找到出现在两个邻域中的任何顶点。不幸的是，这个函数似乎是我代码的瓶颈，因此我的问题是在 OpenMesh 中是否有更优化的方法来完成这个？

4

2 回答 2

2

我不是 OpenMesh 方面的专家，但看起来您正在使用一个相当有效的循环器来查找这些顶点对。

您的函数唯一明显的问题是您正在分配和返回std::vector对象。

宣言

std::vector<MyMesh::VertexHandle> common_neighbors;

定义了一个空向量（以及后续push_back的 s 内部调用malloc，其代价出乎意料地昂贵）。您至少可以在这里预先分配大约预期的顶点数量。

如果您为大量（10000+？）个不同的v1, v2对调用此函数，则应将函数的签名更改为

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh,
               MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2,
               std::vector<MyMesh::VertexHandle>& common_neighbors);

并通过那里预先分配common_neighbors。

你可能还应该提供更多的上下文（你如何调用这个函数，你实际上对这些顶点做了什么 - 例如，如果你需要一个v3相邻的两个v1然后v2制作一个三角形面(v1,v2,v3)，那么你可能应该只取一个v1-v2边缘和迭代相邻的三角形...），以便可以提供更多优化。

于 2020-11-13T17:19:31.643 回答
1

要考虑的另一个方面是您有一个嵌套循环。假设common_neighbors是 10 的数量级，那么 v1 和 v2 都至少有 10 个邻居。通过使用unordered_map，我们可以用两个单独的循环来解决这个问题——这意味着 20 次迭代而不是 100 次迭代。更准确地说是 O(n1 + n2) 而不是 O(n1*n2)。

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh, MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2)
{
    std::vector<MyMesh::VertexHandle> common_neighbors;
    std::unordered_map<MyMesh::VertexHandle, bool> candidates;

    for(MyMesh::VertexVertexIter it = mesh.vv_iter(v1); it.is_valid(); ++it) {
        candidates[*it] = true;
    }

    for(MyMesh::VertexVertexIter it = mesh.vv_iter(v2); it2.is_valid(); ++it) {
        if (candidates.find(*it) != candidates.end()) 
            common_neighbors.push_back(*it); 
    }

    return common_neighbors;
}

细节

为了理解我们在这里做什么，让我们首先考虑一个概念上相似的方法，它使用std::vector<MyMesh::VertexHandle> candidates：

  • 第一个循环：将v1的所有邻居添加到候选者
  • 第二个循环：如果在候选中找到v2的邻居，则将其添加到common_neighbors

但是，在向量上查找效率低下（与每次迭代候选向量相同）。这就是为什么我们用 替换候选向量的原因unordered_map，它是一个平均复杂度为 O(1) 的哈希映射（最坏的情况是 O(n) - 但实际上，我们可以假设它是 O(1)）。

加紧

如果将您的调用分组是有意义的（并且是可行的）find_common_neighbors，例如：...MyMesh::VertexHandle & v1, std:vector<MyMesh::VertexHandle> & v2)- 那么，请注意第一个循环（填充候选映射）可以重复用于 v2 中的所有元素。所以我们得到 O(n1 + m * n2) 而不是 O(m * (n1 + n2))，其中 n1 是 v1 的大小，n2 是 v2 中的平均大小，m 是 v2 中的顶点数。

于 2020-11-14T19:47:03.850 回答