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

223

Posible duplicado:
algoritmo de mediana variable en C

Dado que los enteros se leen de una secuencia 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, 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 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 1 elemento en min-heap, y así sucesivamente para todos los elementos. Corrígeme si me equivoco aquí.

Luv
fuente
10
Algoritmo inteligente, usando montones. Por el título no pude pensar de inmediato en una solución.
Mooing Duck
1
La solución de Vizier se ve bien para mí, excepto que estaba suponiendo (aunque no dijiste) que esta secuencia podría ser arbitrariamente larga, por lo que no podrías guardar todo en la memoria. ¿Es ese el caso?
Running Wild
2
@RunningWild Para secuencias arbitrariamente largas, puede obtener la mediana de los últimos N elementos mediante el uso de montones de Fibonacci (para obtener eliminaciones de log (N)) y almacenar punteros en los elementos insertados en orden (por ejemplo, una deque), y luego eliminar el más antiguo elemento en cada paso una vez que los montones están llenos (tal vez también mover cosas de un montón a otro). Podría obtener algo mejor que N almacenando el número de elementos repetidos (si hay muchas repeticiones), pero en general, creo que debe hacer algún tipo de suposiciones de distribución si desea la mediana de toda la secuencia.
Dougal
2
Puede comenzar con ambos montones vacíos. Primero int va en un montón; el segundo va en el otro, o mueve el primer elemento al otro montón y luego lo inserta. Esto se generaliza a "no permitir que un montón sea más grande que el otro +1" y no se necesita una carcasa especial (el "valor raíz" de un montón vacío se puede definir como 0)
Jon Watte
Acabo de recibir esta pregunta en una entrevista de MSFT. Gracias por publicar
R Claven

Respuestas:

383

Hay varias soluciones diferentes para encontrar la mediana en 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 (solución de almacenamiento dinámico máximo / almacenamiento dinámico mínimo), y cómo se explica la solución basada en almacenamiento dinámico 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, procese los datos del 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

Luego, en cualquier momento puede 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 una mediana en 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 un tipo integral, entonces podemos usar el orden de conteo, que puede proporcionarle un algoritmo de tiempo constante de memoria constante. La solución basada en el 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 utilizando eso.

Hakan Serce
fuente
66
Estos montones crecen sin límite (es decir, una ventana de 100 elementos que se desliza sobre 10 millones de elementos requeriría que los 10 millones de elementos se almacenen en la memoria). Vea a continuación otra respuesta usando listas de salto indexables que solo requieren que los 100 elementos vistos más recientemente se guarden en la memoria.
Raymond Hettinger
1
También puede tener una solución de memoria limitada utilizando montones, como se explica en uno de los comentarios a la pregunta en sí.
Hakan Serce
1
Puede encontrar una implementación de la solución basada en el montón en c aquí.
AShelly
1
Wow, esto me ayudó no solo a resolver este problema específico, sino que también me ayudó a aprender montones aquí es mi implementación básica en python: github.com/PythonAlgo/DataStruct
swati saoji
2
@HakanSerce ¿Puede explicar por qué hicimos lo que hicimos? Quiero decir que puedo ver que esto funciona, pero no puedo entenderlo intuitivamente.
shiva
51

