You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by dw...@apache.org on 2022/03/30 17:28:05 UTC
[lucene] branch main updated: Implement method to bulk add all collection elements to a PriorityQueue (#770)
This is an automated email from the ASF dual-hosted git repository.
dweiss pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 69b040f Implement method to bulk add all collection elements to a PriorityQueue (#770)
69b040f is described below
commit 69b040fc6292ac47d7f7fc8bc3b7fd601794e54b
Author: Baurzhan <ba...@gmail.com>
AuthorDate: Wed Mar 30 19:28:01 2022 +0200
Implement method to bulk add all collection elements to a PriorityQueue (#770)
Implement method to add all collection elements to a PriorityQueue
Co-authored-by: Dawid Weiss <da...@carrotsearch.com>
---
lucene/CHANGES.txt | 4 +-
.../apache/lucene/search/ExactPhraseMatcher.java | 4 +-
.../java/org/apache/lucene/util/PriorityQueue.java | 32 ++++++++++++
.../org/apache/lucene/util/TestPriorityQueue.java | 59 ++++++++++++++++++++++
4 files changed, 97 insertions(+), 2 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 9baf646..814df40 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -74,7 +74,9 @@ have readonly `Monitor` instances. (Niko Usai)
Improvements
---------------------
-(No changes)
+
+* LUCENE-10494: Implement method to bulk add all collection elements to a PriorityQueue.
+ (Bauyrzhan Sakhariyev)
Optimizations
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/ExactPhraseMatcher.java b/lucene/core/src/java/org/apache/lucene/search/ExactPhraseMatcher.java
index ca125e7..36020c9 100644
--- a/lucene/core/src/java/org/apache/lucene/search/ExactPhraseMatcher.java
+++ b/lucene/core/src/java/org/apache/lucene/search/ExactPhraseMatcher.java
@@ -269,6 +269,7 @@ public final class ExactPhraseMatcher extends PhraseMatcher {
boolean hasImpacts = false;
List<Impact> onlyImpactList = null;
+ List<SubIterator> subIterators = new ArrayList<>(impacts.length);
for (int i = 0; i < impacts.length; ++i) {
int impactsLevel = getLevel(impacts[i], docIdUpTo);
if (impactsLevel == -1) {
@@ -284,7 +285,7 @@ public final class ExactPhraseMatcher extends PhraseMatcher {
}
SubIterator subIterator = new SubIterator(impactList);
- pq.add(subIterator);
+ subIterators.add(subIterator);
if (hasImpacts == false) {
hasImpacts = true;
onlyImpactList = impactList;
@@ -308,6 +309,7 @@ public final class ExactPhraseMatcher extends PhraseMatcher {
// We walk impacts in parallel through a PQ ordered by freq. At any time,
// the competitive impact consists of the lowest freq among all entries of
// the PQ (the top) and the highest norm (tracked separately).
+ pq.addAll(subIterators);
List<Impact> mergedImpacts = new ArrayList<>();
SubIterator top = pq.top();
int currentFreq = top.current.freq;
diff --git a/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java b/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
index fbd06ab..4760256 100644
--- a/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
+++ b/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java
@@ -16,6 +16,7 @@
*/
package org.apache.lucene.util;
+import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.function.Supplier;
@@ -108,6 +109,37 @@ public abstract class PriorityQueue<T> implements Iterable<T> {
}
/**
+ * Adds all elements of the collection into the queue. This method should be preferred over
+ * calling {@link #add(Object)} in loop if all elements are known in advance as it builds queue
+ * faster.
+ *
+ * <p>If one tries to add more objects than the maxSize passed in the constructor, an {@link
+ * ArrayIndexOutOfBoundsException} is thrown.
+ */
+ public void addAll(Collection<T> elements) {
+ if (this.size + elements.size() > this.maxSize) {
+ throw new ArrayIndexOutOfBoundsException(
+ "Cannot add "
+ + elements.size()
+ + " elements to a queue with remaining capacity: "
+ + (maxSize - size));
+ }
+
+ // Heap with size S always takes first S elements of the array,
+ // and thus it's safe to fill array further - no actual non-sentinel value will be overwritten.
+ Iterator<T> iterator = elements.iterator();
+ while (iterator.hasNext()) {
+ this.heap[size + 1] = iterator.next();
+ this.size++;
+ }
+
+ // The loop goes down to 1 as heap is 1-based not 0-based.
+ for (int i = (size >>> 1); i >= 1; i--) {
+ downHeap(i);
+ }
+ }
+
+ /**
* Determines the ordering of objects in this priority queue. Subclasses must define this one
* method.
*
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java b/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
index 3152521..ed22657 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestPriorityQueue.java
@@ -17,6 +17,7 @@
package org.apache.lucene.util;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
@@ -163,6 +164,55 @@ public class TestPriorityQueue extends LuceneTestCase {
assertEquals((Integer) 2, pq.top());
}
+ public void testAddAllToEmptyQueue() {
+ Random random = random();
+ int size = 10;
+ List<Integer> list = new ArrayList<>();
+ for (int i = 0; i < size; i++) {
+ list.add(random.nextInt());
+ }
+ IntegerQueue pq = new IntegerQueue(size);
+ pq.addAll(list);
+
+ pq.checkValidity();
+ assertOrderedWhenDrained(pq, list);
+ }
+
+ public void testAddAllToPartiallyFilledQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> oneByOne = new ArrayList<>();
+ List<Integer> bulkAdded = new ArrayList<>();
+ Random random = random();
+ for (int i = 0; i < 10; i++) {
+ bulkAdded.add(random.nextInt());
+
+ int x = random.nextInt();
+ pq.add(x);
+ oneByOne.add(x);
+ }
+
+ pq.addAll(bulkAdded);
+ pq.checkValidity();
+
+ oneByOne.addAll(bulkAdded); // Gather all "reference" data.
+ assertOrderedWhenDrained(pq, oneByOne);
+ }
+
+ public void testAddAllDoesNotFitIntoQueue() {
+ IntegerQueue pq = new IntegerQueue(20);
+ List<Integer> list = new ArrayList<>();
+ Random random = random();
+ for (int i = 0; i < 11; i++) {
+ list.add(random.nextInt());
+ pq.add(random.nextInt());
+ }
+
+ assertThrows(
+ "Cannot add 11 elements to a queue with remaining capacity: 9",
+ ArrayIndexOutOfBoundsException.class,
+ () -> pq.addAll(list));
+ }
+
public void testRemovalsAndInsertions() {
Random random = random();
int numDocsInPQ = TestUtil.nextInt(random, 1, 100);
@@ -297,4 +347,13 @@ public class TestPriorityQueue extends LuceneTestCase {
};
});
}
+
+ private void assertOrderedWhenDrained(IntegerQueue pq, List<Integer> referenceDataList) {
+ Collections.sort(referenceDataList);
+ int i = 0;
+ while (pq.size() > 0) {
+ assertEquals(pq.pop(), referenceDataList.get(i));
+ i++;
+ }
+ }
}