Pull to refresh

Таблицы Юнга в задачах поиска и сортировки

Algorithms *
Sandbox
Таблицы Юнга являются широко известным (в узких кругах) типом объектов, изучаемых в комбинаторике и смежных науках: ссылка, ссылка, книжка. Ниже рассматривается применение частного вида таблиц Юнга применительно к таким стандартным алгоритмическим задачам, как поиск и сортировка. С этой точки зрения таблицы Юнга весьма близки пирамидам, собственно так они и позиционируются в учебнике Кормена и ко (упражнения в разделе, посвященном пирамидам).
 
Понятие таблицы Юнга

Назовем таблицей Юнга частично упорядоченную почти заполненную числовую матрицу. Частичная упорядоченность означает, что каждый элемент такой матрицы не превышает значений своих верхнего и левого соседей (при условии, что эти соседи вообще у элемента есть). Почти заполненность означает следующее: полностью заполненными в таблице являются первые j строк матрицы (от нулевой до (j-1)-ой), в j-ой строке заполненными являются первые l элементов, все оставшиеся строки являются пустыми. Пример таблицы Юнга показан на следующем рисунке.

Согласно данному нами определению, строки и столбцы таблицы Юнга являются упорядоченными по убыванию. В частности, самый большой элемент таблицы находится в ее левом верхнем углу. Однако, расположение всех остальных элементов уже однозначно не определяется. Таким образом, таблицы Юнга могут рассматриваться как матричный (табличный) аналог частично-упорядоченных почти заполненных деревьев, известных в миру под названием пирамид.
 
Вставка и удаление элементов

Во-первых, разберемся с тем, каким образом вставить в таблицу Юнга новое значение x. Для этого сначала запишем значение x в первую свободную ячейку таблицы, так чтобы не нарушалось ее свойство почти заполненности. Если в таблице имеется не конца заполненная строка, то вставим новый элемент в первую свободную ячейку этой строки. Если такой строки нет, то вставим новый элемент в первую (нулевую) ячейку первой пустой строки. После выполненной вставки нарушенным может быть только свойство частичной упорядоченности. Чтобы восстановить его выполним операцию подъема элемента. Для этого текущий элемент x сравнивается с его верхним и левым соседями. Если кто-нибудь из этих соседей является меньшим x, то меняем местами x с меньшим из соседей. Этот процесс движения x вверх и влево по таблице продолжается до тех пор, пока мы не упремся в левый верхний угол, либо оба соседа (или один, если второго нет) не окажутся большими или равными x. На следующем рисунке показан процесс вставки числа 5 в таблицу с первого рисунка.

Удалять из таблицы Юнга будем только наибольший элемент, расположенный в ее левом верхнем углу. Сначала перенесем в эту ячейку значение x из последней занятой ячейки таблицы, после чего применим операцию спуска элемента. Эта операция выполняется аналогично подъему, но в другую сторону (вправо и вниз), до пор, пока у текущего элемента не окажется нижнего и правого соседей, либо эти соседи (или только один, если второго нет) не окажутся меньшими или равными x. Процесс удаления наибольшего элемента из таблицы с последнего рисунка показан ниже. 

Очевидно, что таблица Юнга с описанными выше операциями вставки и удаления фактически является реализацией АТД Очередь с приоритетом. Интересной особенностью данной реализации является то, что время вставки и удаления является величиной порядка O(max(r,c)), где r и c – размеры матрицы. Если мы положим, что r=c, то получим, что время вставки имеет порядок O(n0.5), где n – число элементов в таблице. Ниже будем считать, что для хранения n элементов используется квадратная таблица наименьшего возможного размера m = int(ceil(sqrt(n))).
 
Сортировка с помощью таблиц Юнга

Понятно, что имея реализацию АТД Очередь с приоритетом, можно организовать сортировку заданной числовой последовательности X. Схема такой сортировки тривиальна: сначала записываем все элементы их X в очередь, затем вынимаем все элементы из очереди и пишем и обратно в X начиная с конца (т.е. справа налево). Таким образом, наибольший элемент окажется записанным в конец X, следующий по величине – в предпоследнюю ячейку X и т.д. Очевидно, что время такой сортировки будет асимптотически равным произведению числа n элементов в X на время вставки (удаления) элементов в очередь. Т.е. при использовании таблицы Юнга в качестве очереди с приоритетом сложность сортировки будет равной O(n1.5). Это означает, что предложенный алгоритм асимптотически занимает промежуточное положение между квадратичными (вставкой) и линейно-логарифмическими алгоритмами (слиянием) и является близким соседом сортировки Шелла.
Описанная общая схема сортировки предполагает, что для хранения очереди используется отдельная структура данных, т.е. дополнительная память объема не меньше, чем n. Однако, как и для пирамид, для таблиц Юнга возможно выполнить сортировку по месту, не выходя за рамки последовательности (массива) X. Для этого заметим, что 1) каждый раз когда элемент вынимается из X, он тут же вставляется в таблицу и наоборот (т.е. суммарный объем необходимой памяти остается все время постоянным и равным n); 2) обычно матрицы хранятся в памяти компьютера построчно в виде, по сути, одномерного массива (либо мы сами можем организовать такую схему хранения). Исходя из этих соображений получаем следующий простой алгоритм сортировки, который использует две вспомогательные функции подъема (MoveUp) и спуска (MoveDown) элементов в таблице Юнга. В каждый момент времени левая часть массива X содержит в себе таблицу Юнга, правая – последовательность X. При первом проходе мы начинаем с таблицы в один элемент и постепенно добавляем в нее элементы из X. На втором проходе последовательно изымаем из таблицы наибольший элемент и меняем его с последним элементом таблицы, одновременно уменьшая размер таблицы на единицу. Это приводит к тому, что выстраиваемая вновь последовательность X оказывается упорядоченной по возрастанию.
from math import *

