Module org.apache.lucene.core
Package org.apache.lucene.util

Class IntroSelector

java.lang.Object
org.apache.lucene.util.Selector
org.apache.lucene.util.IntroSelector
Direct Known Subclasses:
ScalarQuantizer.FloatSelector
public abstract class IntroSelector extends Selector
Adaptive selection algorithm based on the introspective quick select algorithm. The quick select algorithm uses an interpolation variant of Tukey's ninther median-of-medians for pivot, and Bentley-McIlroy 3-way partitioning. For the introspective protection, it shuffles the sub-range if the max recursive depth is exceeded.

This selection algorithm is fast on most data shapes, especially on nearly sorted data, or when k is close to the boundaries. It runs in linear time on average.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private SplittableRandom
    random
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    IntroSelector()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    protected int
    compare(int i, int j)
    Compare entries found in slots i and j.
    protected abstract int
    comparePivot(int j)
    Compare the pivot with the slot at j, similarly to compare(i, j).
    private int
    max(int i, int j, int k)
    Returns the index of the max element among three elements at provided indices.
    private int
    median(int i, int j, int k)
    Copy of IntroSorter#median.
    private int
    min(int i, int j, int k)
    Returns the index of the min element among three elements at provided indices.
    final void
    select(int from, int to, int k)
    Reorder elements so that the element at position k is the same as if all elements were sorted and all other elements are partitioned around it: [from, k) only contains elements that are less than or equal to k and (k, to) only contains elements that are greater than or equal to k.
    (package private) void
    select(int from, int to, int k, int maxDepth)
     
    protected abstract void
    setPivot(int i)
    Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
    private void
    shuffle(int from, int to)
    Shuffles the entries between from (inclusive) and to (exclusive) with Durstenfeld's algorithm.
    private void
    sort3(int from)
    Sorts 3 entries starting at from (inclusive).

    Methods inherited from class org.apache.lucene.util.Selector

    checkArgs, swap

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

  • Constructor Details

    • IntroSelector

      public IntroSelector()

  • Method Details

    • select

      public final void select(int from, int to, int k)
      Description copied from class: Selector
      Reorder elements so that the element at position k is the same as if all elements were sorted and all other elements are partitioned around it: [from, k) only contains elements that are less than or equal to k and (k, to) only contains elements that are greater than or equal to k.
      Specified by:
      select in class Selector

    • select

      void select(int from, int to, int k, int maxDepth)

    • min

      private int min(int i, int j, int k)
      Returns the index of the min element among three elements at provided indices.

    • max

      private int max(int i, int j, int k)
      Returns the index of the max element among three elements at provided indices.

    • median

      private int median(int i, int j, int k)
      Copy of IntroSorter#median.

    • sort3

      private void sort3(int from)
      Sorts 3 entries starting at from (inclusive). This specialized method is more efficient than calling Sorter.insertionSort(int, int).

    • shuffle

      private void shuffle(int from, int to)
      Shuffles the entries between from (inclusive) and to (exclusive) with Durstenfeld's algorithm.

    • setPivot

      protected abstract void setPivot(int i)
      Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).

    • comparePivot

      protected abstract int comparePivot(int j)
      Compare the pivot with the slot at j, similarly to compare(i, j).

    • compare

      protected int compare(int i, int j)
      Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).