Calcular la mediana – javascript

Solución:

Cambie su método de mediana a esto:

function median(values){
  if(values.length ===0) return 0;

  values.sort(function(a,b){
    return a-b;
  });

  var half = Math.floor(values.length / 2);

  if (values.length % 2)
    return values[half];

  return (values[half - 1] + values[half]) / 2.0;
}

violín

Las soluciones anteriores (ordenar y luego buscar el medio) están bien, pero son lentas en conjuntos de datos grandes. Ordenar los datos primero tiene una complejidad de nx log (n).

Existe un algoritmo de mediana más rápido, que consiste en segregar la matriz en dos según un pivote, y luego buscar la mediana en el conjunto mayor. Aquí hay algo de código javascript, pero aquí hay una explicación más detallada

// Trying some array
alert(quickselect_median([7,3,5])); // 2300,5,4,0,123,2,76,768,28]));

function quickselect_median(arr) {
   const L = arr.length, halfL = L/2;
   if (L % 2 == 1)
      return quickselect(arr, halfL);
   else
      return 0.5 * (quickselect(arr, halfL - 1) + quickselect(arr, halfL));
}

function quickselect(arr, k) {
   // Select the kth element in arr
   // arr: List of numerics
   // k: Index
   // return: The kth element (in numerical order) of arr
   if (arr.length == 1)
      return arr[0];
   else {
      const pivot = arr[0];
      const lows = arr.filter((e)=>(e<pivot));
      const highs = arr.filter((e)=>(e>pivot));
      const pivots = arr.filter((e)=>(e==pivot));
      if (k < lows.length) // the pivot is too high
         return quickselect(lows, k);
      else if (k < lows.length + pivots.length)// We got lucky and guessed the median
         return pivot;
      else // the pivot is too low
         return quickselect(highs, k - lows.length - pivots.length);
   }
}

Los lectores astutos notarán algunas cosas:

1. Simplemente transcribí la solución Python de Russel Cohen a JS, así que todo elogio para él.
2. Hay varias optimizaciones pequeñas que vale la pena hacer, pero vale la pena hacer una paralelización, y el código tal como está es más fácil de cambiar en una versión más rápida de un solo subproceso o una versión más rápida de varios subprocesos.
3. Este es el tiempo lineal promedio
   algoritmo, hay un algoritmo más eficiente determinista versión de tiempo lineal, consulte la publicación de Russel para obtener más detalles, incluidos los datos de rendimiento.

ADICION 19 de septiembre de 2019:

Un comentario pregunta si vale la pena hacer esto en javascript. Ejecuté el código en JSPerf y da resultados interesantes.

• si la matriz tiene un número impar de elementos (una cifra para encontrar), la clasificación es un 20% más lenta que esta proposición de “mediana rápida”.

• si hay un número par de elementos, el algoritmo “rápido” es un 40% más lento, porque filtra los datos dos veces, para encontrar los elementos número k y k + 1 para promediar. Es posible escribir una versión de la mediana rápida que no haga esto.

La prueba utilizó matrices bastante pequeñas (29 elementos en la prueba jsperf). El efecto parece ser más pronunciado a medida que las matrices se hacen más grandes. Un punto más general a destacar es: muestra que vale la pena hacer este tipo de optimizaciones en Javascript. Se realiza una gran cantidad de cálculos en JS, incluso con grandes cantidades de datos (piense en paneles, hojas de cálculo, visualizaciones de datos) y en sistemas con recursos limitados (piense en la informática móvil e integrada).

Aquí hay otra solución:

function median(numbers) {
    const sorted = numbers.slice().sort((a, b) => a - b);
    const middle = Math.floor(sorted.length / 2);

    if (sorted.length % 2 === 0) {
        return (sorted[middle - 1] + sorted[middle]) / 2;
    }

    return sorted[middle];
}

console.log(median([4, 5, 7, 1, 33]));

---

---

Utiliza Nuestro Buscador