fxTopBy · fxBottomBy
Los 3 mejores, los 5 más baratos — en una sola pasada, ya en orden, sin ordenar el resto.
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.
sortByDesc — cuando necesitas el orden completo ·
maxBy · minBy — cuando k es 1 ·
quantile — una posición, no los primeros k