Class TopKSelector<T>
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
invalid reference
Comparators#least(int)
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.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final T[]
private int
private final Comparator
<? super T> private final int
private T
The largest of the lowest k elements we've seen so far relative to this comparator. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) TopKSelector
<T> combine
(TopKSelector<T> other) static <T extends Comparable<? super T>>
TopKSelector<T> greatest
(int k) Returns aTopKSelector
that collects the greatestk
elements added to it, relative to the natural ordering of the elements, and returns them viatopK()
in descending order.static <T> TopKSelector
<T> greatest
(int k, Comparator<? super T> comparator) Returns aTopKSelector
that collects the greatestk
elements added to it, relative to the specified comparator, and returns them viatopK()
in descending order.static <T extends Comparable<? super T>>
TopKSelector<T> least
(int k) Returns aTopKSelector
that collects the lowestk
elements added to it, relative to the natural ordering of the elements, and returns them viatopK()
in ascending order.static <T> TopKSelector
<T> least
(int k, Comparator<? super T> comparator) Returns aTopKSelector
that collects the lowestk
elements added to it, relative to the specified comparator, and returns them viatopK()
in ascending order.void
Addselem
as a candidate for the topk
elements.void
Adds each member ofelements
as a candidate for the topk
elements.void
Adds each member ofelements
as a candidate for the topk
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) topK()
Returns the topk
elements offered to thisTopKSelector
, or all elements if fewer thank
have been offered, in the order specified by the factory used to create thisTopKSelector
.private void
trim()
Quickselects the top k elements from the 2k elements in the buffer.
-
Field Details
-
k
private final int k -
comparator
-
buffer
-
bufferSize
private int bufferSize -
threshold
The largest of the lowest k elements we've seen so far relative to this comparator. If bufferSize ≥ k, then we can ignore any elements greater than this value.
-
-
Constructor Details
-
TopKSelector
-
-
Method Details
-
least
Returns aTopKSelector
that collects the lowestk
elements added to it, relative to the natural ordering of the elements, and returns them viatopK()
in ascending order.- Throws:
IllegalArgumentException
- ifk < 0
ork > Integer.MAX_VALUE / 2
-
least
Returns aTopKSelector
that collects the lowestk
elements added to it, relative to the specified comparator, and returns them viatopK()
in ascending order.- Throws:
IllegalArgumentException
- ifk < 0
ork > Integer.MAX_VALUE / 2
-
greatest
Returns aTopKSelector
that collects the greatestk
elements added to it, relative to the natural ordering of the elements, and returns them viatopK()
in descending order.- Throws:
IllegalArgumentException
- ifk < 0
ork > Integer.MAX_VALUE / 2
-
greatest
Returns aTopKSelector
that collects the greatestk
elements added to it, relative to the specified comparator, and returns them viatopK()
in descending order.- Throws:
IllegalArgumentException
- ifk < 0
ork > Integer.MAX_VALUE / 2
-
offer
Addselem
as a candidate for the topk
elements. This operation takes amortized O(1) time. -
trim
private void trim()Quickselects the top k elements from the 2k elements in the buffer. O(k) expected time, O(k log k) worst case. -
partition
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]. Returns the new index of the pivot element, pivotNewIndex, so that everything in [left, pivotNewIndex] is ≤ pivotValue and everything in (pivotNewIndex, right] is greater than pivotValue. -
swap
private void swap(int i, int j) -
combine
-
offerAll
Adds each member ofelements
as a candidate for the topk
elements. This operation takes amortized linear time in the length ofelements
.If all input data to this
TopKSelector
is in a singleIterable
, preferOrdering.leastOf(Iterable, int)
, which provides a simpler API for that use case. -
offerAll
Adds each member ofelements
as a candidate for the topk
elements. This operation takes amortized linear time in the length ofelements
. The iterator is consumed after this operation completes.If all input data to this
TopKSelector
is in a singleIterator
, preferOrdering.leastOf(Iterator, int)
, which provides a simpler API for that use case. -
topK
Returns the topk
elements offered to thisTopKSelector
, or all elements if fewer thank
have been offered, in the order specified by the factory used to create thisTopKSelector
.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.
-