1

我有大约 12 000 个条目的数据库。每个条目都给出了纬度、经度和空距。我需要做的是从当前 GPS 位置找到 25 个最近的条目。我的 ORM 是 greenDao。

有 2 个问题：我还不知道我和条目之间的距离，并且我无法将所有条目加载到 RAM，因为当我这样做时，堆会上升到 70MB，并且应用程序在 OutOfMemoryException 处崩溃（所以我需要使用延迟加载）。

我尝试了这种方法：

  1. 获取给定表的迭代器
  2. 加载条目，计算它与我当前位置的距离，将条目保存到 ArrayList 缓冲区（我每 1000 个条目将缓冲区刷新回数据库（它只是 updateInTx(...)）然后清理它）
  3. 重复第 2 点，直到 iterator.hasNext();
  4. 从具有limit(25).orderAsc() 的条目中查询
  5. 结果

这行得通，但从第 1-3 点开始非常慢（在 Nexus 7 上大约需要 25 秒）。休息大约需要 1.5 秒。

每次用户启动应用程序或请求数据刷新时，我都必须这样做。任何想法如何更好地解决它？

谢谢

编辑：这是计算距离的函数，所以很难在 SQL 中做到这一点:(

double getDistance(GPSCoords myPos, Place place) {
    double dlong = (place.getLongitude() - myPos.getLongitude()) * d2r;
    double dlat = (place.getLatitude() - myPos.getLatitude()) * d2r;
    double a = Math.pow(Math.sin(dlat / 2.0), 2) + Math.cos(myPos.getLatitude() * d2r)
            * Math.cos(place.getLatitude() * d2r) * Math.pow(Math.sin(dlong / 2.0), 2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    double d = 6367 * c;

    return d;
}
4

4 回答 4

2

您应该能够让 SQL 在数据库中完成工作：

select ((x - ?)*(x - ?) + (y - ?)*(y - ?)) as distsq from entries 
order by dist limit 20

不幸的是 sqlite 不提供求幂，因此需要重复项。

如果这仍然不够快，另一种方法是以您的位置为中心进行边界框查询，通过二分搜索调整边界框的大小，直到您有 30 个或更多条目。每个 x 和 y 维度上的索引都会加快这些速度。

编辑由于 OP 说地球曲率很重要，边界框技术可能是我们可以使用 unextended 获得的最佳方法sqlite。这是一个建议的算法：

Let P be the current position
Let Slat = lat0 be the bounding box latitude half-size initialized with a "best guess"
Let Slon = lon0 be the bounding box longitude half-size initialized with a "best guess"
// NB the best guesses should cover an approximately square area on the ground
loop
  Let W = P.lon - Slon, E = P.lon + Slon, N = P.lat + Slat, S = P.lat - Slat
  C = select count(*) from entries
      where W <= lon and lon <= E and S <= lat and lat <= N
  if C indicates the result is too big (e.g. for memory or read time), 
    Slat = 0.5 * Slat
    Slon = 0.5 * Slon
  else
    Let R be the result of the same query for * instead of count(*)
    Let D be the geometric distance from P to the nearest point on bounding box
    Compute r.dist for all r in R (in memory)
    Sort R by dist (in memory)
    Throw away the tail elements of R where r.dist > D 
       // Can't use these because points outside bounding box might be closer!
    If at least 20 remaining R elements, 
      return top 20
    else
      Slat = 2 * Slat
      Slon = 2 * Slon
    end if
  end if
end loop

请注意，您需要纬度和经度的索引。在这种情况下，我不知道 SQLite 查询优化器有多好。一个好的优化器会根据过去查询累积的统计信息选择 lat 或 lon 索引，使用它来快速找到该维度边界框范围内的所有点，然后对该结果进行扫描以获得最终结果。如果优化器不那么聪明，您只想索引可能产生最小初始结果的维度：在平均情况下，这是具有最大几何范围（覆盖距离）的维度。

r* 树索引将使边界框查询更快，但至少通过 Jelly Bean，您必须提供包含此扩展的自己的 SQLite 实例。也许后来的 Android 版本包含它？我不知道。

此外，如果您要在应用程序中包含自定义 SQLite，添加距离（带曲率）函数作为扩展将非常容易。

于 2013-09-19T17:53:11.410 回答
0

我不明白为什么你觉得你需要延迟加载你的条目。70MB 的堆数听起来很可疑，只有 12k 个条目。您是否只是为了计算距离而抓住整行？试着抓住你需要的列：

  • 纬度
  • 经度
  • 首要的关键

假设每个是 8 个字节，那就是24 * 12000字节，或大约 280千字节。给它一些仅仅是 Java 的开销空间，但你仍然在看一些非常易于管理的东西。

然后您可以在代码中进行计算，并让它为每个最近点吐出主键。第二个查询可以只获取这 25 个（这次是整行），你就完成了！

于 2013-09-19T18:27:52.967 回答
0

有很多使用不同风格的 SQL 计算距离的例子。从您的数据库加载每一行并计算它的距离，然后排序并取最近的行，只是从来回到数据库会很慢。在 SQL 中进行计算并仅检索您需要的那些将具有更高的性能。

于 2013-09-19T17:48:45.940 回答
0

您可以尝试将距离计算移动到 sql db。您还可以放置一些更智能的代码，它将运行距离计算，直到他找到 25 个与当前位置的距离小于 x（您选择）的地方。甚至少于 25 个项目（也许你只需要 7 个来填满屏幕），而不是当用户已经在应用程序中时在后台继续计算。这将是一个更好的用户体验。

于 2013-09-19T17:49:51.107 回答