Все ближайшие меньшие значения

В информатике задача поиска всех ближайших меньших значений представляет собой следующую задачу: для каждой позиции в последовательности чисел найти среди предыдущих позиций последнюю позицию, содержащую меньшее значение. Эту проблему можно эффективно решить как с помощью параллельных, так и непараллельных алгоритмов: Беркман, Шибер и Вишкин (1993) , которые впервые определили эту процедуру как полезную подпрограмму для других параллельных программ, разработали эффективные алгоритмы для ее решения в параллельной машине произвольного доступа. модель; ее также можно решить за линейное время на непараллельном компьютере с использованием стекового алгоритма. Позже исследователи изучили алгоритмы ее решения в других моделях параллельных вычислений.

Пример

Предположим, что входными данными является двоичная последовательность Ван дер Корпута.

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

Первый элемент последовательности (0) не имеет предыдущего значения. Ближайшее (единственное) меньшее значение до 8 и до 4 равно 0. Все три значения до 12 меньше, но ближайшее — 4. Продолжая таким же образом, ближайшие предыдущие меньшие значения для этой последовательности (указывающие на несуществование) предыдущего меньшего значения через тире)

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

В большинстве приложений следует вычислять положения ближайших меньших значений, а не сами значения, и во многих приложениях те же вычисления должны выполняться для обращения последовательности, чтобы найти следующее меньшее значение, которое является ближайшим в последовательность.

Приложения

Беркман, Шибер и Вишкин (1993) упоминают множество других проблем, которые можно эффективно решать параллельно, используя вычисление ближайших меньших значений. Среди них можно отметить следующие:

Алгоритмы слияния , вычисляющие шаг слияния при сортировке слиянием . Входные данные этих алгоритмов состоят из двух отсортированных массивов чисел; желаемый результат — тот же набор чисел в одном отсортированном массиве. Если объединить два отсортированных массива, первый в порядке возрастания, а второй в порядке убывания, то предшественником каждого значения в выходных данных будет либо его ближайшее предыдущее меньшее значение, либо ближайшее следующее меньшее значение (в зависимости от того, какое из двух больше). , и положение каждого значения в отсортированном выходном массиве можно легко вычислить по положениям этих двух ближайших меньших значений.
Построение декартовых деревьев . Декартово дерево — это структура данных , введенная Вюйлемином (1980) и дополнительно изученная Габоу, Бентли и Тарджаном (1984) для приложений поиска по диапазону . Декартовы деревья также возникают при определении структуры данных дерева поиска и рандомизированного двоичного поиска для двоичного поиска . Декартово дерево последовательности значений имеет узел для каждого значения. Корень дерева — это минимальное значение последовательности; для каждого другого узла родительским узлом является либо его ближайшее предыдущее меньшее значение, либо ближайшее следующее меньшее значение (в зависимости от того, какое из двух существует и больше). Таким образом, декартовы деревья могут быть построены за линейное время на основе алгоритма всех ближайших меньших значений.
Соответствующие скобки . Если в качестве входных данных задана последовательность символов открывающих и закрывающих круглых скобок вместе с глубиной вложенности каждой скобки, то соответствием каждой открывающейся скобке является следующая закрывающая скобка без большей глубины вложенности, поэтому ее можно найти с помощью всех ближайших вычисление меньших значений, которое разрывает связи в пользу закрывающих круглых скобок. Если глубины вложенности не указаны, их можно рассчитать с помощью вычисления суммы префиксов .

Подобные методы также могут быть применены к задачам триангуляции многоугольников , построения выпуклой оболочки (параллелизация алгоритма выпуклой оболочки последовательного сканирования Грэма ), реконструкции деревьев на основе двух порядков обхода деревьев и построения квадродеревьев. ^[1]

Последовательный алгоритм

На последовательном компьютере все ближайшие меньшие значения могут быть найдены с использованием структуры данных стека : значения обрабатываются в порядке последовательности, используя стек для поддержания подпоследовательности значений, которые были обработаны до сих пор и меньше, чем любое более позднее значение. это уже обработано. В псевдокоде алгоритм следующий.

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

Несмотря на структуру вложенного цикла, время работы этого алгоритма линейно, поскольку каждая итерация внутреннего цикла удаляет элемент, который был добавлен на какой-то предыдущей итерации внешнего цикла. Он тесно связан с алгоритмом Кнута для сортировки стеком (для входных данных, которые можно сортировать таким образом). ^[2]

