使用大数组进行反向地理编码是最快的方法吗？ - 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 公里的半径。

---

我认为代码有效，但我有很多疑问：

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

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

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

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 2

步骤#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)

Answer 3

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

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

Answer 4

要获取最近的城市...

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

// 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
);

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

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

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

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