Algoritmo no trivial para calcular una mediana de ventana deslizante

25

Necesito calcular la mediana de carrera:

  • Entrada: n , k , vector .(x1,x2,,xn)

  • Salida: vector , donde es la mediana de .(y1,y2,,ynk+1)yi(Xyo,Xyo+1,...,Xyo+k-1)

(No hacer trampa con aproximaciones; me gustaría tener soluciones exactas. Los elementos Xyo son enteros grandes).

Hay un algoritmo trivial que mantiene un árbol de búsqueda de tamaño ; el tiempo total de ejecución es . (Aquí, un "árbol de búsqueda" se refiere a una estructura de datos eficiente que admite inserciones, eliminaciones y consultas medianas en tiempo logarítmico).kO(norteIniciar sesiónk)

Sin embargo, esto me parece un poco estúpido. Aprenderemos efectivamente todas las estadísticas de pedidos dentro de todas las ventanas de tamaño , no solo las medianas. Además, esto no es demasiado atractivo en la práctica, especialmente si es grande (los árboles de búsqueda grandes tienden a ser lentos, la sobrecarga en el consumo de memoria no es trivial, la eficiencia de la memoria caché a menudo es pobre, etc.).kk

¿Podemos hacer algo sustancialmente mejor?

¿Hay límites inferiores (por ejemplo, ¿es el algoritmo trivial asintóticamente óptimo para el modelo de comparación)?


Editar: David Eppstein dio un buen límite inferior para el modelo de comparación. Me pregunto si, sin embargo, es posible hacer algo un poco más inteligente que el algoritmo trivial.

Por ejemplo, podríamos hacer algo en este sentido: dividir el vector de entrada en partes de tamaño ; ordenar cada parte (haciendo un seguimiento de las posiciones originales de cada elemento); y luego use el vector ordenado por partes para encontrar las medianas en ejecución de manera eficiente sin ninguna estructura de datos auxiliar. Por supuesto, esto seguiría siendo , pero en la práctica la ordenación de matrices tiende a ser mucho más rápida que el mantenimiento de los árboles de búsqueda.kO(norteIniciar sesiónk)


Edición 2: Saeed quería ver algunas razones por las que creo que la ordenación es más rápida que las operaciones del árbol de búsqueda. Aquí hay puntos de referencia muy rápidos, para , :k=107 7norte=108

  • ≈ 8s: ordenando vectores con elementos cada unonorte/ /kk
  • ≈ 10s: ordenando un vector con elementosnorte
  • ≈80: inserciones y eliminaciones en una tabla hash de tamaño knortek
  • ≈ 390s: inserciones y eliminaciones en un árbol de búsqueda equilibrado de tamaño knortek

La tabla hash está ahí solo para comparar; no es de uso directo en esta aplicación.

En resumen, tenemos casi un factor 50 de diferencia en el rendimiento de la ordenación frente a las operaciones de árbol de búsqueda equilibrado. Y las cosas empeoran mucho si aumentamos .k

(Detalles técnicos: Datos = enteros aleatorios de 32 bits. Computadora = una computadora portátil moderna típica. El código de prueba se escribió en C ++, utilizando las rutinas de biblioteca estándar (std :: sort) y las estructuras de datos (std :: multiset, std :: unsorted_multiset). Utilicé dos compiladores C ++ diferentes (GCC y Clang), y dos implementaciones diferentes de la biblioteca estándar (libstdc ++ y libc ++). Tradicionalmente, std :: multiset se ha implementado como un árbol rojo-negro altamente optimizado).

