Algoritmo no trivial para calcular una mediana de ventana deslizante

Necesito calcular la mediana de carrera:

Entrada: $n$ , $k$ , vector . $(x_1, x_2, \dotsc, x_n)$
Salida: vector , donde es la mediana de . $(y_1, y_2, \dotsc, y_{n-k+1})$ $y_i$ $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$

(No hacer trampa con aproximaciones; me gustaría tener soluciones exactas. Los elementos $x_i$ 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). $k$ $O(n \log k)$

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

¿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. $k$ $O(n \log k)$

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 = 10^7$ $n = 10^8$

≈ 8s: ordenando vectores con elementos cada uno $n/k$ $k$
≈ 10s: ordenando un vector con elementos $n$
≈80: inserciones y eliminaciones en una tabla hash de tamaño $n$ $k$
≈ 390s: inserciones y eliminaciones en un árbol de búsqueda equilibrado de tamaño $n$ $k$

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

ds.algorithms ds.data-structures lower-bounds Jukka Suomela
fuente

No creo que puedas mejorar

. La razón es que, si nos fijamos en una ventana

, nunca puedes descartar ninguno de los números

n l o g k

$nlogk$

x_{t}, . . ., x_{t + k - 1}

$x_t,...,x_{t+k-1}$

de ser medianas de la ventana futura. Esto significa que en cualquier momento debe mantener al menos

x_{t + \frac{k}{2}}, . . ., x_{t + k - 1}

$x_{t+\frac{k}{2}},...,x_{t+k-1}$

enteros en una estructura de datos, y no parece actualizarse en menos de un tiempo de registro.

\frac{k}{2}

$\frac{k}{2}$

Su algoritmo trivial para mí parece ser

, ¿estoy entendiendo mal algo? Y creo que debido a esto tienes problemas con la gran

, de lo contrario el factor logarítmico no es nada en aplicaciones prácticas, tampoco hay una gran constante oculta en este algoritmo.

O ((n - k) \cdot k \cdot \log k)

$O((n-k)\cdot k \cdot \log k)$

O (n \log k)

$O(n \log k)$

k

$k$

Saeed

@Saeed: en el algoritmo trivial, procesas los elementos uno por uno; en el paso

, agrega

al árbol de búsqueda y (si

) también elimina

del árbol de búsqueda. Estos son

pasos, cada uno de los cuales toma tiempo

i

$i$

x_{i}

$x_i$

i > k

$i > k$

x_{i - k}

$x_{i-k}$

n

$n$

O (\log k)

$O(\log k)$

Jukka Suomela

¿Quiere decir que tiene un árbol de búsqueda equilibrado, no un árbol de búsqueda casual?

Saeed

@Saeed: Tenga en cuenta que en mis puntos de referencia ni siquiera intenté encontrar medianas. Acabo de hacer

inserciones y

eliminaciones en un árbol de búsqueda de tamaño

, y se garantiza que estas operaciones tomarán tiempo

. 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

, pero será ridículamente lento en la práctica y también desperdiciará mucho de la memoria

n

$n$

n

$n$

k

$k$

O (\log k)

$O(\log k)$

O (n \log n)

$O(n \log n)$

Jukka Suomela

Respuestas:

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

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. $\Omega(n\log n)$

David Eppstein
fuente

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

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

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 elementos. $n/k$ $k$
Hacer postprocesamiento en tiempo lineal.

A grandes rasgos, la idea es esta:

Considere dos bloques de entrada adyacentes, y , ambos con elementos; dejar que los elementos sean y en el orden de aparición en el vector de entrada . $a$ $b$ $k$ $a_1, a_2, ..., a_k$ $b_1, b_2, ..., b_k$ $x$
Ordena estos bloques y aprende el rango de cada elemento dentro del bloque.
Aumentar los vectores y 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 y . $a$ $b$ $a'$ $b'$
Uno por uno, borrar todos los elementos de la lista enlazada , en el orden inverso de aparición . Siempre que eliminemos un elemento, recuerde cuál fue su sucesor y predecesor en el momento de la eliminación . $b'$ $b_k, b_{k-1}, ..., b_1$
Ahora mantenga "punteros medianos" y que apuntan a las listas y , respectivamente. Inicialice en el punto medio de e inicialice en la cola de la lista vacía . $p$ $q$ $a'$ $b'$ $p$ $a'$ $q$ $b'$
Para cada : $i$
- Elimine de la lista (este es el tiempo , simplemente elimine de la lista vinculada). Compare con el elemento señalado por para ver si eliminamos antes o después de . $a_i$ $a'$ $O(1)$ $a_i$ $p$ $p$
- Puso volver a la lista en su posición original (esto es tiempo, hemos memorizado el predecesor y sucesor de ). Compare con el elemento señalado por para ver si agregamos el elemento antes o después de . $b_i$ $b'$ $O(1)$ $b_i$ $b_i$ $q$ $q$
- Actualice los punteros y para que la mediana de la lista unida esté en o en . (Este es el momento , 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 y en cada lista, y mantendremos la invariante de que ambos y punto a elementos que son tan cerca de la mediana como sea posible.) $p$ $q$ $a' \cup b'$ $p$ $q$ $O(1)$ $p$ $q$ $p$ $q$

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:

https://github.com/suomela/median-filter

Aquí hay una gráfica de tiempos de ejecución (para ): $n \approx 2\cdot 10^6$

Azul = clasificación + postprocesamiento, . $O(n \log k)$
Verde = mantener dos montones, , implementación desde https://github.com/craffel/median-filter $O(n \log k)$
Rojo = mantener dos árboles de búsqueda, . $O(n \log k)$
Negro = mantener un vector ordenado, . $O(n k)$
Eje X = tamaño de la ventana ( ). $\approx 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

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 . $m$ $O(n \log m + m \log n)$

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 adicional para extraer la nueva mediana. Este $O(\log m)$ $O(\log n)$ $O(\log n)$ 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(n \log m + m \log k)$

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 (n \log m)

$O(n \log m)$

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

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