使用大数组进行反向地理编码是最快的方法吗？ - javascript 和性能

Question

我在 Google Maps 上有很多点，我想为每个点显示最近的城市（因此进行反向地理编码）。我有一个这样的多维数组：

citta_vicine = [];

var comuni = [
 ["Abano Terme (PD)",45.3594,11.7894],
 ["Abbadia Cerreto (LO)",45.3122,9.5928],
 ["Abbadia Lariana (LC)",45.8992,9.3336],
 ["Abbadia San Salvatore (SI)",42.8800,11.6775],
 ["Abbasanta (OR)",40.1250,8.8200]
]

//city, latitude, longitude

问题是我的数组包含意大利的所有城市（8000！）并且是 300 Kb。

要获得最近的城市，我可以使用这个：

//this line will be inside for loop of points
 var city_near= estrapola_paese(50,lat,lng); //lat and lng are coordinates of these points
//


 function estrapola_paese(distanza,latB,longB){ 
  citta_vicine = [];
  for(var i= 0; i < comuni.length; i++){
    var dist_eqcity= dist_coords(comuni[i][1],comuni[i][2],latB,longB);
    if(dist_eqcity < distanza){
        citta_vicine.push([dist_eqcity, comuni[i][0]]);
    }
  }
  if(citta_vicine.length > 0){
    citta_vicine.sort(function(a, b) {
        return a - b;
    }); 
    return citta_vicine[0][1];
  }
  else{
    distanza = distanza+50;
    estrapola_paese(distanza,latB,longB);   
  }
 }

//calculate distance in Km between city and "point"
function dist_coords(latA,longA,latB,longB) {
 var R = 6372.795477598;
 var laA = latA * Math.PI/180;
 var laB = latB * Math.PI/180;
 var loA = longA * Math.PI/180;
 var loB = longB * Math.PI/180;
 var distanza = R * Math.acos(Math.sin(laA)*Math.sin(laB) + Math.cos(laA)*Math.cos(laB) * Math.cos(loA-loB));
 if(isNaN(distanza) == true){   
  distanza = 0;
 }
 return distanza;
}

简而言之，对于性能问题，我（首先）只考虑距该点50公里半径范围内的城市。如果 50 公里以内有城市，我将城市（和距离）添加到 "citta_vicine" 数组中，并将后一个数组从最低值到最高值排序。因此距离最近的城市最远。

如果 50 公里内没有城市，那么我会再次执行函数 "estrapola_paese"，但会增加半径以考虑另外 50 公里。

我认为 CODE WORKS 但我有很多疑问：

1) 文件大小为 459 KB：是不是太大了？

2) 有没有更好的方法来完成这一切？

3) 数组 citta_vicine 的排序是否正确？如果不为空是这样的：

   [
    ["tokyo",34],
    ["rome",24],
    ["paris",54]
   ]

使用这个：

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

我将得到这个输出：

   [        
    ["rome",24],
    ["tokyo",34],
    ["paris",54]
   ]

我希望你能帮助我，对不起我的英语。

Answer 1

您可能希望在第二个数组元素之后排序：

 citta_vicine.sort(function(a, b) {
   return a[1] - b[1];
 });

Answer 2

由于城市数据不是动态变化的，并且您需要经常计算距离/最近邻，因此使用地理空间索引（KD-Tree、R-Tree 等）会很有意义。

这是一个使用 geokdbush 的示例实现，它基于使用 KD-Tree 实现的静态空间索引。它考虑了地球曲率和日期变更线。

const kdbush = require('kdbush');
const geokdbush = require('geokdbush');

// I've stored the data points as objects to make the values unambiguous
const cities = [
  { name: "Abano Terme (PD)", latitude: 45.3594, longitude: 11.7894 },
  { name: "Abbadia Cerreto (LO)", latitude: 45.3122, longitude: 9.5928 },
  { name: "Abbadia Lariana (LC)", latitude: 45.8992, longitude: 9.3336 },
  { name: "Abbadia San Salvatore (SI)", latitude: 42.8800, longitude: 11.6775 },
  { name: "Abbasanta (OR)", latitude: 40.1250, longitude: 8.8200 }
];

// Create the index over city data ONCE
const index = kdbush(cities, ({ longitude }) => longitude, ({ latitude }) => latitude);

// Get the nearest neighbour in a radius of 50km for a point with latitude 43.7051 and longitude 11.4363
const nearest = geokdbush.around(index, 11.4363, 43.7051, 1, 50);

再次记住，kdbush 是一个静态索引，无法更改（您无法从中添加或删除城市）。如果您需要在初始化后更改城市数据，这取决于您更改的频率，使用索引可能成本太高。

Answer 3

To get nearest city...

如果您只对最近的城市感兴趣，则无需对整个列表进行排序。这是您在一行代码中获得的第一个性能提升！

// Unneeded sort:
const closest = cityDistancePairs.sort((a, b) => a[1] - b[2])[0];

// Only iterates once instead:
const closestAlt = cityDistancePairs.reduce(
  (closest, current) => current[1] < closest[1] ? current : closest
);

要进一步优化，您需要对代码的哪些部分进行基准测试需要最长运行。一些想法：

在计算精确值之前快速检查 lat/lon 差异。如果坐标之间的距离超过一定的增量，您就已经知道它们超出了范围。
通过实现记忆模式来缓存计算的距离，以确保在具有不同限制 (50 -> 100) 的第二次传递时，您不会重新计算距离

但是，我无法想象 8000 次距离计算的循环是真正的性能消耗...我猜测 解析 javascript[=27 的 300kb =] 才是真正的瓶颈。你如何初始化城市数组？

确保将数据集精简为仅包含您实际使用的属性和值。如果您知道您只会使用名称和 lat/lon，则可以预处理数据以仅包含这些。这可能会使它比 300kb 小得多并且更易于使用。

Answer 4

颠覆你的计算

步骤 #1 计算所有位置的距离。

步骤 #2 按距离值对结果进行排序

步骤 #3 查找位置，重复此步骤至少找到一条记录。

勾选DEMO，计算一个有7320条记录的列表用了~17.22119140625ms

const citites = [
  [`Abano Terme (PD)`, 45.3594, 11.7894],
  [`Abbadia Cerreto (LO)`, 45.3122, 9.5928],
  [`Abbadia Lariana (LC)`, 45.8992, 9.3336],
  [`Abbadia San Salvatore (SI)`, 42.8800, 11.6775],
  [`Abbasanta (OR)`, 40.1250, 8.8200]
]

function distance(lat, long) {
  const R = 6372.795477598
  const PI = Math.PI / 180
  return cities
    .map(city => {
      const laA = city[1] * PI
      const laB = lat * PI
      const loA = city[2] * PI
      const loB = long * PI
      const dist = R * Math.acos(
        Math.sin(laA) * Math.sin(laB) +
        Math.cos(laA) * Math.cos(laB) * Math.cos(loA - loB)
      ) || 0
      return { dist, city }
    })
    .sort((a, b) => a.dist - b.dist)
}


function nearest(dist, lat, long) {
  const locations = distance(lat, long)
  function find(delta) {
    const result = []
    for (let location of locations) {
      if (location.dist > delta) break
      result.push(location.city)
    }
    return result.length > 0
      ? result
      : find(delta + 50)
  }
  return find(dist)
}

const result = nearest(50, 41.89595563, 12.48325842)

使用大数组进行反向地理编码是最快的方法吗？ - javascript 和性能

Reverse geocoding with big array is fastest way? - javascript and performance

javascript

arrays

optimization

performance

reverse-geocoding