Jukka Suomela
fuente
1
No creo que puedas mejorar . La razón es que, si nos fijamos en una ventana x t , . . . , x t + k - 1 , nunca puedes descartar ninguno de los números x t + knortelosolkXt,...,Xt+k-1de ser medianas de la ventana futura. Esto significa que en cualquier momento debe mantener al menoskXt+k2,...,Xt+k-1 enteros en una estructura de datos, y no parece actualizarse en menos de un tiempo de registro. k2
RB
Su algoritmo trivial para mí parece ser no O ( n log k ) , ¿estoy entendiendo mal algo? Y creo que debido a esto tienes problemas con la gran k , de lo contrario el factor logarítmico no es nada en aplicaciones prácticas, tampoco hay una gran constante oculta en este algoritmo. O((norte-k)kIniciar sesiónk)O(norteIniciar sesiónk)k
Saeed
@Saeed: en el algoritmo trivial, procesas los elementos uno por uno; en el paso , agrega x i al árbol de búsqueda y (si i > k ) también elimina x i - k del árbol de búsqueda. Estos son n pasos, cada uno de los cuales toma tiempo O ( log k ) . ixii>kxiknO(logk)
Jukka Suomela
¿Quiere decir que tiene un árbol de búsqueda equilibrado, no un árbol de búsqueda casual?
Saeed
1
@Saeed: Tenga en cuenta que en mis puntos de referencia ni siquiera intenté encontrar medianas. Acabo de hacer inserciones y n eliminaciones en un árbol de búsqueda de tamaño k , y se garantiza que estas operaciones tomarán tiempo O ( log k ) . Solo necesita aceptar que las operaciones del árbol de búsqueda son muy lentas en la práctica, en comparación con la ordenación. Verá esto fácilmente si intenta escribir un algoritmo de clasificación que funcione agregando elementos a un árbol de búsqueda equilibrado; ciertamente funciona en tiempo O ( n log n ) , pero será ridículamente lento en la práctica y también desperdiciará mucho de la memoria nortenortekO(Iniciar sesiónk)O(norteIniciar sesiónnorte)
Jukka Suomela

Respuestas:

32

Aquí hay un límite inferior de la clasificación. Dado un conjunto de entrada de longitud n que se ordenará, cree una entrada para su problema medio de ejecución que consiste en n - 1 copias de un número menor que el mínimo de S , luego S en sí, luego n - 1 copias de un número mayor que el máximo de S , y establezca k = 2 n - 1 . Las medianas de funcionamiento de esta entrada son el mismo que el orden de clasificación de S .Snortenorte-1SSnorte-1Sk=2norte-1S

Entonces, en un modelo de cálculo de comparación, se requiere el tiempo . Posiblemente, si sus entradas son enteras y utiliza algoritmos de clasificación de enteros, puede hacerlo mejor.Ω(norteIniciar sesiónnorte)

David Eppstein
fuente
66
Esta respuesta realmente me hace preguntarme si lo contrario también es válido: dado un algoritmo de clasificación eficiente, ¿obtenemos un algoritmo mediano eficiente? (Por ejemplo, ¿un algoritmo de clasificación de números enteros eficiente implica un algoritmo de mediana de ejecución eficiente para los números enteros? ¿O un algoritmo de clasificación eficiente de E / S proporciona un algoritmo de mediana de ejecución eficiente de E / S?)
Jukka Suomela
1
Una vez más, muchas gracias por su respuesta, ¡realmente me puso en el camino correcto y me inspiró para el algoritmo de filtro mediano basado en la clasificación! Al final pude encontrar un artículo de 1991 que presentaba básicamente el mismo argumento que el que da aquí, y Pat Morin le dio un puntero a otro artículo relevante de 2005; ver referencias [6] y [9] aquí .
Jukka Suomela
9

Editar: este algoritmo ahora se presenta aquí: http://arxiv.org/abs/1406.1717


Sí, para resolver este problema es suficiente realizar las siguientes operaciones:

  • Ordenar vectores, cada uno con k elementos.norte/ /kk
  • Hacer postprocesamiento en tiempo lineal.

