Encuentra la mediana de ejecución de una secuencia de enteros

Posible duplicado:
Algoritmo de la mediana de rodadura en C

Dado que los enteros se leen de una secuencia de datos. Encuentra la mediana de 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, el número de elementos en montones difiere a lo sumo en 1 elemento. Cuando ambos montones contienen el mismo número de elementos, encontramos el promedio de los datos de 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 mínimo, es decir, cómo podríamos saber la mediana efectiva aquí? Creo que insertaríamos 1 elemento en max-heap y luego el siguiente 1 elemento en min-heap, y así sucesivamente para todos los elementos. Corrígeme si me equivoco aquí.

Hay una serie de soluciones diferentes para encontrar la mediana de ejecución de los datos transmitidos, hablaré brevemente de ellos al final de la respuesta.

La pregunta es acerca de los detalles de una solución específica (solución de montón máxima de montones / min) y cómo funciona la solución basada en montones se explica a continuación:

Para los primeros dos elementos, agregue el más pequeño al maxHeap a la izquierda y el más grande al minHeap a la derecha. Luego, procese los datos de la secuencia 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 una mediana como esta:

  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é sobre el problema en general como se prometió al comienzo de la respuesta. Encontrar una mediana de ejecución 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 es probablemente imposible para el caso general. Por otro lado, si los datos tienen algunas características que podemos explotar, podemos desarrollar soluciones especializadas eficientes. Por ejemplo, si sabemos que los datos son de tipo integral, podemos usar la clasificación por conteo , que puede proporcionarle un algoritmo de constante de memoria constante. La solución basada en Heap es una solución más general porque también se puede usar 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 eso.

Si no puede mantener todos los elementos en la memoria a la vez, este problema se vuelve mucho más difícil. La solución de montón requiere que mantenga todos los elementos en la memoria a la vez. Esto no es posible en la mayoría de las aplicaciones de este problema en el mundo real.

En cambio, cuando vea números, realice un seguimiento de la cantidad de veces que vea cada número entero. Suponiendo enteros de 4 bytes, son 2 ^ 32 cubos, o como máximo 2 ^ 33 enteros (clave y número para cada int), que son 2 ^ 35 bytes o 32 GB. Es probable que sea mucho menos que esto porque no necesita almacenar la clave o contar para aquellas entradas que son 0 (es decir, como un default en python). Esto lleva tiempo constante para insertar cada nuevo entero.

Luego, en cualquier punto, para encontrar la mediana, simplemente use los recuentos para determinar qué número entero es el elemento medio. Esto lleva tiempo constante (aunque sea una gran constante, pero constante, no obstante).

Si la varianza de la entrada se distribuye estadísticamente (p. Ej., Normal, log-normal … etc.), el muestreo del yacimiento 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; } } } 

"reservorio" es entonces una muestra en ejecución, uniforme (regular) de todas las entradas, independientemente del tamaño. Encontrar la mediana (o cualquier percentil) es una cuestión directa de ordenar el depósito y sondear el punto interesante.

Como el depósito es de tamaño fijo, se puede considerar que el ordenamiento es efectivamente O (1), y este método se ejecuta con consumo constante de tiempo y memoria.

La forma más eficiente de calcular un percentil de una secuencia que he encontrado es el algoritmo P²: Raj Jain, Imrich Chlamtac: el algoritmo P² para el cálculo dynamic de cuantiilos e histogtwigs sin almacenar observaciones. Commun. ACM 28 (10): 1076 – 1085 (1985)

El algoritmo es sencillo de implementar y funciona extremadamente bien. Sin embargo, es una estimación, así que tenlo en cuenta. Del resumen:

Se propone un algoritmo heurístico para el cálculo dynamic de la mediana y otros cuantiles. Las estimaciones se producen dinámicamente a medida que se generan las observaciones. Las observaciones no se almacenan; por lo tanto, el algoritmo tiene un requisito de almacenamiento muy pequeño y fijo independientemente del número de observaciones. Esto lo hace ideal para implementar en un chip cuantil que se puede usar en controladores y grabadoras industriales. El algoritmo se extiende aún más al trazado de histogtwigs. La precisión del algoritmo se analiza.

Este problema tiene una solución exacta que solo necesita que los elementos vistos más recientemente se guarden en la memoria. Es rápido y se adapta bien.

Una lista jerárquica indexable admite O (ln n) inserción, eliminación y búsqueda indexada de elementos arbitrarios mientras se mantiene el orden ordenado. Cuando se combina con una cola FIFO que rastrea la n-ésima entrada más antigua, la solución es simple:

 class RunningMedian: 'Fast running median with O(lg n) updates where n is the window size' def __init__(self, n, iterable): self.it = iter(iterable) self.queue = deque(islice(self.it, n)) self.skiplist = IndexableSkiplist(n) for elem in self.queue: self.skiplist.insert(elem) def __iter__(self): queue = self.queue skiplist = self.skiplist midpoint = len(queue) // 2 yield skiplist[midpoint] for newelem in self.it: oldelem = queue.popleft() skiplist.remove(oldelem) queue.append(newelem) skiplist.insert(newelem) yield skiplist[midpoint] 

Aquí hay enlaces para completar el código de trabajo (una versión de clase fácil de entender y una versión de generador optimizada con el código de skiplist indexable en línea):

Una forma intuitiva de pensar sobre esto es que si tuviera un árbol binario completamente balanceado, entonces la raíz sería el elemento mediano, ya que allí habría el mismo número de elementos más pequeños y más grandes. Ahora, si el árbol no está lleno, este no será el caso, ya que faltarán elementos en el último nivel.

Entonces, lo que podemos hacer es tener la mediana y dos árboles binarios balanceados, uno para los elementos menores que la mediana y otro para los elementos mayores que la mediana. Los dos árboles deben mantenerse en el mismo tamaño.

Cuando obtenemos un nuevo entero de la secuencia de datos, lo comparamos con la mediana. Si es mayor que la mediana, lo agregamos al árbol derecho. Si los dos tamaños de árbol difieren más de 1, eliminamos el elemento mínimo del árbol derecho, lo convertimos en la nueva mediana y colocamos la mediana anterior en el árbol izquierdo. Del mismo modo para más pequeño.

Eficiente es una palabra que depende del contexto. La solución a este problema depende de la cantidad de consultas realizadas en relación con la cantidad de inserciones. Supongamos que está insertando N números y K veces hacia el final en el que estaba interesado en la mediana. La complejidad del algoritmo basado en el montón sería O (N log N + K).

Considera la siguiente alternativa. Escriba los números en una matriz, y para cada consulta, ejecute el algoritmo de selección lineal (utilizando el pivote de la conexión rápida, por ejemplo). Ahora tiene un algoritmo con tiempo de ejecución O (KN).

Ahora bien, si K es suficientemente pequeño (consultas infrecuentes), el último algoritmo es en realidad más eficiente y viceversa.

¿No puedes hacer esto con solo un montón? Actualización: no. Ver el comentario.

Invariant: después de leer 2*n entradas, el min-heap contiene el n más grande de ellos.

Bucle: lee 2 entradas. Añádalos al montón y elimine los mínimos del montón. Esto restablece el invariante.

Entonces, cuando se han leído 2n entradas, el mínimo del montón es el enésimo más grande. Deberá haber una pequeña complicación adicional para promediar los dos elementos alrededor de la posición mediana y para manejar consultas después de un número impar de entradas.