Class 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 java.util.SplittableRandom random  
    • Constructor Summary

      Constructors 
      Constructor Description
      IntroSelector()  
    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      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.
      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 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • random

        private java.util.SplittableRandom random
    • Constructor Detail

      • IntroSelector

        public IntroSelector()
    • Method Detail

      • 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).