Encuentre la mediana móvil a partir de un flujo de números enteros
Posible duplicado:
algoritmo de mediana móvil en C
Dado que los números enteros se leen de un flujo de datos. Encuentre la mediana de los elementos leídos hasta ahora de manera eficiente.
Solución que he leído: Podemos usar un montón máximo en el lado izquierdo para representar elementos que son menores que la mediana efectiva y un montón mínimo en el lado derecho para representar elementos que son mayores que la mediana efectiva.
Después de procesar un elemento entrante, la cantidad de elementos en el montón difiere como máximo en 1 elemento. Cuando ambos montones contienen la misma cantidad de elementos, encontramos el promedio de los datos raíz del montón como mediana efectiva. Cuando los montones no están equilibrados, seleccionamos la mediana efectiva de la raíz del montón que contiene más elementos.
Pero, ¿cómo construiríamos un montón máximo y un montón mínimo, es decir, cómo sabríamos la mediana efectiva aquí? Creo que insertaríamos 1 elemento en max-heap y luego el siguiente elemento en min-heap, y así sucesivamente para todos los elementos. Corrígeme si me equivoco aquí.
Hay varias soluciones diferentes para encontrar la mediana móvil a partir de datos transmitidos; hablaré brevemente de ellas al final de la respuesta.
La pregunta es sobre los detalles de una solución específica (solución de montón máximo/mínimo), y a continuación se explica cómo funciona la solución basada en montón:
Para los dos primeros elementos, agregue uno más pequeño al maxHeap de la izquierda y uno más grande al minHeap de la derecha. Luego procese los datos de la transmisión uno por uno,
Step 1: Add next item to one of the heaps
if next item is smaller than maxHeap root add it to maxHeap,
else add it to minHeap
Step 2: Balance the heaps (after this step heaps will be either balanced or
one of them will contain 1 more item)
if number of elements in one of the heaps is greater than the other by
more than 1, remove the root element from the one containing more elements and
add to the other one
Luego, en cualquier momento dado, puedes calcular la mediana de esta manera:
If the heaps contain equal amount of elements;
median = (root of maxHeap + root of minHeap)/2
Else
median = root of the heap with more elements
Ahora hablaré del problema en general como prometí al principio de la respuesta. Encontrar la mediana móvil a partir de un flujo de datos es un problema difícil, y encontrar una solución exacta con restricciones de memoria de manera eficiente probablemente sea imposible para el caso general. Por otro lado, si los datos tienen algunas características que podamos explotar, podemos desarrollar soluciones especializadas eficientes. Por ejemplo, si sabemos que los datos son de tipo integral, entonces podemos usar la ordenación por conteo , que puede brindarle un algoritmo de tiempo constante de memoria constante. La solución basada en montón es una solución más general porque también se puede utilizar para otros tipos de datos (dobles). Y, por último, si no se requiere la mediana exacta y una aproximación es suficiente, puede intentar estimar una función de densidad de probabilidad para los datos y estimar la mediana usando esa.
Si la varianza de la entrada está distribuida estadísticamente (por ejemplo, normal, log-normal, etc.), entonces el muestreo de yacimientos es una forma razonable de estimar percentiles/medianas a partir de un flujo de números arbitrariamente largo.
int n = 0; // Running count of elements observed so far
#define SIZE 10000
int reservoir[SIZE];
while(streamHasData())
{
int x = readNumberFromStream();
if (n < SIZE)
{
reservoir[n++] = x;
}
else
{
int p = random(++n); // Choose a random number 0 >= p < n
if (p < SIZE)
{
reservoir[p] = x;
}
}
}
"depósito" es entonces una muestra continua, uniforme (justa) de todas las entradas, independientemente de su tamaño. Encontrar la mediana (o cualquier percentil) es entonces una cuestión sencilla de clasificar el depósito y sondear el punto interesante.
Dado que el depósito tiene un tamaño fijo, se puede considerar que la clasificación es efectivamente O(1), y este método se ejecuta con tiempo y consumo de memoria constantes.
