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
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
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:
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 ithA[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]