一种更高效的Haversine函数

Question

一种更高效的Haversine函数

4

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

这是一个基本的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的行似乎占用了最多的时间。

由于频繁地调用它，我希望使它变得更快一些。我接受多线程解决方案（并且目前正在自己开发一个），但考虑到我之前的问题的使用情况（链接如上），实现起来可能会更加困难。

- charliefox2

2

最佳优化是少调用它…… 快速查看其他问题会发现你需要“最接近5”或类似的东西。这使得它成为一个有点XY问题。 - H H

为什么将弧度转换为角度或将角度转换为弧度会产生如此大的惩罚？这实际上只是一个简单的乘法运算。虽然它是一个浮点运算，但它应该远不及那些三角函数那么昂贵。 - Abion47

1

另外，我正在查看维基百科上对Haversine公式的定义，但是没有任何地方提到需要进行Atan运算。你实际上想让这个方法返回什么值？ - Abion47

@HenkHolterman 我认为这总是一个很好的思考方式，也是我经常考虑的。如果您能立即看到需要改进的地方，我会很乐意接受。同时，这是一项昂贵的操作，我希望能够精简它。 - charliefox2

@Abion47 这只是我使用的实现方式。我认为你可以选择使用或不使用，无论哪种方式距离都是相同的。我正在计算两个纬度-经度对之间的距离。将其转换为弧度大约需要1-1.5秒钟的时间。如果我想要，实际上我可以将所有值都存储为弧度，所以这不是问题。顺便说一下，我使用的Haversine公式是从这里提取的http://www.movable-type.co.uk/scripts/latlong.html。 - charliefox2

在维基百科上列出了 d = 2 * r * Math.Asin(Math.Sqrt(h));，因此可以消除调用 Math.Sqrt 这个问题，这将有助于提高性能。然而，我认为你的整体设计可能存在更大的问题。在另一个问题的评论中，你提到需要为500个邮政编码调用33,000次 Haversine（这就是16,500,000来自哪里）。首先，为什么要这样做？其次，这种设置（假设邮政编码彼此引用）正好适合使用查找表。 - Abion47

2个回答

4

对我来说，这更准确。

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

- Dave

我回来有点晚，但这种方法犯了一个关键性的错误，即计算 Math.Sin(dLat / 2) 和 Math.Sin(dLon / 2) 两次，而不是只计算一次并缓存结果。算术操作很便宜，但三角函数非常昂贵，所以在不必要时进行三角函数运算会使算法的效率不高。 - Abion47

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abion47 · Accepted Answer

这是我能够优化的最佳答案（据我所知，这是在不对公式本身进行巫师级别的优化的情况下，答案可能得到的最优化的结果）：

// 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个纬度经度对，每个对都要调用33000次？这是一个很需要优化的系统。首先，您可以先计算出对的线性距离平方，并仅处理低于某个阈值的对。或者您可以维护一个查找表，以避免重复计算相同的对。或者根据那个33000数字的来源，您可以优先考虑不需要调用该方法如此之多的情况。