Top Description Fields Constructors Methods
com.google.common.collect

pack-priv final Class TopKSelector<T extends @Nullable Object>

extends Object
Class Inheritance
Annotations
@GwtCompatible
@ElementTypesAreNonnullByDefault
Static Imports
com.google.common.base.Preconditions.checkArgument, .Preconditions.checkNotNull, com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT
An accumulator that selects the "top" 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 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.

Author
Louis Wasserman

Field Summary

Modifier and TypeField and Description
private final @Nullable T[]
buffer

private int
bufferSize

private final Comparator<? super T>
comparator

private final int
k

private T
threshold

The largest of the lowest k elements we've seen so far relative to this comparator.

Constructor Summary

AccessConstructor and Description
private
TopKSelector(Comparator<? super T> comparator, int k)

Method Summary

Modifier and TypeMethod and Description
pack-priv TopKSelector<T>
combine(TopKSelector<T> other)

public static <T extends Comparable<? super T>> TopKSelector<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.

public static <T extends @Nullable Object> TopKSelector<T>
greatest(int k, 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.

public static <T extends Comparable<? super T>> TopKSelector<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.

public static <T extends @Nullable Object> TopKSelector<T>
least(int k, 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.

public void
offer(T elem)

Adds elem as a candidate for the top k elements.

public void
offerAll(Iterable<? extends T> elements)

Adds each member of elements as a candidate for the top k elements.

public void
offerAll(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)

public 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.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

bufferback to summary
private final @Nullable T[] buffer
bufferSizeback to summary
private int bufferSize
comparatorback to summary
private final Comparator<? super T> comparator
kback to summary
private final int k
thresholdback to summary
private T 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.

Annotations
@CheckForNull

Constructor Detail

TopKSelectorback to summary
private TopKSelector(Comparator<? super T> comparator, int k)

Method Detail

combineback to summary
pack-priv TopKSelector<T> combine(TopKSelector<T> other)
greatestback to summary
public static <T extends Comparable<? super T>> TopKSelector<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.

Exceptions
IllegalArgumentException:
if k < 0 or k > Integer.MAX_VALUE / 2
greatestback to summary
public static <T extends @Nullable Object> TopKSelector<T> greatest(int k, 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.

Exceptions
IllegalArgumentException:
if k < 0 or k > Integer.MAX_VALUE / 2
leastback to summary
public static <T extends Comparable<? super T>> TopKSelector<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.

Exceptions
IllegalArgumentException:
if k < 0 or k > Integer.MAX_VALUE / 2
leastback to summary
public static <T extends @Nullable Object> TopKSelector<T> least(int k, 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.

Exceptions
IllegalArgumentException:
if k < 0 or k > Integer.MAX_VALUE / 2
offerback to summary
public void offer(T elem)

Adds elem as a candidate for the top k elements. This operation takes amortized O(1) time.

offerAllback to summary
public void offerAll(Iterable<? extends T> elements)

Adds each member of 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.

offerAllback to summary
public void offerAll(Iterator<? extends T> elements)

Adds each member of 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.

partitionback to summary
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.

swapback to summary
private void swap(int i, int j)
topKback to summary
public 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.

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.

trimback to summary
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.