Еще более простой последовательный алгоритм с линейным временем ( Барбай, Фишер и Наварро (2012) , лемма 1) даже не требует стека; предполагается, что входная последовательность задана в виде массива A[1,n] размера nи сохраняет индекс j предыдущего меньшего значения i^й ценить A[i] в P[i]. Мы предполагаем искусственный общий минимум на уровне A[0]:

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

Параллельные алгоритмы

Беркман, Шибер и Вишкин (1993) показали, как эффективно решать проблему всех ближайших меньших значений на параллельной машине произвольного доступа с параллельным чтением и записью . Для последовательности из n значений, хранящихся в виде массива , они используют дважды логарифмическое дерево , чтобы показать, что проблема может быть решена за время O(log log n ), используя линейный объем общей работы. Для последовательностей, где все значения являются целыми числами в интервале [1, s ], Беркман, Матиас и Рагде (1998) улучшили эту границу до O(log log log s ); они также показали, что для достаточно больших значений s предыдущая дважды логарифмическая оценка времени является лучшим, чего можно достичь для этой задачи. После этой работы параллельные алгоритмы для задачи всех ближайших меньших значений также были разработаны для других моделей параллельных вычислений, включая параллельные компьютеры с сетью связи со структурой гиперкуба . ^[3] и объемная синхронная параллельная модель. ^[4]

Примечания

^ Берн, Эппштейн и Тенг (1999) .
^ Кнут, Дональд (1968), «Том 1: Фундаментальные алгоритмы», Искусство компьютерного программирования , Ридинг, Массачусетс: Аддисон-Уэсли .
^ Кравец и Плакстон (1996) .
^ Он и Хуан (2001) .

Ссылки

Барбей, Джереми; Фишер, Йоханнес; Наварро, Гонсало (2012), «LRM-деревья: сжатые индексы, адаптивная сортировка и сжатые перестановки», Theoretical Computer Science , 459 : 26–41, arXiv : 1009.5863 , doi : 10.1016/j.tcs.2012.08.010 .
Беркман, Омер; Матиас, Йоси; Рагде, Прабхакар (1998), «Тройно-логарифмические параллельные верхняя и нижняя границы минимума и минимума диапазона в небольших областях», Journal of Algorithms , 28 (2): 197–215, doi : 10.1006/jagm.1997.0905 .
Беркман, Омер; Шибер, Барух ; Вишкин, Узи (1993), «Оптимальные дважды логарифмические параллельные алгоритмы, основанные на поиске всех ближайших меньших значений», Journal of Algorithms , 14 (3): 344–370, doi : 10.1006/jagm.1993.1018 .
Берн, Маршалл; Эппштейн, Дэвид ; Тенг, Шан-Хуа (1999), «Параллельное построение квадродеревьев и качественная триангуляция» (PDF) , International Journal of Computational Geometry & Applications , 9 (6), World Scientific Publishing Company: 517–532, doi : 10.1142/S0218195999000303 .
Габоу, Гарольд Н .; Бентли, Джон Луис ; Тарьян, Роберт Э. (1984), «Масштабирование и связанные с ним методы решения задач геометрии», Труды шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84 , Нью-Йорк, Нью-Йорк, США: ACM, стр. 135–143, дои : 10.1145/800057.808675 , ISBN 0-89791-133-4 , S2CID 17752833 .
Он, Синь; Хуан, Чунь-Си (2001), «Эффективный алгоритм BSP для всех ближайших меньших значений», Journal of Parallel and Distributed Computing , 61 (10): 1425–1438, doi : 10.1006/jpdc.2001.1741 .
Кравец, Д.; Плакстон, К.Г. (1996), «Все ближайшие меньшие значения гиперкуба», IEEE Trans. Параллельные и распределенные системы , 7 (5): 456–462, doi : 10.1109/71.503770 .
Вийемен, Жан (1980), «Объединяющий взгляд на структуры данных», Commun. ACM , 23 (4), Нью-Йорк, штат Нью-Йорк, США: ACM: 229–239, doi : 10.1145/358841.358852 .

[1] Берн, Эппштейн и Тенг (1999) .

[2] Кнут, Дональд (1968), «Том 1: Фундаментальные алгоритмы», Искусство компьютерного программирования , Ридинг, Массачусетс: Аддисон-Уэсли .

[3] Кравец и Плакстон (1996) .

[4] Он и Хуан (2001) .

[1]

[2]

[3]

[4]