lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "David Smiley (JIRA)" <j...@apache.org>
Subject [jira] Commented: (LUCENE-2965) Faster GeoHashUtils
Date Fri, 11 Mar 2011 14:45:59 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-2965?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13005655#comment-13005655
] 

David Smiley commented on LUCENE-2965:
--------------------------------------

The proper way to propose a code improvement is to post a patch file.  Please do so and then
we'll discuss.
FYI I already made some performance tweaks to encode/decode as part of SOLR-2155

> Faster GeoHashUtils
> -------------------
>
>                 Key: LUCENE-2965
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2965
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: contrib/spatial
>    Affects Versions: 2.9.2, 2.9.4, 3.0, 3.0.1, 3.0.2, 3.0.3
>            Reporter: 朱文彬
>
> 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 };
> 	}

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message