Computación mediana incremental con la máxima eficiencia de memoria

Question

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

Si tuviera que calcular la media, podría simplemente almacenar la suma y el número de valores generados y así tener O (1) requisito de memoria. ¿Qué tal la mediana? ¿Hay alguna manera de ahorrar en el obvio O (n) que proviene de almacenar todos los valores?

Editar: Interesado en 2 casos: 1) la longitud del flujo es conocida, 2) no lo es.

Answer 1

usted va a necesitar para almacenar al menos ceil (n/2) puntos, porque cualquiera de las primeras N/2 puntos podría ser la mediana. Probablemente, lo más simple sea almacenar los puntos y encontrar la mediana. Si guardar el ceil (n/2) puntos es valioso, lea los primeros n/2 puntos en una lista ordenada (un árbol binario es probablemente el mejor), luego, cuando se agreguen nuevos puntos, elimine los puntos bajos o altos y mantenga seguimiento del número de puntos en cada extremo expulsado.

Editar:

Si la longitud de flujo es desconocido, entonces, evidentemente, como Stephen observó en los comentarios, entonces no tenemos más remedio que recordar todo. Si hay elementos duplicados, posiblemente podamos guardar un poco de memoria usando la idea de Dolphins de almacenar valores y conteos.

Answer 2

Puede

• Use estadísticas, si eso es aceptable - por ejemplo, se podría utilizar el muestreo.
• Usar el conocimiento acerca de su flujo de números
  • usando una especie de recuento como enfoque: k valores distintos medios de almacenamiento de memoria O(k))
  • o tirar los valores extremos conocidos y tener un contador (alta, baja).
  • 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

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 etapas a través de la computación que podría desprenderse de la parte superior 'n' e inferior 'n' valores, siempre y cuando esté seguro de que la mediana no está en ese rango superior o inferior.
p. Supongamos que espera 100.000 valores. Cada vez que su número almacenado llega a (digamos) 12,000, puede descartar el 1000 más alto y el 1000 más bajo, volviendo a almacenar 10.000.

Si la distribución de valores es bastante uniforme, esto funcionaría bien. Sin embargo, si existe la posibilidad de que reciba una gran cantidad de valores muy altos o muy bajos cerca del final, eso puede distorsionar su cálculo. Básicamente, si descarta un valor "alto" que es menor que la mediana (eventual) o un valor "bajo" que es igual o mayor que la mediana (eventual), entonces su cálculo está desactivado.

actualización
Bit de un ejemplo
Digamos que el conjunto de datos es el número 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 la más alta y la más baja, dejando 3,5,7
Ahora conseguir dos más, 2,6 por lo que nuestro almacenamiento es 2,3,5,6,7
Descartar la más alta y la más baja, dejando 3,5,6
Obtenga los últimos dos 4,8 y tenemos 3,4,5,6,8
Median sigue siendo 5 y el mundo es un buen lugar.

Sin embargo, supongamos que los cinco primeros números que obtenemos son 1,2,3,4,5
Descartar parte superior e inferior dejando 2,3,4
conseguir dos más 6,7 y tenemos 2, 3,4,6,7
Descartar arriba y abajo dejando 3,4,6
Obtener los últimos dos 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 los extremos. Si se agrupan en grandes cantidades o en pequeños números, descartarlo es arriesgado.