本页尚未翻译,因此以英文显示。 参与翻译

fxTopBy · fxBottomBy

The top 3, the 5 cheapest — in one pass, already in order, without sorting the rest.

List<A> fxTopBy<A>(int k, Object? Function(A a) f, Iterable<A> iterable) List<A> fxBottomBy<A>(int k, Object? Function(A a) f, Iterable<A> iterable) Future<List<A>> fxTopByAsync<A>(int k, Object? Function(A a) f, FxAsyncIterable<A> iterable) Future<List<A>> fxBottomByAsync<A>(int k, Object? Function(A a) f, FxAsyncIterable<A> iterable) Fx<T> Fx<T>.topBy(int k, Object? Function(T a) f) // chain (sync) Fx<T> Fx<T>.bottomBy(int k, Object? Function(T a) f) // chain (sync) Future<List<T>> FxAsync<T>.topBy(int k, Object? Function(T a) f) // chain (async) Future<List<T>> FxAsync<T>.bottomBy(int k, Object? Function(T a) f) // chain (async)

Lecture

The usual way to read a leaderboard is sortByDesc(f, xs).take(k): sort the whole input, keep k, throw the rest away. fxTopBy(k, f, xs) returns the same k elements from one pass that keeps only a k-sized boundary — memory is proportional to k, not to the input, and nothing outside the boundary is retained. fxBottomBy(k, f, xs) is the mirror image: the k smallest keys, smallest first.

The result needs no second pass. It is ordered — descending for topBy, ascending for bottomBy — and a tie is won by the element seen first: a later element whose key only equals the weakest kept key does not displace it, and equal keys inside the result keep their input order. k <= 0 returns an empty list; a k past the end returns every element, ordered. Keys are compared exactly as sortBy compares them, so any Comparable works.

The boundary is kept by insertion, so the worst case is O(n·k): this is for a small k over a large input; when k approaches the input length, sort instead. On the sync chain fx(xs).topBy(k, f) is a step — it returns an Fx, so you can keep chaining — while FxAsync.topBy and the fxTopByAsync twins end the chain with a Future<List>; their key function stays synchronous. fxdart extension (not part of FxTS) — the shape of Python's heapq.nlargest.

Demo 1 · Order, ties & k

Demo 2 · On the chain, sync and async

Try it yourself

Exercise: replace the sort-and-take with one call.

Related: sortByDesc — when you need the whole order · maxBy · minBy — when k is 1 · quantile — one position, not the first k