A grandes rasgos, la idea es esta:

  • Considere dos bloques de entrada adyacentes, y b , ambos con k elementos; dejar que los elementos sean un 1 , un 2 , . . . , Un k y b 1 , b 2 , . . . , b k en el orden de aparición en el vector de entrada x .unasikuna1,una2,...,unaksi1,si2,...,sikX
  • Ordena estos bloques y aprende el rango de cada elemento dentro del bloque.
  • Aumentar los vectores y b con punteros predecesor / sucesor de modo que siguiendo las cadenas de puntero que puede atravesar los elementos en un orden creciente. De esta manera, hemos construido listas doblemente vinculadas a y b .unasiunasi
  • Uno por uno, borrar todos los elementos de la lista enlazada , en el orden inverso de aparición b k , b k - 1 , . . . , b 1 . Siempre que eliminemos un elemento, recuerde cuál fue su sucesor y predecesor en el momento de la eliminación .sisik,sik-1,...,si1
  • Ahora mantenga "punteros medianos" y q que apuntan a las listas a ' y b ' , respectivamente. Inicialice p en el punto medio de a e inicialice q en la cola de la lista vacía b .pagsqunasipagsunaqsi
  • Para cada :yo

    • Elimine de la lista a (este es el tiempo O ( 1 ) , simplemente elimine de la lista vinculada). Compare una i con el elemento señalado por p para ver si eliminamos antes o después de p .unayounaO(1)unayopagspags
    • Puso volver a la lista b ' en su posición original (esto es O ( 1 ) tiempo, hemos memorizado el predecesor y sucesor de B i ). Compare b i con el elemento señalado por q para ver si agregamos el elemento antes o después de q .siyosiO(1)siyosiyoqq
    • Actualice los punteros y q para que la mediana de la lista unida a b esté en p o en q . (Este es el momento O ( 1 ) , solo siga uno o dos pasos en las listas vinculadas para arreglar todo. Realizaremos un seguimiento de cuántos elementos hay antes / después de p y q en cada lista, y mantendremos la invariante de que ambos p y q punto a elementos que son tan cerca de la mediana como sea posible.)pagsqunasipagsqO(1)pagsqpagsq

Las listas vinculadas son solo matrices de elementos de índices, por lo que son livianas (excepto que la localidad de acceso a la memoria es deficiente).k


Aquí hay una implementación de muestra y puntos de referencia:

Aquí hay una gráfica de tiempos de ejecución (para ):norte2106 6

  • Azul = clasificación + postprocesamiento, .O(norteIniciar sesiónk)
  • Verde = mantener dos montones, , implementación desde https://github.com/craffel/median-filterO(norteIniciar sesiónk)
  • Rojo = mantener dos árboles de búsqueda, .O(norteIniciar sesiónk)
  • Negro = mantener un vector ordenado, .O(nortek)
  • Eje X = tamaño de la ventana ( ).k/ /2
  • Eje Y = tiempo de ejecución en segundos.
  • Datos = enteros de 32 bits y enteros aleatorios de 64 bits, de varias distribuciones.

tiempos de funcionamiento

Jukka Suomela
fuente
3

Dado el límite de David, es poco probable que pueda hacerlo mejor en el peor de los casos, pero hay mejores algoritmos sensibles a la salida. Específicamente, si en el número de medianas en el resultado, podemos resolver el problema en el tiempo O ( n log m + m log n ) .metroO(norteIniciar sesiónmetro+metroIniciar sesiónnorte)

Para hacer esto, reemplace el árbol binario balanceado con un árbol binario balanceado que consista solo de aquellos elementos que fueron medianas en el pasado, más dos montones de Fibonacci entre cada par de medianas anteriores (una para cada dirección), más recuentos para que podamos localice qué montón de Fibonacci contiene un elemento particular en el orden. No te molestes en eliminar elementos. Cuando insertamos un nuevo elemento, podemos actualizar nuestra estructura de datos en tiempo . Si los nuevos recuentos indican que la mediana está en uno de los montones de Fibonacci, se necesita una O adicional ( log n ) para extraer la nueva mediana. Este O ( log n )O(Iniciar sesiónmetro)O(Iniciar sesiónnorte)O(Iniciar sesiónnorte) la carga se produce solo una vez por mediana.

Si hubiera una forma limpia de eliminar elementos sin dañar la agradable complejidad del montón de Fibonacci, llegaríamos a , pero no estoy seguro de si esto es posible.O(norteIniciar sesiónmetro+metroIniciar sesiónk)

Geoffrey Irving
fuente
Vaya, esto no funciona como está escrito, ya que si no elimina elementos, los recuentos no reflejarán la nueva ventana. No estoy seguro de si se puede solucionar, pero dejaré la respuesta en caso de que haya alguna manera.
Geoffrey Irving
O(norteIniciar sesiónmetro)
nota al margen: la pregunta no está clara, la estructura de datos subyacente no está definida, solo sabemos algo muy vago. ¿Cómo quieres mejorar algo que no sabes de qué se trata? ¿Cómo quieres comparar tu enfoque?
Saeed
1
Pido disculpas por el trabajo incompleto. He hecho la pregunta concreta necesaria para corregir esta respuesta aquí: cstheory.stackexchange.com/questions/21778/… . Si crees que es apropiado, puedo eliminar esta respuesta hasta que se resuelva la pregunta secundaria.
Geoffrey Irving