Valores menores más cercanos

En Ciencias de la Computación, el problema valores menores más cercanos es el siguiente: para cada posición en una secuencia no ordenada de números, buscar entre las posiciones anteriores la última posición que contiene un valor menor. Este problema se puede resolver de manera eficiente, tanto por medio de algoritmos paralelos como no paralelos:Berkman, Schieber y Vishkin (1993), quienes por primera vez identificaron la utilidad de este procedimiento para otros programas paralelos, desarrollaron algoritmos eficientes para resolverlo en un modelo de máquina de acceso aleatorio paralelo. Este problema también puede ser resuelto en tiempo lineal en una computadora no paralela usando un algoritmo basado en pila. Posteriormente otros investigadores han estudiado algoritmos para resolverlo en otros modelos de computación paralela.

Ejemplo

Supongamos que la entrada es la secuencia van der Corput binaria.

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 ningún valor previo. El menor (y único) valor más cercano anterior a 8 y a 4 es 0. Los tres valores anteriores a 12 son menores, pero el más cercano es el 4. De esta forma, los valores menores más cercanos para esta secuencia (indicando la no existencia de un valor previo más pequeño por un guion) son

—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.

En la mayoría de las aplicaciones, las posiciones de los valores menores más cercanos, y no los propios valores, deben calcularse, y en muchas aplicaciones el mismo cálculo debe efectuarse al inverso de la secuencia con el fin de encontrar el siguiente valor más pequeño que es más cercano en la secuencia.

Aplicaciones

Berkman, Schieber y Vishkin (1993) mencionan muchos otros problemas que pueden ser resueltos de manera eficiente en paralelo usando el cálculo de los valores menores más cercanos. Entre ellos, se incluyen los siguientes:

• Algoritmos de mezcla, cálculo de la etapa de fusión de una ordenación por mezcla. La entrada a estos algoritmos consiste en dos arreglos ordenados de números, el resultado deseado es el mismo conjunto de números en un solo arreglo ordenado. Si se concatenan los dos arreglos ordenados, el primero en orden ascendente y el segundo en orden descendente, entonces, el predecesor de cada valor en la salida es el valor menor anterior más cercano o el valor menor posterior más cercano (según cuál de los dos sea más grande), y la posición de cada valor en el arreglo de salida ordenado se puede calcular fácilmente a partir de las posiciones de estos dos valores menores más cercanos.
• Construcción de árboles cartesianos. Un árbol cartesiano es una estructura de datos introducida por Vuillemin (1980) y más tarde estudiada por Gabow, Bentley y Tarjan (1984) para aplicaciones de búsqueda de rango. Los árboles cartesianos también surgen en la definición de treap y estructuras de datos de árboles binarios de búsqueda aleatorios para 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 cualquier otro nodo, el padre del nodo es o bien su valor menor previo más cercano o su menor valor siguiente más cercano (entre los dos valores aquel que existe y es mayor). Por lo tanto, los árboles cartesianos se pueden construir en tiempo lineal basado en el algoritmo de valores menores más cercanos.
• Coincidencia de paréntesis. Si una secuencia de caracteres de paréntesis abiertos y cerrados se da como entrada, junto con la profundidad de anidamiento de cada paréntesis, entonces el coincidente de cada paréntesis abierto es el paréntesis cerrado a la derecha más cercano que tenga profundidad de anidamiento menor, por lo que puede encontrarse mediante el cálculo de valores menores más cercanos. Si no se dan las profundidades de anidamiento, se pueden calcular utilizando el cálculo de suma de prefijo. La siguiente secuencia de paréntesis junto con la profundidad de anidamiento de cada uno, ilustra lo anterior:

     ( ( ) ( ( ( ) ( ) ) ) )

     1 2 1 2 3 4 3 4 3 2 1 0

Técnicas similares también pueden aplicarse a problemas de triangulación de polígonos, la construcción de envolventes convexas (paralelización del algoritmo secuencial deGraham para envolventes convexas), la reconstrucción de árboles a partir de dos de los ordenamientos transversales de árboles, y la construcción del quadtree.​

