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/22 18:09:26 UTC
lucene-solr:master: LUCENE-7242: LatLonTree should build a balanced
tree
Repository: lucene-solr
Updated Branches:
refs/heads/master bf232d763 -> 776f9ec7c
LUCENE-7242: LatLonTree should build a balanced tree
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/776f9ec7
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/776f9ec7
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/776f9ec7
Branch: refs/heads/master
Commit: 776f9ec7c8f2a3a07c5ce5229c66c2f113291ba9
Parents: bf232d7
Author: Robert Muir <rm...@apache.org>
Authored: Fri Apr 22 12:08:16 2016 -0400
Committer: Robert Muir <rm...@apache.org>
Committed: Fri Apr 22 12:09:15 2016 -0400
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +-
.../org/apache/lucene/document/LatLonTree.java | 69 +++++++++-----------
2 files changed, 33 insertions(+), 39 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/776f9ec7/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 4b72294..848e022 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -64,8 +64,7 @@ Optimizations
multiple polygons and holes, with memory usage independent of
polygon complexity. (Karl Wright, Mike McCandless, Robert Muir)
-* LUCENE-7159, LUCENE-7222, LUCENE-7229, LUCENE-7239: Speed up LatLonPoint
- polygon performance. (Robert Muir)
+* LUCENE-7159: Speed up LatLonPoint polygon performance. (Robert Muir, Ryan Ernst)
* LUCENE-7211: Reduce memory & GC for spatial RPT Intersects when the number of
matching docs is small. (Jeff Wartes, David Smiley)
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/776f9ec7/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java
index 8a6e6d8..f7a2927 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonTree.java
@@ -16,17 +16,13 @@
*/
package org.apache.lucene.document;
-import java.util.ArrayList;
import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
-import java.util.Random;
import org.apache.lucene.geo.Polygon;
import org.apache.lucene.index.PointValues.Relation;
/**
- * 2D polygon implementation represented as a randomized interval tree of edges.
+ * 2D polygon implementation represented as a balanced interval tree of edges.
* <p>
* contains() and crosses() are still O(n), but for most practical polygons
* are much faster than brute force.
@@ -338,45 +334,44 @@ final class LatLonTree {
* @return root node of the tree.
*/
private static Edge createTree(double polyLats[], double polyLons[]) {
- // edge order is deterministic and reproducible based on the double values.
- // TODO: make a real balanced tree instead :)
- List<Integer> list = new ArrayList<Integer>(polyLats.length - 1);
+ Edge edges[] = new Edge[polyLats.length - 1];
for (int i = 1; i < polyLats.length; i++) {
- list.add(i);
- }
- Collections.shuffle(list, new Random(Arrays.hashCode(polyLats) ^ Arrays.hashCode(polyLons)));
- Edge root = null;
- for (int i : list) {
double lat1 = polyLats[i-1];
double lon1 = polyLons[i-1];
double lat2 = polyLats[i];
double lon2 = polyLons[i];
- Edge newNode = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2), Math.max(lat1, lat2));
- if (root == null) {
- // add first node
- root = newNode;
- } else {
- // traverse tree to find home for new node, along the path updating all parent's max value along the way.
- Edge node = root;
- while (true) {
- node.max = Math.max(node.max, newNode.max);
- if (newNode.low < node.low) {
- if (node.left == null) {
- node.left = newNode;
- break;
- }
- node = node.left;
- } else {
- if (node.right == null) {
- node.right = newNode;
- break;
- }
- node = node.right;
- }
- }
+ edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2), Math.max(lat1, lat2));
+ }
+ // sort the edges then build a balanced tree from them
+ Arrays.sort(edges, (left, right) -> {
+ int ret = Double.compare(left.low, right.low);
+ if (ret == 0) {
+ ret = Double.compare(left.max, right.max);
}
+ return ret;
+ });
+ return createTree(edges, 0, edges.length - 1);
+ }
+
+ /** Creates tree from sorted edges (with range low and high inclusive) */
+ private static Edge createTree(Edge edges[], int low, int high) {
+ if (low > high) {
+ return null;
+ }
+ // add midpoint
+ int mid = (low + high) >>> 1;
+ Edge newNode = edges[mid];
+ // add children
+ newNode.left = createTree(edges, low, mid - 1);
+ newNode.right = createTree(edges, mid + 1, high);
+ // pull up max values to this node
+ if (newNode.left != null) {
+ newNode.max = Math.max(newNode.max, newNode.left.max);
+ }
+ if (newNode.right != null) {
+ newNode.max = Math.max(newNode.max, newNode.right.max);
}
- return root;
+ return newNode;
}
/**