自定义顶点数组插入查重避免n×n遍历的性能问题问询

方案1：哈希表（平均O(1)插入/查重，整体时间复杂度O(n)） #

• 核心逻辑：额外维护一个存储点坐标的哈希集合，利用哈希表的常数级查找能力避免全量遍历
• 前置要求：为Point类型实现两个基础逻辑
  • 相等判断函数：两个Point的所有坐标分量完全相等时返回true
  • 哈希计算函数：将所有坐标分量组合生成低碰撞率的哈希值，二维点可采用hash(x) * 大质数 + hash(y)的实现方式
• 伪代码实现：

// 全局维护两个存储结构
Array vertexList // 存储原始顶点对象的数组
HashSet coordinateSet // 仅存储Point坐标的哈希集合

func MyFunc(vrtx inpVertex)
{
    point refPt = inpVertex->getPoint();
    if (coordinateSet.contains(refPt)) {
        return;
    }
    coordinateSet.add(refPt);
    vertexList.add(inpVertex);
}

• 注意事项：如果浮点坐标存在精度误差，允许微小偏差判定为同一点的场景，需要先将坐标乘以精度系数取整完成量化后，再做哈希和相等判断。

方案2：有序容器（O(log n)插入/查重，整体时间复杂度O(n log n)） #

• 之前排序漏判的核心原因：未采用全坐标词典序的排序规则，导致坐标相同的点没有被排列到相邻位置。
• 正确实现逻辑：
  • 自定义全坐标排序规则：二维点按x→y的优先级比较，三维点按x→y→z的优先级比较，保证坐标完全相同的点排序后必然相邻
  • 维护有序存储结构，插入前通过二分查找判断是否存在重复坐标
• 伪代码实现：

// 按全坐标词典序排序的顶点数组
Array sortedVertexList

func MyFunc(vrtx inpVertex)
{
    point refPt = inpVertex->getPoint();
    // 二分查找使用和排序规则一致的比较逻辑
    int findPos = binarySearch(sortedVertexList, refPt);
    if (findPos >= 0) {
        return;
    }
    // 插入到对应位置保持数组有序
    sortedVertexList.insert(-findPos - 1, inpVertex);
}

选型建议 #

• 对性能要求高、可接受少量额外内存开销的场景，优先选择哈希表方案
• 对哈希碰撞风险有顾虑、不需要保留原始插入顺序的场景，选择有序容器方案
• 超大规模点云场景可额外引入网格哈希、八叉树等空间索引优化，普通业务场景前两种方案即可满足需求。

内容的提问来源于stack exchange，提问作者sameer karjatkar