lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mikemcc...@apache.org
Subject lucene-solr git commit: Replace O(N^2) cost bitset clearing with O(N)
Date Fri, 11 Mar 2016 23:42:44 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/master 007d41c9f -> 684b22222


Replace O(N^2) cost bitset clearing with O(N)


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/684b2222
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/684b2222
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/684b2222

Branch: refs/heads/master
Commit: 684b222221ab0bb1a617b579f79fdf8c612fa16f
Parents: 007d41c
Author: Mike McCandless <mikemccand@apache.org>
Authored: Fri Mar 11 18:43:34 2016 -0500
Committer: Mike McCandless <mikemccand@apache.org>
Committed: Fri Mar 11 18:43:34 2016 -0500

----------------------------------------------------------------------
 .../java/org/apache/lucene/util/bkd/BKDWriter.java   | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/684b2222/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
index f5a2d81..f1aba9d 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
@@ -1126,6 +1126,14 @@ public class BKDWriter implements Closeable {
       byte[] maxSplitPackedValue = new byte[packedBytesLength];
       System.arraycopy(maxPackedValue, 0, maxSplitPackedValue, 0, packedBytesLength);
 
+      // When we are on this dim, below, we clear the ordBitSet:
+      int dimToClear;
+      if (numDims - 1 == splitDim) {
+        dimToClear = numDims - 2;
+      } else {
+        dimToClear = numDims - 1;
+      }
+
       for(int dim=0;dim<numDims;dim++) {
 
         if (dim == splitDim) {
@@ -1152,6 +1160,9 @@ public class BKDWriter implements Closeable {
             if (ordBitSet.get(ord)) {
               rightPointWriter.append(packedValue, ord, docID);
               nextRightCount++;
+              if (dim == dimToClear) {
+                ordBitSet.clear(ord);
+              }
             } else {
               leftPointWriter.append(packedValue, ord, docID);
             }
@@ -1164,10 +1175,6 @@ public class BKDWriter implements Closeable {
         }
       }
 
-      if (numDims > 1) {
-        ordBitSet.clear(0, pointCount);
-      }
-
       // Recurse on left tree:
       build(2*nodeID, leafNodeOffset, leftSlices,
             ordBitSet, out,


Mime
View raw message