Faster GeoHashUtils [LUCENE-2965]

I found the current implement of org.apache.lucene.spatial.geohash.GeoHashUtils.encode and decode is slow and this is my improvement (400% faster )

/\*\*
- Encodes the given latitude and longitude into a geohash
\*
- `@param` latitude Latitude to encode
- `@param` longitude Longitude to encode
- `@return` Geohash encoding of the longitude and latitude
\*/
public static String encode(double latitude, double longitude) {
double latL = -90, latH = 90;
double lngL = -180, lngH = 180;
double mid;
// assert PRECISION % 2 == 0;
final char[] geohash = new char[PRECISION];
int len = 0;
int ch = 0;
while (len <PRECISION) {
if (longitude > (mid = (lngL + lngH) \* 0.5)) {
ch |= 16;
lngL = mid;
} else
lngH = mid;

if (longitude > (mid = (lngL + lngH) \* 0.5)) {
ch |= 4;
lngL = mid;
} else
lngH = mid;

if (longitude > (mid = (lngL + lngH) \* 0.5)) {
ch |= 1;
lngL = mid;
} else {
lngH = mid;
}

if (latitude > (mid = (latL + latH) \* 0.5)) {
ch |= 8;
latL = mid;
} else {
latH = mid;
}
if (latitude > (mid = (latL + latH) \* 0.5)) {
ch |= 2;
latL = mid;
} else {
latH = mid;
}

geohash[len++] = BASE_32[ch];
ch = 0;

if (latitude > (mid = (latL + latH) \* 0.5)) {
ch |= 16;
latL = mid;
} else
latH = mid;

if (longitude > (mid = (lngL + lngH) \* 0.5)) {
ch |= 8;
lngL = mid;
} else
lngH = mid;

if (latitude > (mid = (latL + latH) \* 0.5)) {
ch |= 4;
latL = mid;
} else
latH = mid;

if (longitude > (mid = (lngL + lngH) \* 0.5)) {
ch |= 2;
lngL = mid;
} else
lngH = mid;

if (latitude > (mid = (latL + latH) \* 0.5)) {
ch |= 1;
latL = mid;
} else
latH = mid;

geohash[len++] = BASE_32[ch];
ch = 0;
}

return new String(geohash);
}

