Все ближайшие меньшие значения - All nearest smaller values

В Информатика, то все ближайшие меньшие значения Задача заключается в следующем: для каждой позиции в последовательности чисел поиск среди предыдущих позиций последней позиции, содержащей меньшее значение. Эта проблема может быть эффективно решена как параллельными, так и непараллельными алгоритмами: Беркман, Шибер и Вишкин (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]

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

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

S = новая пустая структура данных стеказа x во входной последовательности делать    пока S непусто, а верхний элемент S больше или равен x делать        поп S если S является пустой тогда        x не имеет предшествующего меньшего значения еще        ближайшее меньшее значение к x - это верхний элемент S push x на S

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

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

за я от 1 до n: j = i-1 пока A [j]> = A [i]: j = P [j] P [i] = j

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

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

Примечания

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