如何优化含向量长度计算的双层循环？曲线点筛选性能优化

核心优化点： #

• 提前计算直线范围索引：把直线起止索引的计算移到外层循环外，避免重复遍历XLine数组
• 替换距离计算逻辑：用平方比较替代开根号，减少浮点运算开销
• 内层循环提前终止：一旦找到符合条件的直线点，立即跳出内层循环，无需继续检查
• 修复索引获取bug：原代码错误地获取了XLine的元素值作为索引，改为获取真正的索引位置
• 预分配列表容量：避免返回列表动态扩容的性能损耗
• 修正循环边界：原循环漏掉了曲线的最后一个点

优化后代码： #

(List<int>, List<int>) LineCheck(List<int> Xcurve, List<int> Ycurve, List<int> XLine, List<int> YLine, double deviation)
{
    // 预分配返回列表容量，避免动态扩容
    List<int> returnCurveX = new List<int>(Xcurve.Count);
    List<int> returnCurveY = new List<int>(Ycurve.Count);
    
    // 计算距离阈值的平方，避免开根号运算
    double deviationSquared = deviation * deviation;

    // 仅计算一次直线的起止索引（假设XLine是有序的，符合直线坐标的特性）
    int curveMinX = Xcurve[0];
    int curveMaxX = Xcurve[Xcurve.Count - 1];
    int XStartIndex = XLine.FindIndex(x => x >= curveMinX);
    // 处理找不到的情况，默认从0开始
    XStartIndex = XStartIndex == -1 ? 0 : XStartIndex;
    
    int XEndIndex = XLine.FindLastIndex(x => x <= curveMaxX);
    // 处理找不到的情况，默认到最后一个元素
    XEndIndex = XEndIndex == -1 ? XLine.Count - 1 : XEndIndex;

    for (int i = 0; i < Xcurve.Count; i++)
    {
        bool keepPoint = true;
        int curveX = Xcurve[i];
        int curveY = Ycurve[i];

        for (int j = XStartIndex; j <= XEndIndex; j++)
        {
            // 计算向量差的平方和，无需开根号
            double dx = curveX - XLine[j];
            double dy = curveY - YLine[j];
            double distanceSquared = dx * dx + dy * dy;

            if (distanceSquared < deviationSquared)
            {
                keepPoint = false;
                // 找到符合条件的点，直接跳出内层循环
                break;
            }
        }

        if (keepPoint)
        {
            returnCurveX.Add(curveX);
            returnCurveY.Add(curveY);
        }
    }

    // 裁剪列表容量到实际元素数，节省内存
    returnCurveX.TrimExcess();
    returnCurveY.TrimExcess();

    return (returnCurveX, returnCurveY);
}

额外性能提升建议： #

• 如果XLine是严格有序的，可以用二分查找（Array.BinarySearch）替代FindIndex和FindLastIndex，进一步加快索引定位速度
• 可以考虑将List转为数组（ToArray()），数组的遍历性能略高于List
• 若直线的点是连续的线段，可以直接计算点到直线的代数距离，而不是遍历所有直线点，这会彻底将O(n*m)的复杂度降到O(n)，是最优解（前提是直线可以用解析式表示，比如Ax+By+C=0，点到直线的距离公式为|Ax+By+C|/√(A²+B²)，同样可以用平方比较避免开根号）

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