如何高效检查数组是否包含特定数组？顶点去重性能优化求助

你的问题核心在于数组是引用类型：原生的includes()或者直接用==比较的是数组的引用地址，而非数组的内容，所以无法正确判断两个内容相同的顶点数组是否相等。而你当前的findOne函数是线性遍历，每次检查都要完整遍历output数组，当output规模变大且函数被调用上万次时，效率自然会极低。

优化思路：用哈希表（Set/Map）实现O(1)时间复杂度的查找 #

我们可以把每个顶点数组转换成唯一标识的字符串键（或数字哈希），利用Set的快速查找特性判断顶点是否已存在——这样每次检查的时间复杂度从O(n)直接降到O(1)，整体性能会有质的提升。

修改方案示例 #

1. 提前初始化存储已存在顶点的Set

在调用Face函数前，先创建一个Set来记录已经处理过的顶点：

const existingVertices = new Set();
const output = [];

2. 替换Face函数中的检查逻辑

把原来的findOne调用替换成Set的has方法，同时将顶点数组转换为唯一字符串键：

function Face(v1, v2, v3) { 
  var df = Math.hypot(v2[0] * 1 - v3[0] * 1, v2[1] * 1 - v3[1] * 1, v2[2] * 1 - v3[2] * 1); 
  if (df != 0) { 
    for (var dp = 0; dp < df; dp += gap) { 
      x = v3[0] * 1 + (v2[0] * 1 - v3[0] * 1) / df * dp; 
      y = v3[1] * 1 + (v2[1] * 1 - v3[1] * 1) / df * dp; 
      z = v3[2] * 1 + (v2[2] * 1 - v3[2] * 1) / df * dp; 
      var ds = Math.hypot(x - v1[0] * 1, y - v1[1] * 1, z - v1[2] * 1); 
      if (ds != 0) { 
        for (var dps = 0; dps < ds; dps += gap) { 
          fx = v1[0] * 1 + (x - v1[0] * 1) / ds * dps; 
          fy = v1[1] * 1 + (y - v1[1] * 1) / ds * dps; 
          fz = v1[2] * 1 + (z - v1[2] * 1) / ds * dps; 
          var ffx = Math.round(fx / gap) * gap; 
          var ffy = Math.round(fy / gap) * gap; 
          var ffz = Math.round(fz / gap) * gap; 
          
          // 生成唯一标识的字符串键
          const vertexKey = `${ffx},${ffy},${ffz}`;
          
          if (check) { 
            if (!existingVertices.has(vertexKey)) { 
              existingVertices.add(vertexKey);
              output.push([ffx, ffy, ffz]); 
            } 
          } else { 
            output.push([ffx, ffy, ffz]); 
          } 
        } 
      } 
    } 
  } 
}

额外优化建议 #

• 如果担心字符串拼接的性能损耗，可以提前计算数字哈希值，比如：ffx * 1e6 + ffy * 1e3 + ffz（根据你的数值范围调整系数，避免哈希冲突），用数字作为Set的键，性能会略高一点。
• 若后续需要从键反查顶点数组，可以用Map<string, number[]>存储，键是字符串，值是对应的顶点数组。

为什么这个方案高效？ #

原来的findOne每次检查都要遍历整个output数组，假设output有1000个元素，调用10000次的话总操作次数是10^7级；而用Set的话，每次检查和添加都是O(1)操作，总操作次数仅为10000次左右，性能提升非常明显。

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