更有效的半正矢函数

Question

在我之前的问题中，我希望根据函数结果加速列表选择。现在，我的瓶颈是函数本身。

这是一个基本的半正弦函数，使用以下代码：

private static double Haversine(double lat1, double lat2, double lon1, double lon2)
{            
    const double r = 6371e3; // meters
    var dlat = (lat2 - lat1)/2;
    var dlon = (lon2 - lon1)/2;

    var q = Math.Pow(Math.Sin(dlat), 2) + Math.Cos(lat1) * Math.Cos(lat2) * Math.Pow(Math.Sin(dlon), 2);
    var c = 2 * Math.Atan2(Math.Sqrt(q), Math.Sqrt(1 - q));

    var d = r * c;
    return d / 1000;
}

那么……为什么需要这么快？问题是我经常调用它。向北思考 16,500,000 次。

显然，这已经很多了。在我的用例中，我传递给它必须从中获取位置数据的对象，然后将纬度和经度转换为弧度，这进一步增加了时间（仅增加了约 15%）。我不知道对此我能做些什么，但我确实知道，通过纯粹以弧度加倍的方式传递它（如上所述），大约需要 4.5 秒——这超过了我的实现中处理时间的 75%。为 q 和 c 赋值的行似乎占用了最多的时间。

由于它被多次调用，我希望让它更快一点。我对多线程解决方案持开放态度（并且目前我自己正在研究一个解决方案），但考虑到我上一个问题（上面链接）中的用例，实现起来可能会有点困难。

Answer 1

这是我能得到的最佳答案（据我所知，这是在不对公式本身进行一些向导级优化的情况下可能获得的最优化答案）：

// inputs assumed to be in radians
private static double Haversine(double lat1, double lat2, double lon1, double lon2)
{
    const double r = 6378100; // meters
            
    var sdlat = Math.Sin((lat2 - lat1) / 2);
    var sdlon = Math.Sin((lon2 - lon1) / 2);
    var q = sdlat * sdlat + Math.Cos(lat1) * Math.Cos(lat2) * sdlon * sdlon;
    var d = 2 * r * Math.Asin(Math.Sqrt(q));

    return d;
}

在我的机器上，这个公式运行 1650 万次时，运行时间几乎正好是 3 秒，而上面的版本运行时间仅不到 5 秒。

然而，我认为最大的优化可能是在实际调用此方法的系统中。500 个纬度-经度对中每对 33,000 次？这个系统可能本身就急需优化。对于初学者，您可以首先计算对的线性距离平方，并且仅处理低于特定阈值的对。或者您可以维护一个查找表以避免多次计算同一对。或者，根据 33,000 数字的来源，您可以确定优先级，这样您就不需要调用该方法那么多了。

Answer 2

对我来说这更准确

public static class Haversine {
  public static double calculate(double lat1, double lon1, double lat2, double lon2) {
    var R = 6372.8; // In kilometers
    var dLat = toRadians(lat2 - lat1);
    var dLon = toRadians(lon2 - lon1);
    lat1 = toRadians(lat1);
    lat2 = toRadians(lat2);

    var a = Math.Sin(dLat / 2) * Math.Sin(dLat / 2) + Math.Sin(dLon / 2) * Math.Sin(dLon / 2) * Math.Cos(lat1) * Math.Cos(lat2);
    var c = 2 * Math.Asin(Math.Sqrt(a));
    return R * c;
  }

  public static double toRadians(double angle) {
    return Math.PI * angle / 180.0;
  }
}

void Main() {
  Console.WriteLine(String.Format("The distance between coordinates {0},{1} and {2},{3} is: {4}", 36.12, -86.67, 33.94, -118.40, Haversine.calculate(36.12, -86.67, 33.94, -118.40)));
}

// Returns: The distance between coordinates 36.12,-86.67 and 33.94,-118.4 is: 2887.25995060711