Algoritmo secuencial

En una computadora secuencial, es sencillo el cálculo de los valores menores más cercanos utilizando una pila: uno procesa los valores en orden secuencial, usando la pila para mantener una subsecuencia de los valores que han sido procesados hasta el momento y que son menores que cualquier valor anteriormente procesado. En pseudocódigo, el algoritmo es el siguiente.

S = new empty stack data structure
for x in the input sequence:
    while S is nonempty and the top element of S is greater than or equal to x:
        pop S
    if S is empty:
        x has no preceding smaller value
    else:
        the nearest smaller value to x is the top element of S
    push x onto S

A pesar de tener una estructura de ciclo anidado, el tiempo de ejecución de este algoritmo es lineal, porque cada iteración del ciclo interno elimina un elemento que se había añadido en alguna iteración anterior del ciclo exterior. Está estrechamente relacionado con un algoritmo de Knuth para ordenamiento con una pila (para entradas que puedan ordenarse de esta manera).​

Un algoritmo secuencial aún más simple (Barbay, Fischer y Navarro (2012), Lemma 1) ni siquiera necesita una pila, sino que asume que la secuencia de entrada se da como un arreglo A [1, n], y almacena el valor menor precedente del valor i-ésimo A[i] en P [i]. Asumimos un mínimo global artificial en A [0]:

for i from 1 to n:
    set j to i-1
    while A[j] > A[i]:
        set j to P[j]
    set P[i] to j

Algoritmos paralelos

Berkman, Schieber y Vishkin (1993) mostraron la forma de resolver el problema de los valores menores más cercanos de manera eficiente en una máquina de acceso aleatorio. Para una secuencia de n valores, almacenados en un arreglo, muestran que el problema puede ser resuelto en tiempo O(log log n) usando 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 esta cota a O(log log log s); también mostraron que, para valores suficientemente grandes de s, O(log log n) es la mejor cota que se puede lograr para el problema. Desde entonces, algoritmos paralelos para este problema se han desarrollado en otros modelos de computación paralela, incluyendo computadoras paralelas con una red de comunicaciones estructurada en forma de hipercubo,​ y el modelo paralelo sincrónico.​

Referencias

• Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), «LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations», Theoretical Computer Science 459: 26-41, doi:10.1016/j.tcs.2012.08.010 ..
• Berkman, Omer; Matias, Yossi; Ragde, Prabhakar (1998), «Triply-logarithmic parallel upper and lower bounds for minimum and range minima over small domains», Journal of Algorithms 28 (2): 197-215, doi:10.1006/jagm.1997.0905 ..
• Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), «Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values», Journal of Algorithms 14 (3): 344-370, doi:10.1006/jagm.1993.1018 ..
• Bern, Marshall; Eppstein, David; Teng, Shang-Hua (1999), «Parallel construction of quadtrees and quality triangulations», International Journal of Computational Geometry & Applications (World Scientic Publishing Company) 9 (6), doi:10.1142/S0218195999000303 ..
• Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), «Scaling and related techniques for geometry problems», STOC '84: Proc. 16th ACM Symp. Theory of Computing, New York, NY, USA: ACM, pp. 135-143, ISBN 0-89791-133-4, doi:10.1145/800057.808675 ..
• He, Xin; Huang, Chun-Hsi (2001), «Communication efficient BSP algorithm for all nearest smaller values», Journal of Parallel and Distributed Computing 61 (10): 1425-1438, doi:10.1006/jpdc.2001.1741 ..
• Kravets, D.; Plaxton, C. G. (1996), «All nearest smaller values on the hypercube», IEEE Trans. Parallel and Distributed Systems 7 (5): 456-462, doi:10.1109/71.503770 ..
• Vuillemin, Jean (1980), «A unifying look at data structures», Commun. ACM (New York, NY, USA: ACM) 23 (4): 229-239, doi:10.1145/358841.358852 ..

• Datos: Q4730032