fxTopBy · fxBottomBy
The top 3, the 5 cheapest — in one pass, already in order, without sorting the rest.
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.
sortByDesc — when you need the whole order ·
maxBy · minBy — when k is 1 ·
quantile — one position, not the first k