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++;
+    }
+  }
 }