根据与用户的接近程度对大量人员进行有效排序

Question

因此，我正在尝试创建一个包含大小不一的 15 个最亲近的人的列表。该数组的大小几乎总是 ~100 个对象，但为了测试，我试图让它与 10,000 个对象一起使用（可能需要将项目进一步扩展到这些数字）。

目前采用的方法是循环遍历人物数组，根据人物和用户的经纬度（前者存储在数组中）计算他们与用户的距离).这是使用 haversine 公式完成的并且效果很好（虽然它确实需要 ~500 毫秒）。

然而，问题是当运行在移动设备（本例中为三星 Galaxy S5）上时，性能确实会受到影响。 S5 按照与预先确定的纬度和经度的接近程度对 10,000 条记录进行排序所花费的时间是惊人的 1,500-1,600 毫秒，对于将在其中任何一方做很多事情的应用程序来说，这是一个不可接受的延迟过程。

所以我的问题是，我是否缺少一些从根本上更有效的排序此列表的方法？是否有更有效的替代公式？我可以简单地计算 .000001s 中纬度和经度的组合差异并根据它进行排序吗？

备注:

用户的位置是可变的，因此无法存储接近度
我知道我要求移动设备 CPU 在短时间内 space 执行 100,000,000 次计算，因此这可能是不可避免的
排序方法是原生的JavaScript排序方法，下面是我测试这些时序的简化版本：

patientArray.sort(function(a, b)
{
    return GetDistanceToPoint(a["Lat"], a["Lng"]) - GetDistanceToPoint(b["Lat"], b["Lng"]);
});

// Function to get the User's distance to a point
  function GetDistanceToPoint(Latitude, Longitude)
  {
   // Check if the User's current Latitude and Longitude are available
   if(currentLat && currentLng)
   {
    // Convert degrees to a radius
    function degreeToRadius(degree)
    {
     return degree * (Math.PI/180)
    }

    // Variable to store radius of the Earth in Km
    var earthRadius = 6371;
    
    // Calculate the distance between the two points
    var dLat = degreeToRadius(Latitude-currentLat);
    var dLon = degreeToRadius(Longitude-currentLng); 
    var a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(degreeToRadius(currentLat)) * Math.cos(degreeToRadius(Latitude)) * Math.sin(dLon/2) * Math.sin(dLon/2); 
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    var d = earthRadius * c;
    return d;
   }
   return "-1";
  }

Answer 1

这一切都必须进行测试，但这里有一些我会尝试的想法。

对于大量使用三角函数，您可以使用查找表。这总是一个好主意。例如，预先计算 sin() 的 360 个（或更多）值，并为代码中的每个 sin（弧度）使用 sinTable[degrees].

（我以 360 值为例，因为你的索引是一个角度，但任何值都可以，这完全取决于你需要什么精度——如果需要，它可以有数千个值。）

避免不必要的计算。可能看起来很明显，但人们经常写类似 x/(2*Math.PI) 而不是 x*A 的东西，其中 A （当然更好的名字）被计算一次为 1/(2*Math.PI).

尽可能记住每个值，如果有意义的话。

如果您的数据具有某些特定性质，例如从不跨越地球的一半，那么您可以尝试作弊并在平面上使用坐标 - 然后您只需计算平方根（也可以预先计算以使用查找表）。

这些是我首先想到的事情。希望对你有帮助。

更新：

您进行了编辑，所以我现在知道的更多了。以下是我的提示：

不要将度数转换为弧度。保留度数并将它们用作三角函数预先计算值的查找表中的索引。如果您需要更高的精度，则将度数乘以 10 或其他值，并使用 0 到 3600 之间的比例，而不是 0 到 360 之间的比例。找到一个适合您的 size/precision 折衷方案。

您可以通过这种方式消除所有 sin() 和 cos() 调用，如果幸运的话，您可以消除 atan2()。我不会太担心 sqrt() 但如果你知道这些值通常是什么，你也可以消除它。如果 sqrt() 或 atan2() 等函数的值事先未知，那么您可以回退到实际函数以获得超出查找表范围的值。

避免过多的函数调用。而不是传递给 patientArray.sort() 的匿名函数，它调用 GetDistanceToPoint()，调用 degreeToRadius() - 您只需要一个可以作为参数直接传递给 .sort() 的函数和该函数不需要 return d - 它可以 return 只是 c （在你的例子中）。

如果您仅使用该值进行排序，则无需将所有内容都乘以 earthRadius。

另一个快速的想法：使用类型化数组（用于查找表），并在可能的情况下使用 asm.js 和 SIMD.js 进行额外优化。

首先想到的就是这些。我很想听听您的代码能获得多快的速度。祝你好运。

更新 2：

另一个想法 - 除了（或除了）优化 GetDistanceToPoint() 之外，您还可以确保它不会为每个对象调用多次。

而不是：

patientArray.sort(function(a, b)
{
    return GetDistanceToPoint(a["Lat"], a["Lng"]) - GetDistanceToPoint(b["Lat"], b["Lng"]);
});

您可以尝试执行以下操作：

patientArray.forEach(function (element) {
  element.distance = GetDistanceToPoint(element["Lat"], element["Lng"]);
});

或者 for 循环可能会更快：

for (var i = 0; i < patientArray.length; i++) {
  var element = patientArray[i];
  element.distance = GetDistanceToPoint(element["Lat"], element["Lng"]);
}

存储整个 patientArray 数组的值。

然后在排序函数中：

patientArray.sort(function(a, b)
{
    return a.distance - b.distance;
});

它有望为您节省大量对 GetDistanceToPoint 的调用。

根据与用户的接近程度对大量人员进行有效排序

Efficiently sorting large arrays of people by their proximity to the user

javascript

arrays

sorting

mobile

latitude-longitude