源码地址，redis geo的实现采用了前方源码，而此源码提供了两种计算z阶曲线值的算法(z阶曲线即将x,y的值通过二进制奇偶位分别处理组合为一个位置的整形结果),而redis选择的fast而不是二分下面将对二者进行分析。
算法一 二分计算
//最小纬度
#define GEO_LAT_MIN -85.05112878
//最大纬度
#define GEO_LAT_MAX 85.05112878
//最小经度
#define GEO_LONG_MIN -180
//最大经度
#define GEO_LONG_MAX 180
//step 默认为26,因为一次循环会计算出lat,lon两个值所以结果需要*2即52,8字节应该是64位而此处只用了52位,
//原因在于c中的double类型的小数精度就是52,为了保证小数的精度所以此处使用52
for (; i < step; i++) {
//lat_bit 纬度值
//lon_bit 经度值
uint8_t lat_bit, lon_bit;
//每次都进行除以二 然后判断当前经纬度在最小值-中间值，中间值-最大值
//此处判断这里没有使用中间值而是使用最大值-当前值>=当前值=最小值
//这样可以计算出-85.000 - 0 - 85.000假如 lat = 35
//结果为55.000 >= 120 ,条件不满足则走else修改最小值为（最大值+最小值）/2
//这样就将范围修改成了0 - 85.000,此处有一个规则就为如果只在最大值-中间值则设置当前循环为1
//否则设置结果为0,即进入if就是0进入else就是1
if (lat_range.max - latitude >= latitude - lat_range.min)
{
lat_bit = 0;
lat_range.max = (lat_range.max + lat_range.min) / 2;
}
else
{
lat_bit = 1;
lat_range.min = (lat_range.max + lat_range.min) / 2;
}
//纬度和经度计算结果一样
if (lon_range.max - longitude >= longitude - lon_range.min)
{
lon_bit = 0;
lon_range.max = (lon_range.max + lon_range.min) / 2;
}
else
{
lon_bit = 1;
lon_range.min = (lon_range.max + lon_range.min) / 2;
}
//上方说过如果进入if结果为0else结果为1此处便是将值<<1并且+得到的结果
//从而计算出一串二进制lon/lat都是一个根据当前地址计算出的二进制结果,然后在结果进行
//组合如lat=101 lon= 011 结果为100111
hash->bits <<= 1;
hash->bits += lon_bit;
hash->bits <<= 1;
hash->bits += lat_bit;
}
根据上放计算出结果可以推到算法二
算法二
//最小值都是负数 所以此处减的结果还是正数，然后除以整数得到当前纬度在纬度总值的占比
double lat_offset =
(latitude - lat_range->min) / (lat_range->max - lat_range->min);
//一样计算当前经度在经度总值的占比
double long_offset =
(longitude - long_range->min) / (long_range->max - long_range->min);
//获取到的占比 * 1<< 26位得到的double结果与二分得到的结果一致
//应该是有效位一致(26)最高位开始计算26得到的位数和二分计算的26位相等
lat_offset *= (1ULL << step);
long_offset *= (1ULL << step);
hash->bits = interleave64(lat_offset, long_offset);
这里可以看到算法二的复杂度为O(1)，而算法一的复杂度则是O(26)，虽然26也是常数但是如果访问量上来那么性能差距会越来越大。
总结推导
乍一看这两个算法没用半毛钱关系为什么结果是一致的,下面将会根据算法一的结果推导算法二的过程,此部分由B站用户建立操作系统的根据地的弟子‘点点点’提供
假设由二分得到结果,[a1,a2,a2,a4,...an] 其中每个a都是一个二进制位结果为1/0。
我们便可以使用二分的过程列出一个式子,image.png
其中A是上方结果按顺序对应如1/2A = a1,L为进制位的总长度26，下面进行变式
image.png
再次进行变式
image.png
最终得到结果image.png
这并不是我们要计算的,因为我们早已得知他的结果了所以我们需要将注意力放到这个式子
image.png
这个式子就很熟悉了不就是算法二的计算过程了，从而推导出两个算法的计算结果相等。
网友评论