lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dsmi...@apache.org
Subject [16/50] [abbrv] lucene-solr:solr-5750: LUCENE-7242: LatLonTree should build a balanced tree
Date Wed, 27 Apr 2016 18:22:00 GMT
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/solr-5750
Commit: 776f9ec7c8f2a3a07c5ce5229c66c2f113291ba9
Parents: bf232d7
Author: Robert Muir <rmuir@apache.org>
Authored: Fri Apr 22 12:08:16 2016 -0400
Committer: Robert Muir <rmuir@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;
   }
 
   /**


Mime
View raw message