Si no puede guardar todos los elementos en la memoria a la vez, este problema se vuelve mucho más difícil. La solución de almacenamiento dinámico requiere que mantenga 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 números, realice un seguimiento del recuento del número de veces que ve cada número entero. Suponiendo enteros de 4 bytes, eso es 2 ^ 32 cubos, o como máximo 2 ^ 33 enteros (clave y recuento para cada int), que es 2 ^ 35 bytes o 32 GB. Es probable que sea mucho menos que esto porque no necesita almacenar la clave o contar las entradas que son 0 (es decir, como un defaultdict 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 un tiempo constante (aunque sea una constante grande, pero no obstante constante).

Andrew C
fuente
3
Si casi todos los números se ven una vez, una lista escasa requerirá aún más memoria. Y parece bastante probable que si tiene tantos números que no encajan en el número, que la mayoría de los números aparecerán una vez. A pesar de eso, esta es una solución inteligente para conteos masivos de números.
Mooing Duck
1
Para una lista escasa, estoy de acuerdo, esto es peor en términos de memoria. Aunque si los enteros se distribuyen aleatoriamente, comenzará a obtener duplicados mucho antes de lo que implica la intuición. Ver mathworld.wolfram.com/BirthdayProblem.html . Así que estoy bastante seguro de que esto será efectivo tan pronto como tenga incluso unos pocos GB de datos.
Andrew C
44
@AndrewC, ¿puedes explicar cómo tomará tiempo constante encontrar la mediana? Si he visto n tipos diferentes de enteros, en el peor de los casos, el último elemento puede ser la mediana. Esto hace que la mediana encuentre actividad O (n).
shshnk
@shshnk ¿No es n el número total de elementos que es >>> 2 ^ 35 en este caso?
VishAmdi
@shshnk Tienes razón en que sigue siendo lineal en la cantidad de enteros diferentes que has visto, como dijo VishAmdi, la suposición que estoy haciendo para esta solución es que n es la cantidad de números que has visto, lo cual es mucho mayor que 2 ^ 33. Si no ve tantos números, la solución maxheap es definitivamente mejor.
Andrew C
49

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 una secuencia de números arbitrariamente larga.

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 continua, 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 depósito y sondear el punto interesante.

Como 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 un consumo constante de tiempo y memoria.

Colm MacCárthaigh
fuente
por curiosidad, ¿por qué necesitas variación?
LazyCat
La secuencia podría devolver menos elementos de TAMAÑO, dejando el depósito medio vacío. Esto debe considerarse al calcular la mediana.
Alex
¿Hay alguna manera de hacer esto más rápido calculando la diferencia en lugar de la mediana? ¿Es la muestra eliminada y agregada y la mediana anterior suficiente información para eso?
inf3rno
30

La forma más eficiente de calcular el percentil de una secuencia que he encontrado es el algoritmo P²: Raj Jain, Imrich Chlamtac: El algoritmo P² para el cálculo dinámico de cuantiiles e histogramas 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 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 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 grabadores industriales. El algoritmo se extiende aún más al trazado del histograma. Se analiza la precisión del algoritmo.

Hellblazer
fuente
2
Count-Min Sketch es mejor que P ^ 2 en que también da error vinculado mientras que este último no.
sinoTrinity
1
Considere también la "Computación en línea eficiente en el espacio de resúmenes cuantiles" de Greenwald y Khanna, que también ofrece límites de error y tiene buenos requisitos de memoria.
Paul Chernoch
1
Además, para un enfoque probabilístico, vea esta publicación de blog: research.neustar.biz/2013/09/16/… y el documento al que hace referencia está aquí: arxiv.org/pdf/1407.1121v1.pdf Esto se llama "Frugal Streaming "
Paul Chernoch
27

Si queremos encontrar la mediana de los n elementos vistos más recientemente, este problema tiene una solución exacta que solo necesita guardar los n elementos vistos más recientemente en la memoria. Es rápido y escala bien.

Una lista de salto indexable admite la inserción, eliminación y búsqueda indexada O (ln n) de elementos arbitrarios mientras se mantiene el orden ordenado. Cuando se combina con una cola FIFO que rastrea la ené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 optimizada del generador con el código indexable de la lista de omisión incluido):

Raymond Hettinger
fuente
77
Sin embargo, si lo entiendo correctamente, esto solo le da una mediana de los últimos N elementos vistos, no todos los elementos hasta ese punto. Sin embargo, esto parece una solución realmente ingeniosa para esa operación.
Andrew C
16
Correcto. La respuesta suena como si fuera posible encontrar la mediana de todos los elementos simplemente manteniendo los últimos n elementos en la memoria; eso es imposible en general. El algoritmo solo encuentra la mediana de los últimos n elementos.
Hans-Peter Störr
8
El término "mediana de ejecución" se usa típicamente para referirse a la mediana de un subconjunto de datos. El OP se utiliza un término común de manera no estándar.
Rachel Hettinger
18

Una forma intuitiva de pensar en esto es que si tuviera un árbol de búsqueda binario completamente equilibrado, entonces la raíz sería el elemento mediano, ya que habría la misma cantidad 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 es tener la mediana y dos árboles binarios balanceados, uno para elementos menores que la mediana y otro para elementos mayores que la mediana. Los dos árboles deben mantenerse al 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 más de 1, eliminamos el elemento min del árbol derecho, lo convertimos en la nueva mediana y colocamos la mediana anterior en el árbol izquierdo. Del mismo modo para los más pequeños.

Irene Papakonstantinou
fuente
Cómo vas a hacer eso? "eliminamos el elemento mínimo del árbol correcto"
Hengameh
2
Me refería a árboles de búsqueda binarios, por lo que el elemento min queda completamente desde la raíz.
Irene Papakonstantinou
7

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. Suponga 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. Coloca los números en una matriz y, para cada consulta, ejecuta el algoritmo de selección lineal (usando el pivote de clasificación rápida, por ejemplo). Ahora tiene un algoritmo con tiempo de ejecución O (KN).

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

Pedro es
fuente
1
En el ejemplo del montón, la búsqueda es tiempo constante, por lo que creo que debería ser O (N log N + K), pero su punto aún se mantiene.
Andrew C
Sí, buen punto, editará esto. Tienes razón N log N sigue siendo el término principal.
Peteris
-2

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

Invariante: después de leer las 2*nentradas, el montón mínimo contiene la nmayor de ellas.

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

Entonces, cuando 2nse han leído las entradas, el min 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 media y para manejar consultas después de un número impar de entradas.

Darius Bacon
fuente
1
No funciona: puedes soltar cosas que luego resultan estar cerca de la cima. Por ejemplo, pruebe su algoritmo con los números del 1 al 100, pero en orden inverso: 100, 99, ..., 1.
zellyn
Gracias zellyn. Es tonto de mi parte convencerme de que el invariante se restableció.
Darius Bacon