fxQuantile · fxQuantileBy
La mediana, un p95 o cualquier percentil — en tiempo lineal, sin ordenarlo todo.
Lección
La forma habitual de leer un percentil es ordenar una copia e indexarla:
sorted[((n - 1) * q).round()]. Eso es
O(n log n) para leer una sola posición.
fxQuantile(q, xs) devuelve el mismo valor mediante
quickselect, que solo particiona hasta que esa posición
queda fijada — O(n) de media, y los pivotes por mediana de
tres mantienen también lineales las entradas ya ordenadas e invertidas,
las formas reales más comunes. La entrada nunca se reordena; el trabajo
se hace sobre una copia.
El rango es de rango más cercano: el valor en el índice
((n - 1) * q).round() de la entrada ordenada. Así,
q = 0 es el mínimo, 1 el máximo y
0.5 la mediana — el mayor de los dos valores centrales cuando
la longitud es par. No se interpola nada: la respuesta es siempre una de
las entradas. Una entrada vacía devuelve null; un
q fuera de [0, 1] lanza ArgumentError.
fxQuantileBy(q, f, xs) ordena por una clave numérica y
devuelve el elemento — el producto de precio mediano, no el
precio mediano. f se ejecuta una vez por elemento. En la
cadena son fx(numbers).quantile(q) y
fx(items).quantileBy(q, f). Extensión de fxdart (sin
contraparte en FxTS).
Demo 1 · Mediana y percentiles
Demo 2 · quantileBy devuelve el elemento
Pruébalo tú
Ejercicio: sustituye el ordenar-e-indexar por una sola llamada.