def YoungTableauSort(X, n):
  m = int(ceil(sqrt(n))) # размер таблицы
  for i in range(1,n): # создаем таблицу
    MoveUp(X,i,m) 
  for i in range(1,n): # упорядочиваем последовательность
    X[0], X[n-i] = X[n-i], X[0]
    MoveDown(X,n-i,m) 

def MoveUp(X,i,m):
  while True:
    t = i
    if i%m and X[i-1]<X[t]: t = i-1 # проверяем ячейку слева
    if i/m and X[i-m]<X[t]: t = i-m # проверяем ячейку сверху
    if i==t: return # достигли пункта назначения
    X[i], X[t] = X[t], X[i]
    i = t

def MoveDown(X,k,m): # k - число элементов в таблице
  i = 0
  while True:
    t = i
    if i%m+1<m and i+1<k and X[i+1]>X[t]: t = i+1 # проверяем ячейку справа
    if i/m+1<m and i+m<k and X[i+m]>X[t]: t = i+m # проверяем ячейку снизу
    if i==t: return # пришли
    X[i], X[t] = X[t], X[i]
    i = t


Итого, имеем алгоритм сортировки по месту, работающий за время O(n1.5) в худшем случае.

Поиск в таблице Юнга

Предположим мы хотим использовать таблицу Юнга (представленную одномерным массивом, как это было сделано выше) в качестве контейнера. Какие функции может поддерживать такой контейнер? Прежде всего вставка нового элемента, во-вторых, поиск наибольшего элемента (искать особенно при этом и не надо, т.к. этот элемент стоит первым), удаление наибольшего элемента, преобразование в упорядоченную последовательность. Перечисленные операции присущи также и пирамидам. Что отличает таблицы Юнга о пирамид, так это возможность эффективного поиска элементов. Найти что-нибудь кроме наибольшего элемента в пирамиде можно только полным перебором всех ее элементов (в худшем случае). Зато в таблице Юнга поиск любого элемента можно выполнить за то же время порядка O(n0.5). Алгоритм такого поиска выглядит следующим образом. Начинаем поиск элемента x с правого верхнего угла таблицы (в одномерном массиве это элемент с номером m-1). Если текущий элемент равен искомому, то поиск завершен. Если текущий элемент меньше искомого, то надо сдвинуться по таблице на шаг влево, т.к. все элементы ниже будут заведомо меньшими x. Если сдвигаться некуда, то поиск объявляется неуспешным. Если текущий элемент больше искомого, то надо сдвинуться вниз на одну ячейку. Если текущая строка последняя, то сдвиг невозможен – поиск неуспешный. Если же текущая строка не последняя, но элемента внизу текущего нет, то надо опять сдвигаться влево (с проверкой на достижение левого края таблицы). Код такой функции приведен ниже.
def Find(X,k,m,x): # k - число элементов в таблице
  i = m-1
  while True:
    if X[i]==x: return i # нашли
    if X[i]<x or i/m+1<m and i+m>=k: # требуется сдвиг влево
      if i%m: i -= 1
      else: return -1
    else: # требуется сдвиг вниз
      if i/m<m-1 and i+m<k: i += m
      else: return -1


Несложно убедиться, что число просмотренных элементов таблице при выполнении поиска не превышает удвоенного размера таблицы, т.е. опять же является величиной порядка O(n0.5). Пример поиска числа 4 в таблице Юнга показан на следующем рисунке.

 
Вместо заключения

К рассмотренным выше операциям над таблицами Юнга можно добавить 1) изменение значения любого элемента за время O(n0.5); 2) удаление произвольного элемента за время O(n0.5); 3) поиск наименьшего элемента, который вообще выполняется за постоянное время, т.к. наименьший элемент в силу определения таблицы Юнга расположен либо в последней непустой ячейке, либо в последней ячейке предпоследней непустой строки.
Таким образом, таблицы Юнга могут рассматриваться как относительно простой аналог двоичным деревьям поиска, преимуществ: простота реализации, малые накладные расходы на хранение данных; недостатки: время выполнения основных операций не логарифмическое, а «корнеквадратичное», проблема переполнения — после того, как в таблице заканчивается место, мы можем либо добавить новую строку (не выполняя полную реструктуруризацию, но нарушая квадратность таблицы, что в дальнейшем может привести к снижению эффективности операций), либо выполнить полную реструктуризацию в новую квадратную таблицу большего размера. Перечисленные недостатки частично решаются с помощью так называемых двоичных таблиц Юнга, о которых я как-нибудь в ближайшем будущем постараюсь написать.
Tags:
Hubs:
Total votes 50: ↑50 and ↓0 +50
Views 6.1K
Comments 13
Comments Comments 13