algorithm - Cálculo incremental de la mediana con eficiencia máxima de memoria

Question

Tengo un proceso que genera valores y que observo. Cuando el proceso termina, quiero calcular la mediana de esos valores.

Si tuviera que calcular la media, solo podría almacenar la suma y el número de valores generados y, por lo tanto, tener el requisito de memoria O (1). ¿Qué tal la mediana? ¿Hay alguna forma de ahorrar en la obvia O (n) proveniente del almacenamiento de todos los valores?

Edición: Interesado en 2 casos: 1) la longitud de la secuencia es conocida, 2) no lo es.

Answer 1

Si tiene valores discretos y mucha repetición, puede almacenar los valores y los recuentos, lo que ahorraría un poco de espacio.

Posiblemente en las etapas del cálculo, usted podría descartar los valores superior ''n'' y inferior ''n'', siempre y cuando esté seguro de que la mediana no está en ese rango superior o inferior.
Por ejemplo, digamos que está esperando 100.000 valores. Cada vez que su número almacenado llega a (digamos) 12,000, puede descartar los 1000 más altos y los 1000 más bajos, reduciendo el almacenamiento a 10,000.

Si la distribución de valores es bastante consistente, esto funcionaría bien. Sin embargo, si existe la posibilidad de que recibas un gran número de valores muy altos o muy bajos cerca del final, eso podría distorsionar tu cálculo. Básicamente, si descartas un valor "alto" que es menor que la mediana (eventual) o un valor "bajo" que es igual o mayor que la mediana (eventual), tu cálculo está desactivado.

Actualizar
Poco de un ejemplo
Digamos que el conjunto de datos son los números 1,2,3,4,5,6,7,8,9.
Por inspección la mediana es 5.

Digamos que los primeros 5 números que obtienes son 1,3,5,7,9.
Para ahorrar espacio descartamos lo más alto y lo más bajo, dejando 3,5,7.
Ahora consigue dos más, 2,6 así que nuestro almacenamiento es 2,3,5,6,7.
Descarta lo más alto y lo más bajo, dejando 3,5,6.
Consigue los dos últimos 4,8 y tenemos 3,4,5,6,8.
La mediana sigue siendo 5 y el mundo es un buen lugar.

Sin embargo, digamos que los primeros cinco números que obtenemos son 1,2,3,4,5.
Deseche la parte superior e inferior dejando 2,3,4.
Consigue dos más 6,7 y tenemos 2,3,4,6,7.
Deseche la parte superior e inferior dejando 3,4,6.
Consigue las dos últimas 8,9 y tenemos 3,4,6,8,9.
Con una mediana de 6 que es incorrecta.

Si nuestros números están bien distribuidos, podemos seguir recortando las extremidades. Si se pueden agrupar en grandes cantidades o en grandes cantidades, el descarte es arriesgado.

Answer 2

Usted puede

• Utilice las estadísticas, si eso es aceptable, por ejemplo, podría usar el muestreo.
• Usa el conocimiento sobre tu flujo de números
  • utilizando una aproximación de tipo de conteo: k valores distintos significa almacenar memoria O(k) )
  • o tire de los valores atípicos conocidos y mantenga un contador (alto, bajo).
  • Si sabe que no tiene duplicados, podría usar un mapa de bits ... pero eso es solo una constante más pequeña para O(n) .

Answer 3

Deberá almacenar al menos diez puntos (n / 2), ya que cualquiera de los primeros n / 2 puntos podría ser la mediana. Probablemente sea más sencillo simplemente almacenar los puntos y encontrar la mediana. Si guardar puntos ceil (n / 2) es valioso, entonces lea los primeros n / 2 puntos en una lista ordenada (probablemente lo mejor es un árbol binario), luego, a medida que se agreguen nuevos puntos, saque los puntos altos o bajos y mantenga seguimiento de la cantidad de puntos en cada extremo expulsado.

Editar:

Si se desconoce la longitud del flujo, entonces, obviamente, como observó Stephen en los comentarios, no tenemos más remedio que recordar todo. Si los elementos duplicados son probables, posiblemente podríamos ahorrar un poco de memoria usando la idea de los delfines de almacenar valores y conteos.