c# - 更高效的半正弦函数

Question

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

这是一个基本的Haversine函数，使用以下代码:

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

这是我能得到的答案的最优化(而且，据我所知，这是在没有对公式本身进行一些向导级优化的情况下可能得到的最优化的答案):

private static double Haversine(double lat1, double lat2, double lon1, double lon2)
{
    const double r = 6371; // 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 个数字的来源，您可以确定优先级，这样您就不需要调用几乎那么多的方法。