/\*\*
- Decodes the given geohash into a latitude and longitude
\*
- `@param` geohash Geohash to deocde
- `@return` Array with the latitude at index 0, and longitude at index 1
\*/
public static double[] decode(String geohash) {
double latL = -90.0, latH = 90.0;
double lngL = -180.0, lngH = 180.0;
double gap;
int len = geohash.length();
for (int i = 0; i < len; ) {
switch (geohash.charAt(i++)) {
case '0':
latH -= (latH - latL) \* 0.75;
lngH -= (lngH - lngL) \* 0.875;
break;
case '1':
latH -= (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.125;
lngH -= gap \* 0.75;
break;
case '2':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
lngH -= (lngH - lngL) \* 0.875;
break;
case '3':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.125;
lngH -= gap \* 0.75;
break;
case '4':
latH -= (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.625;
break;
case '5':
latH -= (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.375;
lngH -= gap \* 0.5;
break;
case '6':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.625;
break;
case '7':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.375;
lngH -= gap \* 0.5;
break;
case '8':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
lngH -= (lngH - lngL) \* 0.875;
break;
case '9':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.125;
lngH -= gap \* 0.75;
break;
case 'b':
latL += (latH - latL) \* 0.75;
lngH -= (lngH - lngL) \* 0.875;
break;
case 'c':
latL += (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.125;
lngH -= gap \* 0.75;
break;
case 'd':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.625;
break;
case 'e':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.375;
lngH -= gap \* 0.5;
break;
case 'f':
latL += (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.625;
break;
case 'g':
latL += (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.375;
lngH -= gap \* 0.5;
break;
case 'h':
latH -= (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.375;
break;
case 'j':
latH -= (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.625;
lngH -= gap \* 0.25;
break;
case 'k':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.375;
break;
case 'm':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.625;
lngH -= gap \* 0.25;
break;
case 'n':
latH -= (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.75;
lngH -= gap \* 0.125;
break;
case 'p':
latH -= (latH - latL) \* 0.75;
lngL += (lngH - lngL) \* 0.875;
break;
case 'q':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.75;
lngH -= gap \* 0.125;
break;
case 'r':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.5;
lngL += (lngH - lngL) \* 0.875;
break;
case 's':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.375;
break;
case 't':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.625;
lngH -= gap \* 0.25;
break;
case 'u':
latL += (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.375;
break;
case 'v':
latL += (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.625;
lngH -= gap \* 0.25;
break;
case 'w':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.75;
lngH -= gap \* 0.125;
break;
case 'x':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.25;
lngL += (lngH - lngL) \* 0.875;
break;
case 'y':
latL += (latH - latL) \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.75;
lngH -= gap \* 0.125;
break;
case 'z':
latL += (latH - latL) \* 0.75;
lngL += (lngH - lngL) \* 0.875;
break;
}
switch (geohash.charAt(i++)) {
case '0':
latH -= (latH - latL) \* 0.875;
lngH -= (lngH - lngL) \* 0.75;
break;
case '1':
gap = latH - latL;
latL += gap \* 0.125;
latH -= gap \* 0.75;
lngH -= (lngH - lngL) \* 0.75;
break;
case '2':
latH -= (latH - latL) \* 0.875;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case '3':
gap = latH - latL;
latL += gap \* 0.125;
latH -= gap \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case '4':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.625;
lngH -= (lngH - lngL) \* 0.75;
break;
case '5':
gap = latH - latL;
latL += gap \* 0.375;
latH -= gap \* 0.5;
lngH -= (lngH - lngL) \* 0.75;
break;
case '6':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.625;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case '7':
gap = latH - latL;
latL += gap \* 0.375;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case '8':
latH -= (latH - latL) \* 0.875;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case '9':
gap = latH - latL;
latL += gap \* 0.125;
latH -= gap \* 0.75;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case 'b':
latH -= (latH - latL) \* 0.875;
lngL += (lngH - lngL) \* 0.75;
break;
case 'c':
gap = latH - latL;
latL += gap \* 0.125;
latH -= gap \* 0.75;
lngL += (lngH - lngL) \* 0.75;
break;
case 'd':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.625;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case 'e':
gap = latH - latL;
latL += gap \* 0.375;
latH -= gap \* 0.5;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case 'f':
gap = latH - latL;
latL += gap \* 0.25;
latH -= gap \* 0.625;
lngL += (lngH - lngL) \* 0.75;
break;
case 'g':
gap = latH - latL;
latL += gap \* 0.375;
latH -= gap \* 0.5;
lngL += (lngH - lngL) \* 0.75;
break;
case 'h':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.375;
lngH -= (lngH - lngL) \* 0.75;
break;
case 'j':
gap = latH - latL;
latL += gap \* 0.625;
latH -= gap \* 0.25;
lngH -= (lngH - lngL) \* 0.75;
break;
case 'k':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.375;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case 'm':
gap = latH - latL;
latL += gap \* 0.625;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case 'n':
gap = latH - latL;
latL += gap \* 0.75;
latH -= gap \* 0.125;
lngH -= (lngH - lngL) \* 0.75;
break;
case 'p':
latL += (latH - latL) \* 0.875;
lngH -= (lngH - lngL) \* 0.75;
break;
case 'q':
gap = latH - latL;
latL += gap \* 0.75;
latH -= gap \* 0.125;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case 'r':
latL += (latH - latL) \* 0.875;
gap = lngH - lngL;
lngL += gap \* 0.25;
lngH -= gap \* 0.5;
break;
case 's':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.375;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case 't':
gap = latH - latL;
latL += gap \* 0.625;
latH -= gap \* 0.25;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case 'u':
gap = latH - latL;
latL += gap \* 0.5;
latH -= gap \* 0.375;
lngL += (lngH - lngL) \* 0.75;
break;
case 'v':
gap = latH - latL;
latL += gap \* 0.625;
latH -= gap \* 0.25;
lngL += (lngH - lngL) \* 0.75;
break;
case 'w':
gap = latH - latL;
latL += gap \* 0.75;
latH -= gap \* 0.125;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case 'x':
latL += (latH - latL) \* 0.875;
gap = lngH - lngL;
lngL += gap \* 0.5;
lngH -= gap \* 0.25;
break;
case 'y':
gap = latH - latL;
latL += gap \* 0.75;
latH -= gap \* 0.125;
lngL += (lngH - lngL) \* 0.75;
break;
case 'z':
latL += (latH - latL) \* 0.875;
lngL += (lngH - lngL) \* 0.75;
break;
}
}
return new double[] { (latL + latH) / 2D, (lngL + lngH) / 2D };
}

---
Migrated from [LUCENE-2965](https://issues.apache.org/jira/browse/LUCENE-2965) by 朱文彬

Start by locating org.apache.lucene.spatial.geohash.GeoHashUtils and its encode and decode methods, then compare the current implementation with the proposed code in the issue. Verify that the optimized methods preserve existing geohash behavior and establish whether the reported speed improvement is reproducible before considering the work done.

Written by the indexing model from the issue text.