algorithm - sacar - Encontrar la mediana en ejecución de un flujo de enteros

media mediana y moda estadistica

Question

Posible duplicado:
Rolling mediana algoritmo en C

Dado que los enteros se leen desde un flujo de datos. Encuentra la mediana de los elementos leídos hasta el momento de manera eficiente.

Solución 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 como máximo en 1 elemento. Cuando ambos montones contienen el mismo número de elementos, encontramos el promedio de los datos de la raíz del montón como media 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 mínimo, es decir, cómo conoceríamos 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 estoy equivocado aquí.

Answer 1

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

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

Bucle: Leer 2 entradas. Agrégalos al montón y elimina el mínimo del montón. Esto restablece el invariante.

Así que cuando se han leído 2n entradas, el mínimo del montón es el noveno 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 las consultas después de un número impar de entradas.

Answer 2

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).

Considere la siguiente alternativa. Plunk los números en una matriz, y para cada consulta, ejecute el algoritmo de selección lineal (utilizando el pivote de ordenamiento rápido, por ejemplo). Ahora tienes un algoritmo con tiempo de ejecución O (KN).

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

Answer 3

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

Una lista de elementos indexables admite la inserción O, ln n), la eliminación y la búsqueda indexada de elementos arbitrarios mientras mantiene el orden ordenado. Cuando se combina con una cola FIFO que rastrea la entrada número n 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í están los 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 lista de salto indexable en línea):

• http://code.activestate.com/recipes/576930-efficient-running-median-using-an-indexable-skipli/

• http://code.activestate.com/recipes/577073 .

Answer 4

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

La pregunta es sobre los detalles de una solución específica (max heap / min heap solution), y cómo funciona la solución basada en heap se explica a continuación:

Para los dos primeros elementos, agregue uno más pequeño al maxHeap a la izquierda y uno más grande al minHeap a la derecha. Luego procesa los datos de flujo 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

Entonces en cualquier momento 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é sobre el problema en general como se prometió al comienzo de la respuesta. Encontrar la mediana de ejecución a partir de un flujo de datos es un problema difícil, y encontrar una solución exacta con limitaciones 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 un tipo integral, entonces podemos usar la ordenación de conteo , que puede darle un algoritmo de tiempo constante de memoria constante. La solución basada en Heap 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 utilizando eso.

Answer 5

La forma más eficiente de calcular un percentil de un flujo que he encontrado es el algoritmo P²: Raj Jain, Chlamtac Imrich: el algoritmo P² para el cálculo dinámico de cuantiles e histogramas sin almacenar observaciones. Comun. 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. De lo abstracto:

Se propone un algoritmo heurístico para el cálculo dinámico 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 fijo muy pequeño, independientemente del número de observaciones. Esto lo hace ideal para implementarlo en un chip de cuantiles que se puede usar en controladores y grabadores industriales. El algoritmo se extiende aún más al trazado de histogramas. Se analiza la precisión del algoritmo.

Answer 6

Si la variación de la entrada está distribuida estadísticamente (p. Ej., Normal, log-normal ... etc), el muestreo de yacimiento es una manera 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 curso, uniforme (regular) de todas las entradas, independientemente de su tamaño. Encontrar la mediana (o cualquier percentil) es entonces una cuestión directa de clasificar el reservorio y encuestar el punto interesante.

Como el reservorio tiene un tamaño fijo, se puede considerar que la clasificación es efectivamente O (1), y este método se ejecuta con un consumo constante de tiempo y memoria.

Answer 7

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 pila requiere que mantengas todos los elementos en la memoria a la vez. Esto no es posible en la mayoría de las aplicaciones del mundo real de este problema.

En cambio, a medida que ve los números, haga un seguimiento del recuento del número de veces que ve cada entero. Suponiendo enteros de 4 bytes, eso es 2 ^ 32 cubos, o como máximo 2 ^ 33 enteros (clave y cuenta para cada int), que es 2 ^ 35 bytes o 32 GB. Es probable que sea mucho menor que esto porque no necesita almacenar la clave o el recuento para las entradas que son 0 (es decir, como un punto predeterminado en Python). Esto lleva tiempo constante para insertar cada nuevo entero.

Luego, en cualquier punto, para encontrar la mediana, simplemente use los conteos para determinar qué entero es el elemento central. Esto lleva tiempo constante (aunque sea una constante grande, pero no obstante constante).

Answer 8

Una forma intuitiva de pensar en esto es que si tuviera un árbol binario equilibrado completo, entonces la raíz sería el elemento de la mediana, 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 del último nivel.

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

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