fxTopBy · fxBottomBy

Los 3 mejores, los 5 más baratos — en una sola pasada, ya en orden, sin ordenar el resto.

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)

Lección

La forma habitual de leer una clasificación es sortByDesc(f, xs).take(k): ordenar toda la entrada, quedarse con k y tirar el resto. fxTopBy(k, f, xs) devuelve los mismos k elementos en una sola pasada que solo mantiene una frontera de tamaño k — la memoria es proporcional a k, no a la entrada, y nada fuera de la frontera se retiene. fxBottomBy(k, f, xs) es su imagen especular: las k claves más pequeñas, de menor a mayor.

El resultado no necesita una segunda pasada. Está ordenado — descendente en topBy, ascendente en bottomBy — y un empate lo gana el primer elemento visto: un elemento posterior cuya clave solo iguala a la más débil de la frontera no la desplaza, y las claves iguales dentro del resultado conservan el orden de entrada. k <= 0 devuelve una lista vacía; un k mayor que la entrada devuelve todos los elementos, ordenados. Las claves se comparan exactamente como en sortBy, así que sirve cualquier Comparable.

La frontera se mantiene por inserción, así que el peor caso es O(n·k): es para un k pequeño sobre una entrada grande; cuando k se acerca a la longitud de la entrada, ordena. En la cadena síncrona fx(xs).topBy(k, f) es un paso — devuelve un Fx, así que puedes seguir encadenando —, mientras que FxAsync.topBy y las variantes fxTopByAsync terminan la cadena con un Future<List>; su función de clave sigue siendo síncrona. Extensión de fxdart (no forma parte de FxTS) — la forma de heapq.nlargest de Python.

Demo 1 · Orden, empates & k

Demo 2 · En la cadena, síncrona y asíncrona

Pruébalo tú

Ejercicio: sustituye el ordenar-y-tomar por una sola llamada.

Relacionado: sortByDesc — cuando necesitas el orden completo · maxBy · minBy — cuando k es 1 · quantile — una posición, no los primeros k