You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2016/03/12 00:42:44 UTC
lucene-solr git commit: Replace O(N^2) cost bitset clearing with O(N)
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 <mi...@apache.org>
Authored: Fri Mar 11 18:43:34 2016 -0500
Committer: Mike McCandless <mi...@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,