final class TopKSelector<T>
extends java.lang.Object
k elements added to it, relative to a provided
comparator. "Top" can mean the greatest or the lowest elements, specified in the factory used to
create the TopKSelector instance.
If your input data is available as a Stream, prefer passing Comparators#least(int) to Stream.collect(java.util.stream.Collector). If it is available
as an Iterable or Iterator, prefer Ordering.leastOf(Iterable, int).
This uses the same efficient implementation as Ordering.leastOf(Iterable, int),
offering expected O(n + k log k) performance (worst case O(n log k)) for n calls to offer(T) and a call to topK(), with O(k) memory. In comparison, quickselect has the same
asymptotics but requires O(n) memory, and a PriorityQueue implementation takes O(n log
k). In benchmarks, this implementation performs at least as well as either implementation, and
degrades more gracefully for worst-case input.
The implementation does not necessarily use a stable sorting algorithm; when multiple equivalent elements are added to it, it is undefined which will come first in the output.
| Modifier and Type | Field and Description |
|---|---|
private T[] |
buffer |
private int |
bufferSize |
private java.util.Comparator<? super T> |
comparator |
private int |
k |
private T |
threshold
The largest of the lowest k elements we've seen so far relative to this comparator.
|
| Modifier | Constructor and Description |
|---|---|
private |
TopKSelector(java.util.Comparator<? super T> comparator,
int k) |
| Modifier and Type | Method and Description |
|---|---|
(package private) TopKSelector<T> |
combine(TopKSelector<T> other) |
static <T extends java.lang.Comparable<? super T>> |
greatest(int k)
Returns a
TopKSelector that collects the greatest k elements added to it,
relative to the natural ordering of the elements, and returns them via topK() in
descending order. |
static <T> TopKSelector<T> |
greatest(int k,
java.util.Comparator<? super T> comparator)
Returns a
TopKSelector that collects the greatest k elements added to it,
relative to the specified comparator, and returns them via topK() in descending order. |
static <T extends java.lang.Comparable<? super T>> |
least(int k)
Returns a
TopKSelector that collects the lowest k elements added to it,
relative to the natural ordering of the elements, and returns them via topK() in
ascending order. |
static <T> TopKSelector<T> |
least(int k,
java.util.Comparator<? super T> comparator)
Returns a
TopKSelector that collects the lowest k elements added to it,
relative to the specified comparator, and returns them via topK() in ascending order. |
void |
offer(T elem)
Adds
elem as a candidate for the top k elements. |
void |
offerAll(java.lang.Iterable<? extends T> elements)
Adds each member of
elements as a candidate for the top k elements. |
void |
offerAll(java.util.Iterator<? extends T> elements)
Adds each member of
elements as a candidate for the top k elements. |
private int |
partition(int left,
int right,
int pivotIndex)
Partitions the contents of buffer in the range [left, right] around the pivot element
previously stored in buffer[pivotValue].
|
private void |
swap(int i,
int j) |
java.util.List<T> |
topK()
Returns the top
k elements offered to this TopKSelector, or all elements if
fewer than k have been offered, in the order specified by the factory used to create
this TopKSelector. |
private void |
trim()
Quickselects the top k elements from the 2k elements in the buffer.
|
private final int k
private final java.util.Comparator<? super T> comparator
private final T[] buffer
private int bufferSize
@CheckForNull private T threshold
private TopKSelector(java.util.Comparator<? super T> comparator, int k)
public static <T extends java.lang.Comparable<? super T>> TopKSelector<T> least(int k)
TopKSelector that collects the lowest k elements added to it,
relative to the natural ordering of the elements, and returns them via topK() in
ascending order.java.lang.IllegalArgumentException - if k < 0 or k > Integer.MAX_VALUE / 2public static <T> TopKSelector<T> least(int k, java.util.Comparator<? super T> comparator)
TopKSelector that collects the lowest k elements added to it,
relative to the specified comparator, and returns them via topK() in ascending order.java.lang.IllegalArgumentException - if k < 0 or k > Integer.MAX_VALUE / 2public static <T extends java.lang.Comparable<? super T>> TopKSelector<T> greatest(int k)
TopKSelector that collects the greatest k elements added to it,
relative to the natural ordering of the elements, and returns them via topK() in
descending order.java.lang.IllegalArgumentException - if k < 0 or k > Integer.MAX_VALUE / 2public static <T> TopKSelector<T> greatest(int k, java.util.Comparator<? super T> comparator)
TopKSelector that collects the greatest k elements added to it,
relative to the specified comparator, and returns them via topK() in descending order.java.lang.IllegalArgumentException - if k < 0 or k > Integer.MAX_VALUE / 2public void offer(T elem)
elem as a candidate for the top k elements. This operation takes amortized
O(1) time.private void trim()
private int partition(int left,
int right,
int pivotIndex)
private void swap(int i,
int j)
TopKSelector<T> combine(TopKSelector<T> other)
public void offerAll(java.lang.Iterable<? extends T> elements)
elements as a candidate for the top k elements. This
operation takes amortized linear time in the length of elements.
If all input data to this TopKSelector is in a single Iterable, prefer
Ordering.leastOf(Iterable, int), which provides a simpler API for that use case.
public void offerAll(java.util.Iterator<? extends T> elements)
elements as a candidate for the top k elements. This
operation takes amortized linear time in the length of elements. The iterator is
consumed after this operation completes.
If all input data to this TopKSelector is in a single Iterator, prefer
Ordering.leastOf(Iterator, int), which provides a simpler API for that use case.
public java.util.List<T> topK()
k elements offered to this TopKSelector, or all elements if
fewer than k have been offered, in the order specified by the factory used to create
this TopKSelector.
The returned list is an unmodifiable copy and will not be affected by further changes to
this TopKSelector. This method returns in O(k log k) time.