最近用了下https://github.com/spatial4j/spatial4j spatial4j 做地理位置的搜索。
其中给定两个点的经纬度计算距离的公式有3种:
Haversine http://en.wikipedia.org/wiki/Haversine_formula
Law of Cosines(余弦定理) http://en.wikipedia.org/wiki/Spherical_law_of_cosines
Vincenty http://en.wikipedia.org/wiki/Vincenty's_formulae
spatial4j 默认使用的是Haversine
其中根据http://stackoverflow.com/questions/2096385/formulas-to-calculate-geo-proximity/ 的讨论
从速度上讲: Law of Cosines > Haversine > Vincenty
然后我就用了 Law of Cosines,结果发现比另两个都慢。。。
这不科学啊,然后我就开始看code: https://github.com/spatial4j/spatial4j/blob/master/src/main/java/com/spatial4j/core/distance/DistanceUtils.java
里面的3个函数distHaversineRAD, distLawOfCosinesRAD 和 distVincentyRAD
给定的地球表面的两点,这三个函数都是计算球心到这两点的向量的夹角,有了这个夹角的话乘以地球半径就是距离。
把里面的3个函数拿出来跑测试,用同一组100万中国经纬度范围longitude (73, 135) latitude (3, 53)
的随机数据在我的MacBookPro测试一下:
distHaversineRAD cost: 193.561ms
distLawOfCosinesRAD cost: 407.285ms
distVincentyRAD cost: 264.404ms
distLawOfCosinesRAD 果然最慢的啊,仔细看了下这个函数。
public static double distLawOfCosinesRAD(double lat1, double lon1, double lat2, double lon2) {
// Check for same position
if (lat1 == lat2 && lon1 == lon2)
return 0.0;
// Get the m_dLongitude difference. Don't need to worry about
// crossing 180 since cos(x) = cos(-x)
double dLon = lon2 - lon1;
double a = DEG_90_AS_RADS - lat1;
double c = DEG_90_AS_RADS - lat2;
double cosB = (Math.cos(a) * Math.cos(c))
+ (Math.sin(a) * Math.sin(c) * Math.cos(dLon));
// Find angle subtended (with some bounds checking) in radians
if (cosB < -1.0)
return Math.PI;
else if (cosB >= 1.0)
return 0;
else
return Math.acos(cosB);
}
优化1:
直觉告诉我acos这个计算反余弦的肯定最耗时。其实在搜索中使用距离函数最多的场景是做Filter用,比如给定中心点的经纬度搜索10公里范围内的人。
假设中心点经纬度是(lon1, lat1),距离d,地球半径为r,要判断的点是(lon2, lat2)
spatial4j中判断是否在范围内的做法:distLawOfCosinesRAD(lat1, lon1, lat2, lon2) < d/r
注意到Cosine在[0, PI]之间是递减的,任意两个向量的夹角也是在[0, PI]之间,所以如果判断距离是不是在范围内,可以不计算出来角度, 只计算出Cosine即可。
Math.cos(distLawOfCosinesRAD(lat1, lon1, lat2, lon2)) > Math.cos(d/r)
其中Math.cos(d/r)只需要计算一次,存储下来。
这样做距离Filter用的时候,distLawOfCosinesRAD 变成了这个样子
public static double distLawOfCosinesRAD(double lat1, double lon1, double lat2, double lon2) {
if (lat1 == lat2 && lon1 == lon2) return 0.0;
// Get the m_dLongitude difference. Don't need to worry about
// crossing 180 since cos(x) = cos(-x)
double dLon = lon2 - lon1;
double a = DEG_90_AS_RADS - lat1;
double c = DEG_90_AS_RADS - lat2;
double cosB = (Math.cos(a) * Math.cos(c)) + (Math.sin(a) * Math.sin(c) * Math.cos(dLon));
return cosB;
}
distLawOfCosinesRAD cost: 79.048ms
耗时变成了原来的1/5。
优化2:
又看了一下这个函数,作为处女座的人完全无法接收这两行啊:
double a = DEG_90_AS_RADS - lat1;
double c = DEG_90_AS_RADS - lat2;
其中 DEG_90_AS_RADS = Math.PI / 2;
显然Math.cos(a) = Math.sin(Math.PI / 2 - a) 所以干掉这两行后,distLawOfCosinesRAD 变成了这个样子
public static double distLawOfCosinesRAD(double lat1, double lon1, double lat2, double lon2) {
// Check for same position
if (lat1 == lat2 && lon1 == lon2) return 0.0;
// Get the m_dLongitude difference. Don't need to worry about
// crossing 180 since cos(x) = cos(-x)
double dLon = lon2 - lon1;
double cosB = (Math.sin(lat1) * Math.sin(lat2)) + (Math.cos(lat1) * Math.cos(lat2) * Math.cos(dLon));
return cosB;
}
distLawOfCosinesRAD cost: 36.258ms
又减少了一半。这个下降的幅度显然不合理,因为只是少做了两次double减法。感觉这个提高是和数据分布有关系,在中国的经纬度范围内效果很好,其实在美国的经纬度范围longitude (-75,-120) latitude (30, 50) 效果也很好。
优化3:
一次搜索中,中心点的经纬度(lon1, lat1)是不变的,但是每次计算距离我们都要计算Math.sin(lat1) 和 Math.cos(lat1), 如果把Math.sin(lat1) 和 Math.cos(lat1) 只计算一次每次计算距离时作为参数直接传入,那么会各减少一次Math.sin 和 Math.cos 计算。
distLawOfCosinesRAD cost: 24.356ms
减少了10多ms,这个优化效果不明显了。
如果还要继续优化:
假设每次搜索过程中需要和中心点(lon1, lat1)比较的点(lon2, lat2)的集合只取决于索引(比如每个用户的经纬度),那么我们在建索引时可以将经纬度(lon, lat)
转为空间坐标系(x, y, z)比如可以这样映射:
x = Math.cos(lat) * Math.cos(lon);
y = Math.cos(lat) * Math.sin(lon);
z = Math.sin(lat);
然后把(x, y, z)建入索引。
那么当我们求向量夹角时,只需要做一次点乘操作。比如求(lon1, lat1)和 (lon2, lat2)的夹角,只需要计算
x1*x2 + y1*y2 + z1*z2 这样避免了做任何三角函数换算这个效率是最高的,做100万次这样的操作基本在10ms以内。
Bobo的GeoFacetFilter就是这样做的。https://github.com/senseidb/bobo/blob/master/bobo-browse/src/main/java/com/browseengine/bobo/facets/filter/GeoFacetFilter.java
其实
x1*x2 + y1*y2 + z1*z2
= Math.cos(lat1) *Math.cos(lon1)*Math.cos(lat2) * Math.cos(lon2) +
Math.cos(lat1) *Math.sin(lon1) * Math.cos(lat2)*Math.sin(lon2) +
Math.sin(lat1)*Math.sin(lat2)
= Math.cos(lat1)*Math.cos(lat2)*(Math.cos(lon1) * Math.cos(lon2) + Math.sin(lon1)*Math.sin(lon2)) + Math.sin(lat1)*Math.sin(lat2)
= Math.cos(lat1)*Math.cos(lat2)*Math.cos(lon1-lon2) + Math.sin(lat1)*Math.sin(lat2)
这个结果和distLawOfCosinesRAD完全等价。
由于计算距离的耗时只是整个搜索耗时中的一部分,所以第一个优化在线上体现最明显,第二个不太明显,第三个基本属于过度优化了。
分享到:
相关推荐
赠送jar包:spatial4j-0.6.jar; 赠送原API文档:spatial4j-0.6-javadoc.jar; 赠送源代码:spatial4j-0.6-sources.jar; 赠送Maven依赖信息文件:spatial4j-0.6.pom; 包含翻译后的API文档:spatial4j-0.6-javadoc-...
赠送jar包:spatial4j-0.6.jar; 赠送原API文档:spatial4j-0.6-javadoc.jar; 赠送源代码:spatial4j-0.6-sources.jar; 赠送Maven依赖信息文件:spatial4j-0.6.pom; 包含翻译后的API文档:spatial4j-0.6-javadoc-...
spatial4j官方发布以及maven发布的版本都是基于jdk1.7编译的,碰到jdk1.6的项目会报unsupported major.minor version 51.0错误。这个资源是我基于jdk1.6编译的,执行测试案例都通过了。
spatial4j-0.4.1.jar
spatial4j, Java的地理空间库 Spatial4j ( 注:spatial4j主页的官方版本位于 LocationTech: 但是,这个自述文件包含了更丰富的信息。Spatial4j是一个通用的空间/地理空间 ASL 许可的开放源代码Java库。 它的核
如果您正在使用空间网格平方索引方案(无论是还是自定义的东西),那么您很可能会从Spatial4j中找到特别有用的工具。 Spatial4j经过了良好的测试; 通过持续集成(以及另一个Hudson构建)对其进行监视,我们使用...
part 2 共两部分 Handbook of Applied Spatial Analysis Software Tools, Methods and Applications
介绍了如何使用Oracle Spatial操作通过ArcSDE存储到Oracle数据库中的空间数据
这是关于空间逻辑的电子书,一千多页的巨著,经典著作,英文版
这是关于空间统计的电子书,高清,最新版本,经典著作,英文版
DBSCAN(Density-Based Spatial Clustering of Applications with Noise) 为一种基于密度的聚类算法,它不仅可以找出具有任何形状的簇,而且还可以用于检测离群值。其基本思想为数据点分布紧凑的应被划分为一类,而...
A Basic Spatial Econometrics learning book.
关于光学的分集技术的好文章,介绍了BER的表达式,和光传输的湍流的影响情况
注:下文中的 *** 代表文件名中的组件名称。 # 包含: 中文-英文对照文档:【***-javadoc-API文档-中文(简体)-英语-对照版.zip】 jar包下载地址:【***.jar下载地址(官方地址+国内镜像地址).txt】 Maven依赖:【*...
适合理解bag of features,考虑patch之间的空间关系
NULL 博文链接:https://nlslzf.iteye.com/blog/626844
Statistics in Practice is an important international series of texts which provide detailed coverage of statistical concepts, methods and worked case studies in specific fields of investigation and ...
Density-based spatial clustering of applications with noise (DBSCAN) is a data clustering algorithm,DBSCAN's definition of a cluster is based on the notion of density reachability.
treatment of the field of spatial data analysis. It begins with an overview of spatial data analysis and the importance of location (place, context and space) in scientific and policy-related research...