@GwtCompatible 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 an Iterable
or Iterator
, prefer
Ordering.leastOf(Iterable, int)
, which provides the same implementation with an
interface tailored to that use case.
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 |
---|---|
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
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
public 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
public 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
public 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
public void offer(@Nullable 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)
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.