java.lang.Object
org.apache.lucene.util.Selector
org.apache.lucene.util.IntroSelector
- Direct Known Subclasses:
ScalarQuantizer.FloatSelector
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 -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected int
compare
(int i, int j) Compare entries found in slotsi
andj
.protected abstract int
comparePivot
(int j) Compare the pivot with the slot atj
, similarly tocompare(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 ofIntroSorter#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 positionk
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 tok
and(k, to)
only contains elements that are greater than or equal tok
.(package private) void
select
(int from, int to, int k, int maxDepth) protected abstract void
setPivot
(int i) Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(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).
-
Field Details
-
random
-
-
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 positionk
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 tok
and(k, to)
only contains elements that are greater than or equal tok
. -
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 ofIntroSorter#median
. -
sort3
private void sort3(int from) Sorts 3 entries starting at from (inclusive). This specialized method is more efficient than callingSorter.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 sloti
so that it can later be used as a pivot, seecomparePivot(int)
. -
comparePivot
protected abstract int comparePivot(int j) Compare the pivot with the slot atj
, similarly tocompare(i, j)
. -
compare
protected int compare(int i, int j) Compare entries found in slotsi
andj
. The contract for the returned value is the same asComparator.compare(Object, Object)
.
-