Todos los valores más pequeños más cercanos

En informática , el problema de todos los valores más pequeños más cercanos es la siguiente tarea: para cada posición en una secuencia de números, buscar entre las posiciones anteriores la última posición que contenga un valor más pequeño. Este problema se puede resolver de manera eficiente tanto mediante algoritmos paralelos como no paralelos: Berkman, Schieber y Vishkin (1993), quienes identificaron por primera vez el procedimiento como una subrutina útil para otros programas paralelos, desarrollaron algoritmos eficientes para resolverlo en el modelo de máquina de acceso aleatorio paralelo ; también se puede resolver en tiempo lineal en una computadora no paralela utilizando un algoritmo basado en pila . Investigadores posteriores han estudiado algoritmos para resolverlo en otros modelos de computación paralela.

Supongamos 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 ningún valor previo. El valor más cercano (único) más pequeño anterior a 8 y a 4 es 0. Los tres valores anteriores a 12 son más pequeños, pero el más cercano es 4. Continuando de la misma manera, los valores más cercanos anteriores más pequeños para esta secuencia (indicando la inexistencia de un valor anterior más pequeño mediante 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í, y en muchas aplicaciones se debe realizar 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 cerca en la secuencia.

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 cercanos. Entre ellos, se incluyen los siguientes:

• Algoritmos de fusión , que calculan el paso de fusión de una ordenación por fusión . La entrada de estos algoritmos consiste en dos matrices ordenadas de números; la salida deseada es el mismo conjunto de números en una única matriz ordenada. Si se concatenan 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 anterior más pequeño más cercano o su valor siguiente más pequeño más cercano (el que sea más grande de los dos), 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 estudiada más a fondo por Gabow, Bentley y Tarjan (1984) para aplicaciones de búsqueda de rangos . Los árboles cartesianos también surgen en la definición de las estructuras de datos treap y de árboles de búsqueda binaria aleatorizados para búsquedas binarias . 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 nodo, el padre del nodo es su valor anterior más pequeño más cercano o su valor siguiente más pequeño más cercano (el que exista de los dos y sea mayor). Por lo tanto, los árboles cartesianos se pueden construir en tiempo lineal basándose en un algoritmo de todos los valores más pequeños más cercanos.
• Paréntesis coincidentes . Si se proporciona como entrada una secuencia de caracteres de paréntesis de apertura y cierre, junto con la profundidad de anidamiento de cada paréntesis, entonces la coincidencia con cada paréntesis de apertura es el siguiente paréntesis de cierre sin mayor profundidad de anidamiento, por lo que se puede encontrar mediante un cálculo de todos los valores más pequeños más cercanos que deshace los empates a favor de los paréntesis de cierre. Si no se proporcionan las profundidades de anidamiento, se pueden calcular mediante un cálculo de suma de prefijos .

También se pueden aplicar técnicas similares a problemas de triangulación de polígonos , construcción de envoltura convexa (paralelizando el algoritmo de envoltura convexa de escaneo Graham secuencial ), reconstrucción de árboles a partir de dos de los órdenes de recorrido de los árboles y construcción de árboles cuaternarios. ^[1]

En una computadora secuencial, todos los valores más pequeños más cercanos se pueden encontrar utilizando una estructura de datos de pila : se procesan los valores en orden secuencial, utilizando la pila para mantener una subsecuencia de los valores que se han procesado hasta ahora y que son más pequeños que cualquier valor posterior que ya se haya 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 mientras 
    S no esté vacía y el elemento superior de S sea mayor o igual a x
        Estallido S
    Si S está vacío entonces
        x no tiene ningún valor menor precedente
    demás
        El valor más pequeño más cercano a x 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, ya que cada iteración del bucle interno elimina un elemento que se había añadido 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; supone que la secuencia de entrada se proporciona como una matriz A[1,n]de tamaño n, y almacena el índice jdel valor precedente más pequeño del valor i^thA[i] en P[i]. Suponemos un mínimo general artificial en A[0]:

para i de 1 a n:
    j = i-1
    mientras A[j] >= A[i]:
        j = P[j]
    P[i] = j

Berkman, Schieber y Vishkin (1993) demostraron cómo resolver el problema de todos los valores más pequeños más cercanos de manera eficiente en una máquina de acceso aleatorio paralelo de lectura y escritura simultáneas . Para una secuencia de n valores, almacenados como una matriz , utilizan un árbol doblemente logarítmico para demostrar que el problema se puede resolver en un tiempo O(log log  n ) utilizando una cantidad lineal de trabajo total. Para secuencias donde todos los valores son 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 el mejor que se puede lograr para el problema. Desde este trabajo, también se han desarrollado algoritmos paralelos para el problema de todos los valores más pequeños más cercanos en otros modelos de computación paralela, incluidos los ordenadores paralelos con una red de comunicaciones estructurada en hipercubo , ^[3] y el modelo paralelo sincrónico masivo . ^[4]

• Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), "Árboles LRM: índices comprimidos, ordenamiento adaptativo y permutaciones comprimidas", Theoretical Computer Science , 459 : 26–41, arXiv : 1009.5863 , doi :10.1016/j.tcs.2012.08.010.
• Berkman, Omer; Matias, Yossi; Ragde, Prabhakar (1998), "Límites superiores e inferiores paralelos triplemente logarítmicos para mínimos y mínimos de rango 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 la búsqueda de todos los valores más pequeños más cercanos", Journal of Algorithms , 14 (3): 344–370, doi :10.1006/jagm.1993.1018.
• Bern, Marshall; Eppstein, David ; Teng, Shang-Hua (1999), "Construcción paralela de árboles cuaternarios y triangulaciones de calidad" (PDF) , International Journal of Computational Geometry & Applications , 9 (6), World Scientific Publishing Company: 517–532, doi :10.1142/S0218195999000303.
• Gabow, Harold N. ; Bentley, Jon Louis ; Tarjan, Robert E. (1984), "Escalamiento y técnicas relacionadas para problemas de geometría", Actas del decimosexto simposio anual de la ACM sobre teoría de la computación - STOC '84 , Nueva York, NY, EE. UU.: ACM, págs. 135–143, doi :10.1145/800057.808675, ISBN 0-89791-133-4, Número de identificación del sujeto  17752833.
• He, 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. Parallel and Distributed Systems , 7 (5): 456–462, doi :10.1109/71.503770.
• Vuillemin, Jean (1980), "Una mirada unificadora a las estructuras de datos", Commun. ACM , 23 (4), Nueva York, NY, EE. UU.: ACM: 229–239, doi : 10.1145/358841.358852.