You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rm...@apache.org on 2016/04/07 17:28:01 UTC
lucene-solr:master: LUCENE-7185: fix tie-breaker sort bug
Repository: lucene-solr
Updated Branches:
refs/heads/master df07e0c30 -> 05d62a357
LUCENE-7185: fix tie-breaker sort bug
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/05d62a35
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/05d62a35
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/05d62a35
Branch: refs/heads/master
Commit: 05d62a357711d1e4e850a5d2fb7336bf0a7acf24
Parents: df07e0c
Author: Robert Muir <rm...@apache.org>
Authored: Thu Apr 7 11:26:46 2016 -0400
Committer: Robert Muir <rm...@apache.org>
Committed: Thu Apr 7 11:27:52 2016 -0400
----------------------------------------------------------------------
.../java/org/apache/lucene/util/SloppyMath.java | 8 +++-
.../org/apache/lucene/util/TestSloppyMath.java | 41 ++++++++++++++------
.../document/TestLatLonPointDistanceSort.java | 4 +-
3 files changed, 38 insertions(+), 15 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/05d62a35/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java b/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
index d8b7056..7be9be1 100644
--- a/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
+++ b/lucene/core/src/java/org/apache/lucene/util/SloppyMath.java
@@ -37,7 +37,9 @@ public class SloppyMath {
* specified in decimal degrees (latitude/longitude). This works correctly
* even if the dateline is between the two points.
* <p>
- * Error is around 1E-5 (0.01mm) from the actual haversine distance.
+ * Error is at most 2E-1 (20cm) from the actual haversine distance, but is typically
+ * much smaller for reasonable distances: around 1E-5 (0.01mm) for distances less than
+ * 1000km.
*
* @param lat1 Latitude of the first point.
* @param lon1 Longitude of the first point.
@@ -87,7 +89,9 @@ public class SloppyMath {
double x2 = lat2 * TO_RADIANS;
double h1 = 1 - cos(x1 - x2);
double h2 = 1 - cos((lon1 - lon2) * TO_RADIANS);
- return h1 + cos(x1) * cos(x2) * h2;
+ double h = h1 + cos(x1) * cos(x2) * h2;
+ // clobber crazy precision so subsequent rounding does not create ties.
+ return Double.longBitsToDouble(Double.doubleToRawLongBits(h) & 0xFFFFFFFFFFFFFFF8L);
}
/**
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/05d62a35/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java b/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
index f11d35f..ea55971 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestSloppyMath.java
@@ -24,6 +24,8 @@ import static org.apache.lucene.util.SloppyMath.haversinSortKey;
import java.util.Random;
+import org.apache.lucene.geo.GeoTestUtil;
+
public class TestSloppyMath extends LuceneTestCase {
// accuracy for cos()
@@ -31,7 +33,9 @@ public class TestSloppyMath extends LuceneTestCase {
// accuracy for asin()
static double ASIN_DELTA = 1E-7;
// accuracy for haversinMeters()
- static double HAVERSIN_DELTA = 1E-5;
+ static double HAVERSIN_DELTA = 2E-1;
+ // accuracy for haversinMeters() for "reasonable" distances (< 1000km)
+ static double REASONABLE_HAVERSIN_DELTA = 1E-5;
public void testCos() {
assertTrue(Double.isNaN(cos(Double.NaN)));
@@ -127,14 +131,14 @@ public class TestSloppyMath extends LuceneTestCase {
/** Test this method sorts the same way as real haversin */
public void testHaversinSortKey() {
for (int i = 0; i < 100000; i++) {
- double centerLat = -90 + 180.0 * random().nextDouble();
- double centerLon = -180 + 360.0 * random().nextDouble();
+ double centerLat = GeoTestUtil.nextLatitude();
+ double centerLon = GeoTestUtil.nextLongitude();
- double lat1 = -90 + 180.0 * random().nextDouble();
- double lon1 = -180 + 360.0 * random().nextDouble();
+ double lat1 = GeoTestUtil.nextLatitude();
+ double lon1 = GeoTestUtil.nextLongitude();
- double lat2 = -90 + 180.0 * random().nextDouble();
- double lon2 = -180 + 360.0 * random().nextDouble();
+ double lat2 = GeoTestUtil.nextLatitude();
+ double lon2 = GeoTestUtil.nextLongitude();
int expected = Integer.signum(Double.compare(haversinMeters(centerLat, centerLon, lat1, lon1),
haversinMeters(centerLat, centerLon, lat2, lon2)));
@@ -148,10 +152,10 @@ public class TestSloppyMath extends LuceneTestCase {
public void testAgainstSlowVersion() {
for (int i = 0; i < 100_000; i++) {
- double lat1 = -90 + 180.0 * random().nextDouble();
- double lon1 = -180 + 360.0 * random().nextDouble();
- double lat2 = -90 + 180.0 * random().nextDouble();
- double lon2 = -180 + 360.0 * random().nextDouble();
+ double lat1 = GeoTestUtil.nextLatitude();
+ double lon1 = GeoTestUtil.nextLongitude();
+ double lat2 = GeoTestUtil.nextLatitude();
+ double lon2 = GeoTestUtil.nextLongitude();
double expected = haversinMeters(lat1, lon1, lat2, lon2);
double actual = slowHaversin(lat1, lon1, lat2, lon2);
@@ -159,6 +163,21 @@ public class TestSloppyMath extends LuceneTestCase {
}
}
+ public void testAgainstSlowVersionReasonable() {
+ for (int i = 0; i < 100_000; i++) {
+ double lat1 = GeoTestUtil.nextLatitude();
+ double lon1 = GeoTestUtil.nextLongitude();
+ double lat2 = GeoTestUtil.nextLatitude();
+ double lon2 = GeoTestUtil.nextLongitude();
+
+ double expected = haversinMeters(lat1, lon1, lat2, lon2);
+ if (expected < 1_000_000) {
+ double actual = slowHaversin(lat1, lon1, lat2, lon2);
+ assertEquals(expected, actual, REASONABLE_HAVERSIN_DELTA);
+ }
+ }
+ }
+
// simple incorporation of the wikipedia formula
private static double slowHaversin(double lat1, double lon1, double lat2, double lon2) {
double h1 = (1 - StrictMath.cos(StrictMath.toRadians(lat2) - StrictMath.toRadians(lat1))) / 2;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/05d62a35/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
index 5ce819c..0003b30 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointDistanceSort.java
@@ -64,7 +64,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase {
TopDocs td = searcher.search(new MatchAllDocsQuery(), 3, sort);
FieldDoc d = (FieldDoc) td.scoreDocs[0];
- assertEquals(462.1028401330432, (Double)d.fields[0], 0.0D);
+ assertEquals(462.1028401330431, (Double)d.fields[0], 0.0D);
d = (FieldDoc) td.scoreDocs[1];
assertEquals(1054.9842850974826, (Double)d.fields[0], 0.0D);
@@ -101,7 +101,7 @@ public class TestLatLonPointDistanceSort extends LuceneTestCase {
TopDocs td = searcher.search(new MatchAllDocsQuery(), 3, sort);
FieldDoc d = (FieldDoc) td.scoreDocs[0];
- assertEquals(462.1028401330432D, (Double)d.fields[0], 0.0D);
+ assertEquals(462.1028401330431D, (Double)d.fields[0], 0.0D);
d = (FieldDoc) td.scoreDocs[1];
assertEquals(1054.9842850974826, (Double)d.fields[0], 0.0D);