En informática , el problema de valores menores más cercano es la siguiente tarea: para cada posición en una secuencia de números, busque entre las posiciones anteriores la última posición que contenga un valor menor. Este problema se puede resolver de manera eficiente tanto mediante algoritmos paralelos como no paralelos: Berkman, Schieber & Vishkin (1993) , quienes identificaron por primera vez el procedimiento como una subrutina útil para otros programas paralelos, desarrollaron algoritmos eficientes para resolverlo en la máquina de acceso aleatorio paralelo modelo; también se puede resolver en tiempo lineal en una computadora no paralela usando una pila-Algoritmo basado en Investigadores posteriores han estudiado algoritmos para resolverlo en otros modelos de computación paralela.
Ejemplo
Suponga que la entrada es la secuencia binaria de van der Corput
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.
El primer elemento de la secuencia (0) no tiene valor previo. El valor menor más cercano (solo) anterior a 8 y a 4 es 0. Los tres valores anteriores a 12 son menores, pero el más cercano es 4. Continuando de la misma manera, los valores menores anteriores más cercanos para esta secuencia (indicando la inexistencia de un valor anterior menor por un guión) son
- -, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.
En la mayoría de las aplicaciones, se deben calcular las posiciones de los valores más pequeños más cercanos, y no los valores en sí mismos, y en muchas aplicaciones se debe calcular el mismo cálculo para la inversión de la secuencia a fin de encontrar el siguiente valor más pequeño que esté más cercano en la secuencia.
Aplicaciones
Berkman, Schieber y Vishkin (1993) mencionan muchos otros problemas que pueden resolverse eficientemente en paralelo utilizando un cálculo de valores más pequeños más cercano. Entre ellos, se incluyen los siguientes:
- Fusionar algoritmos , calculando el paso de fusión de un tipo de fusión . La entrada a estos algoritmos consta de dos matrices ordenadas de números; la salida deseada es el mismo conjunto de números en una sola matriz ordenada. Si uno concatena las dos matrices ordenadas, la primera en orden ascendente y la segunda en orden descendente, entonces el predecesor de cada valor en la salida es su valor más pequeño anterior más cercano o su valor más pequeño siguiente más cercano (cualquiera de los dos es mayor) , y la posición de cada valor en la matriz de salida ordenada se puede calcular fácilmente a partir de las posiciones de estos dos valores más pequeños más cercanos.
- Construcción de árboles cartesianos . Un árbol cartesiano es una estructura de datos introducida por Vuillemin (1980) y más estudiada por Gabow, Bentley y Tarjan (1984) para aplicaciones de búsqueda de rango . Los árboles cartesianos también surgen en la definición del treap y las estructuras de datos del árbol de búsqueda binaria aleatoria para la búsqueda binaria . El árbol cartesiano de una secuencia de valores tiene un nodo para cada valor. La raíz del árbol es el valor mínimo de la secuencia; para cada otro nodo, el padre del nodo es su valor más pequeño anterior más cercano o su valor más pequeño siguiente más cercano (cualquiera de los dos que exista y sea mayor). Por lo tanto, los árboles cartesianos se pueden construir en tiempo lineal en base a un algoritmo de valores más pequeños más cercano.
- Paréntesis coincidentes . Si se proporciona una secuencia de caracteres de paréntesis abiertos y cerrados como entrada, junto con la profundidad de anidamiento de cada paréntesis, entonces la coincidencia con cada paréntesis abierto es el siguiente paréntesis cerrado sin mayor profundidad de anidación, por lo que se puede encontrar por un todo más cercano cálculo de valores más pequeños que rompe los lazos a favor de paréntesis cerrados. Si no se dan las profundidades de anidación, se pueden calcular utilizando un cálculo de suma de prefijo .
También se pueden aplicar técnicas similares a problemas de triangulación de polígonos , construcción de cascos convexos (paralelizando el algoritmo secuencial de cascos convexos de exploración de Graham ), reconstrucción de árboles a partir de los ordenamientos transversales de dos de los árboles y construcción de cuatro árboles. [1]
Algoritmo secuencial
En una computadora secuencial, es sencillo calcular todos los valores más pequeños más cercanos usando una estructura de datos de pila : uno procesa los valores en orden secuencial, usando la pila para mantener una subsecuencia de los valores que se han procesado hasta ahora y son más pequeños que los posteriores. valor que ya ha sido procesado. En pseudocódigo , el algoritmo es el siguiente.
S = nueva estructura de datos de pila vacía para x en la secuencia de entrada do mientras que S no está vacío y el elemento superior de S es mayor o igual que x do pop S si S está vacío entonces x no tiene un valor menor anterior demás el valor más pequeño más cercano ax es el elemento superior de S empuja x sobre S
A pesar de tener una estructura de bucle anidado, el tiempo de ejecución de este algoritmo es lineal, porque cada iteración del bucle interno elimina un elemento que se había agregado en alguna iteración anterior del bucle externo. Está estrechamente relacionado con un algoritmo de Knuth para ordenar con una pila (para entradas que se pueden ordenar de esta manera). [2]
Un algoritmo secuencial de tiempo lineal aún más simple ( Barbay, Fischer y Navarro (2012) , Lema 1) ni siquiera necesita una pila; asume que la secuencia de entrada se da como una matriz A [1, n], y almacena el índice j del valor anterior más pequeño del i-ésimo valor A [i] en P [i]. Suponemos un mínimo general artificial en A [0]:
para i de 1 a n: j = i-1 mientras que A [j]> = A [i]: j = P [j] P [i] = j
Algoritmos paralelos
Berkman, Schieber y Vishkin (1993) mostraron cómo resolver el problema de valores más pequeños más cercanos de manera eficiente en una máquina de acceso aleatorio paralelo de lectura simultánea de escritura simultánea . Para una secuencia de n valores, almacenados como una matriz , muestran que el problema puede resolverse en el tiempo O (log log n ) utilizando una cantidad lineal de trabajo total. Para secuencias donde todos los valores son números enteros en el intervalo [1, s ], Berkman, Matias y Ragde (1998) mejoraron este límite a O (log log log s ); también demostraron que, para valores suficientemente grandes de s , el límite de tiempo doblemente logarítmico anterior es lo mejor que se puede lograr para el problema. Desde este trabajo, también se han desarrollado algoritmos paralelos para el problema de valores más pequeños más cercanos en otros modelos de computación paralela, incluyendo computadoras paralelas con una red de comunicaciones estructurada en hipercubo , [3] y el modelo paralelo síncrono masivo . [4]
Notas
- ^ Berna, Eppstein y Teng (1999) .
- ^ Knuth, Donald (1968), "Vol. 1: Algoritmos fundamentales", El arte de la programación informática , Lectura, Mass .: Addison-Wesley.
- ^ Kravets y Plaxton (1996) .
- ^ Él y Huang (2001) .
Referencias
- Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), "Árboles LRM: índices comprimidos, ordenación adaptativa y permutaciones comprimidas", Informática teórica , 459 : 26–41, arXiv : 1009.5863 , doi : 10.1016 / j.tcs.2012.08.010.
- Berkman, Omer; Matias, Yossi; Ragde, Prabhakar (1998), "Límites superior e inferior paralelos triplemente logarítmicos para mínimos y rangos mínimos en dominios pequeños", Journal of Algorithms , 28 (2): 197-215, doi : 10.1006 / jagm.1997.0905.
- Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993), "Algoritmos paralelos doblemente logarítmicos óptimos basados en encontrar todos los valores más pequeños más cercanos", Journal of Algorithms , 14 (3): 344–370, doi : 10.1006 / jagm.1993.1018.
- Berna, Marshall; Eppstein, David ; Teng, Shang-Hua (1999), "Construcción paralela de quadtrees y triangulaciones de calidad" (PDF) , International Journal of Computational Geometry & Applications , World Scientific Publishing Company, 9 (6): 517–532, doi : 10.1142 / S0218195999000303.
- Gabow, Harold N .; Bentley, Jon Louis ; Tarjan, Robert E. (1984), "Escalado y técnicas relacionadas para problemas de geometría", STOC '84: Proc. 16 ° ACM Symp. Theory of Computing , Nueva York, NY, EE. UU.: ACM, págs. 135–143, doi : 10.1145 / 800057.808675 , ISBN 0-89791-133-4.
- Él, Xin; Huang, Chun-Hsi (2001), "Algoritmo BSP de comunicación eficiente para todos los valores más pequeños más cercanos", Journal of Parallel and Distributed Computing , 61 (10): 1425–1438, doi : 10.1006 / jpdc.2001.1741.
- Kravets, D .; Plaxton, CG (1996), "Todos los valores más pequeños más cercanos en el hipercubo", IEEE Trans. Sistemas paralelos y distribuidos , 7 (5): 456–462, doi : 10.1109 / 71.503770.
- Vuillemin, Jean (1980), "Una mirada unificadora a las estructuras de datos", Commun. ACM , Nueva York, NY, EE. UU .: ACM, 23 (4): 229–239, doi : 10.1145 / 358841.358852.