c# - 高效算法计算点之间的距离

Question

我有一个非常糟糕的效率问题。 我需要获得一组点之间的最远距离，而我的第一个“蛮力”算法需要将近 80 秒。我需要它在 1 秒内发生。 最坏的情况是将计算转移到后台进程并对它们进行多线程处理，但它仍然需要更快，所以这是我的第一个 stackoverflow 问题..

我拥有的数据是 39 000 组坐标，每组包含大约 200 个 x、y 坐标，我正在寻找每组中最远的距离。

数据点由 x 和 y 表示，我使用 Math.Sqrt(deltaX * deltaX + deltaY * deltaY)

计算它们之间的距离

数据点可以按任何顺序排列。

我的暴力尝试看起来像这样

public static double getAbsoluteMax(IEnumerable<DataPoint> dataPoints)
{
    double maxDistance = 0;

    foreach (DataPoint dp1 in dataPoints)
    {
        foreach (DataPoint dp2 in dataPoints)
        {
            double deltaX = dp1.x - dp2.x;
            double deltaY = dp1.y - dp2.y;
            double distance = Math.Sqrt(deltaX * deltaX + deltaY * deltaY);
            if (distance > maxDistance)
            {
                maxDistance = distance;
            }
        }
    }
    return maxDistance;
}

我每次用 200 个值调用这个函数.. 39 000 次。

我首先想到的是 Perl 中的 Memoize，它缓存任何方法调用的结果，然后在使用相同参数调用相同方法时查找它。也许创建一个包含数学结果的查找表会有所帮助？

也许我可以将计算转移到 matlab 或类似的东西上？

应用程序是 .net 4.5，计算在 .net 4.5 dll 中

Answer 1

找到 n log n 中的凸包。它可能会减少您的设置，然后找到 2 n 的船体直径。基本的图论应该会给你很多性能。

此外，39000 次的函数调用开销非常昂贵……而且数据集会杀死垃圾收集器。您应该尝试创建一些可重用的数组... 78000 个枚举器正在杀死。只需使用一个包含 200 个值的数组并重复使用它。并且不为每个使用 int ...删除 sqrt 并返回值的平方它可以节省几百万个 sqrts ...也许你可以使用 int 的唯一没有 double ...使用多个线程/核心 ...和 ​​sse 指令或卸载到 GPU

编译发布构建和代码优化

例如，这会在大约 2.5 秒内运行:

Random r = new Random(100);
double[] x = new double[200];
double[] y = new double[200];
double maxD = 0;
Stopwatch stopwatch = Stopwatch.StartNew();
for (int i = 0; i < 39000; i++)
{
    for (int j = 0; j < 200; j++)
    {
        x[j] = r.Next();
        y[j] = r.Next();
    }
    for (int j = 0; j < 200; j++)
    {
        for (int k = j + 1; k < 200; k++)
        {
            double dx = x[j] - x[k];
            dx = dx * dx;
            double dy = y[j] - y[k];
            dy = dy * dy;
            double d = dx + dy;
            // this is slow (80 secs):
            //double d = Math.Pow(x[j] - x[k], 2) + Math.Pow(y[j] - y[k], 2);
            if (maxD < d) maxD = d;
        }
    }
}
Console.WriteLine($"{stopwatch.ElapsedMilliseconds}");

Math.Pow 调用(来自 http://referencesource.microsoft.com/#mscorlib/system/math.cs ):

  [System.Security.SecuritySafeCritical]  // auto-generated
  [ResourceExposure(ResourceScope.None)]
  [MethodImplAttribute(MethodImplOptions.InternalCall)]
  public static extern double Pow(double x, double y);