C++高效查找重复向量：自研算法性能瓶颈排查

我正在开发一个处理3D网格的R包，其中构造参数化网格的函数会生成重复顶点（长度为3的数值向量），需要查找并合并这些重复顶点。我用Rcpp实现了去重算法，但相比Rvcg包的vcgClean(mymesh, sel = 0)及R基函数duplicated，自研算法速度极慢。

自研算法逻辑 #

• 假设有n个顶点：取顶点1，与顶点2至n逐一比较；
• 取顶点2，与顶点3至n逐一比较（未跳过已标记为重复的顶点，但重复数量少，非性能瓶颈）；
• 以此类推，后续顶点与后续所有顶点比较。

顶点比较的实现方式 #

方式一：自定义近似相等函数验证 #

bool test = nearEqual(v1(0), v2(0)) && nearEqual(v1(1), v2(1)) && nearEqual(v1(2), v2(2));

其中nearEqual函数实现为：

bool nearEqual(double l, double r) {
  return r == std::nextafter(l, r);
}

方式二：矩阵列向量近似比较 #

const Rcpp::NumericMatrix::Column& v1 = Vertices.column(i);
const Rcpp::NumericMatrix::Column& v2 = Vertices.column(j);
bool test = Rcpp::max(Rcpp::abs(v1 - v2)) < 1e-16;

此前尝试过精确相等验证，速度同样很慢。

疑问 #

请问自研算法速度慢的原因是什么？是O(n²)的比较策略？还是nearEqual函数的问题？抑或其他原因？顶点存储在Rcpp的3×n数值矩阵中。

内容的提问来源于stack exchange，提问作者Stéphane Laurent