优化高效坐标索引C#代码：900k节点下如何提速或并行处理？

我有一个存储三角形节点XYZ坐标的三角形列表，需要从中生成节点列表和三角形节点索引列表，要求距离相近的节点使用同一索引。当前需处理约900k个节点，现有C#代码如下，请问是否有方法提升运行速度或实现并行处理？

// ensureNodeAt
// return node index. Avoid duplicates.
public int ensureNodeAt(XYZ p, double eps_dist = 1e-9)
{
    // backwards - most likely the one we seek is at the back
    for (int i = nodes.Count - 1; i >= 0; --i)
    {
        XYZ v = nodes[i].v - p;
        if (v.X * v.X + v.Y * v.Y + v.Z * v.Z < eps_dist)
        { return i; }
    }
    // Must add a new node
    nodes.Add(p);
    return nodes.Count - 1;
}

void work(List<XYZ> triangles){
    tri = new List<Tri>(triangles.Count / 3); // triangle indices
    nodes = new List<XYZ>(triangles.Count); // triangle nodes
    for (int i = 0; i < triangles.Count; i += 3)
    {
        var a = triangles[i];
        var b = triangles[i + 1];
        var c = triangles[i + 2];
        tri.Add(new Tri(ensureNodeAt(a, eps_dist), ensureNodeAt(b, eps_dist), ensureNodeAt(c, eps_dist)));
    }
}

一、核心性能优化：替换线性查找为空间索引 #

当前ensureNodeAt用全局线性遍历，时间复杂度为O(n)，900k节点场景下整体复杂度会恶化到O(n²)，这是最大性能瓶颈，可通过以下方式解决：

1. 哈希表+坐标离散化（最实用） #

通过将浮点数坐标按精度eps_dist离散化，把相近坐标映射到同一个哈希键，将查找复杂度降到O(1)：

private Dictionary<long, int> _nodeHash = new Dictionary<long, int>();

// 按精度离散化坐标生成哈希键
private long GetHashKey(XYZ p, double eps)
{
    long x = (long)Math.Round(p.X / eps);
    long y = (long)Math.Round(p.Y / eps);
    long z = (long)Math.Round(p.Z / eps);
    // 移位组合减少哈希冲突
    return (x << 40) | (y << 20) | z;
}

public int ensureNodeAt(XYZ p, double eps_dist = 1e-9)
{
    double eps = Math.Sqrt(eps_dist); // 对应平方距离的坐标精度
    long key = GetHashKey(p, eps);
    
    if (_nodeHash.TryGetValue(key, out int index))
    {
        // 二次校验避免哈希冲突误判
        XYZ v = nodes[index] - p;
        if (v.X*v.X + v.Y*v.Y + v.Z*v.Z < eps_dist)
        {
            return index;
        }
    }
    
    int newIndex = nodes.Count;
    nodes.Add(p);
    _nodeHash[key] = newIndex;
    return newIndex;
}

2. 空间分区结构（Octree/均匀网格） #

如果哈希冲突概率高，可将空间划分为网格或八叉树，查找时仅检查目标点所在分区及相邻分区的节点，进一步缩小查找范围，适合高精度或分布极不均匀的节点场景。

二、并行处理实现思路 #

节点去重存在全局状态依赖，直接并行遍历三角形会有线程安全问题，推荐采用批量预处理+并行映射的流程：

批量预处理并行方案 #

void workParallel(List<XYZ> triangles)
{
    // 1. 提取所有节点并并行去重
    var allNodes = triangles.AsParallel()
                            .SelectMany((_, i) => 
                            {
                                int idx = i * 3;
                                return new[] { triangles[idx], triangles[idx+1], triangles[idx+2] };
                            })
                            .Distinct(new XYZEqualityComparer(1e-9))
                            .ToList();
    
    // 2. 建立节点到索引的映射字典
    var nodeMap = allNodes.Select((p, idx) => (p, idx))
                          .ToDictionary(item => item.p, item => item.idx, new XYZEqualityComparer(1e-9));
    
    // 3. 并行生成三角形索引列表
    tri = triangles.AsParallel()
                   .Select((_, i) => 
                   {
                       int idx = i * 3;
                       return new Tri(
                           nodeMap[triangles[idx]],
                           nodeMap[triangles[idx+1]],
                           nodeMap[triangles[idx+2]]
                       );
                   })
                   .ToList();
    nodes = allNodes;
}

// 自定义XYZ相等比较器
public class XYZEqualityComparer : IEqualityComparer<XYZ>
{
    private readonly double _epsSq;
    public XYZEqualityComparer(double epsDist) => _epsSq = epsDist;
    
    public bool Equals(XYZ x, XYZ y)
    {
        var v = x - y;
        return v.X*v.X + v.Y*v.Y + v.Z*v.Z < _epsSq;
    }
    
    public int GetHashCode(XYZ obj)
    {
        double eps = Math.Sqrt(_epsSq);
        long x = (long)Math.Round(obj.X / eps);
        long y = (long)Math.Round(obj.Y / eps);
        long z = (long)Math.Round(obj.Z / eps);
        return (x ^ y ^ z).GetHashCode();
    }
}

注意：确保XYZ为不可变类型，避免并行处理时的线程安全问题。

线程安全的实时添加（不推荐） #

若必须边遍历边添加节点，可使用ConcurrentDictionary做线程安全哈希映射，配合加锁的List存储节点，但锁竞争会大幅抵消并行收益，仅适合无法批量处理的场景。

三、其他小优化 #

• 精准预分配List容量：根据去重比例预估节点数量（比如900k节点去重后约300k），提前分配对应容量减少内存扩容开销
• 预计算精度阈值：将eps_dist提前计算为平方值，避免重复计算
• 使用值类型XYZ：若当前为引用类型，改为值类型可减少GC开销，提升访问速度

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