Pull to refresh

Двоичные таблицы Юнга

Reading time 7 min
Views 3.2K
Итак, как и обещал, продолжение темы о таблицах Юнга. Напомню, что под таблицей Юнга понимается числовая матрица, обладающая некоторыми специальными свойствами. Матрица – это двумерный массив. И вот тут должен возникнуть естественный вопрос – а почему, собственно, массив должен быть двумерным? А что, если мы попробуем реализовать на тех же принципах таблицу размерности три, или четыре, а лучше всего, конечно, пять звездочек! О том, куда приведет нас такое обобщение, можно прочитать под катом...

Одномерные таблицы Юнга


Прежде, чем устремлять размерность таблицы Юнга к бесконечности, давайте посмотрим, что у нас остается «за спиной». Меньше двойки только единица (не считая нуля, но таблица Юнга нулевой размерности – это что-то типа нуль-пространства – никто не знает что это такое, но звучит красиво).
Итак, одномерная таблица Юнга – что это такое? Следуя определению, данному в предыдущем топике – это всего лишь упорядоченный по убыванию одномерный массив, все непустые ячейки которого располагаются в его начале.

Подъем и спуск элементов (базовые операции над таблицами Юнга) в данном случае сводятся к линейному просмотру таблицы справа налево (подъем) или слева направо (спуск):

def MoveUp(X, i):
  while i>0 and X[i]>X[i-1]:
    X[i], X[i-1] = X[i-1], X[i]
    i -= 1

def MoveDown(X, n):
  i = 0
  while i+1<n and X[i]a>X[i+1]:
    X[i], X[i-1] = X[i-1], X[i]    
    i += 1


Сам алгоритм сортировки практически ничем не отличается от того, который был описан здесь.
def YoungSort(X, n):
  for i in range(1,n):
    MoveUp(X,i)
  for i in range(1,n):
    X[0], X[n-i] = X[n-i], X[0]
    MoveDown(X,n-i)

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

Обобщенные таблицы Юнга


Примем за определение обобщенной таблицы Юнга следующее: таблицей Юнга называется частично упорядоченный почти заполненный числовой массив размерности d.
Чтобы определить свойства частичной упорядоченности и почти заполненности, введем понятие верхнего соседа ячейки (элемента) массива. Пусть некоторая ячейки массива характеризуется индексами i1, i2, …, id. Тогда, верхним соседом данной ячейки называется любая ячейка, все индексы которой, за исключением одного, равны индексам данной ячейки, а оставшийся индекс ровно на единицу меньше соответствующего индекса заданной ячейки. Например, у ячейки с индексами [1,0,5,3] имеется три верхних соседа: [0,0,5,3], [1,0,4,3] и [1,0,5,2]. Таким образом, если все индексы ячейки ненулевые, то у нее имеется ровно d верхних соседей, а если все индексы нулевые, то соседей сверху нет – такой элемент назовем вершиной таблицы Юнга.
Тогда, частичная упорядоченность означает, что значение любого элемента таблицы Юнга не больше значений всех его верхних соседей в этой таблице.
Почти заполненность означает, что если некоторая ячейка таблицы Юнга является заполненной (т.е. содержит некоторое значение), то и все ее верхние соседи также являются заполненными.
Нетрудно показать, что вдоль каждой размерности (когда все индексы, кроме одного, зафиксированы) значения ячеек таблицы Юнга образуют невозрастающую последовательность. Как следствие, самый большой элемент таблицы всегда располагается в ее вершине.
К сожалению, визуализация уже трехмерных таблиц Юнга сопряжена со значительными трудностями, поэтому читателю предлагается включить свое многомерное воображение, помогая ему (воображению) при необходимости картинками обычных двумерных таблиц Юнга.
Операции подъема и спуска обобщаются очевидным образом. При подъеме некоторого элемента перебираются все его соседи сверху, если обнаруживаются соседи с меньшими значениями, то из них выбирается наименьший, он меняется местами с текущим и процесс продолжается для нового текущего элемента. Если значения всех верхних соседей больше текущего, то подъем закончен. Пример подъема элемента в трехмерной таблице Юнга приведен на рисунке (показан только фрагмент таблицы).

Спуск выполняется аналогично, но перебираются все соседи снизу (ячейки, для которых текущая является верхним соседом) и из них выбирается наибольший.
Используя данные две операции, можно реализовать вставку нового элемента в таблицу и удаление наибольшего элемента из таблицы. А уже с помощью вставки и удаления просто реализуется сортировка. Реализация подъема и спуска, в принципе, не должная вызывать особых трудностей даже для d-мерных таблиц, но, все-таки, сначала попытаемся оценить сложность данных двух операций.
Будем предполагать, что каждый индекс d-мерной таблицы Юнга изменяется от 0 до m-1. Возьмем наихудший случай – таблица заполнена до конца (число элементов n=md), требуется поднять последний ее элемент, который (так получилось) является наибольшим. Т.е. в конце подъема этот элемент должен оказаться на вершине таблицы. Т.к. в процессе подъема на каждой итерации уменьшается на единицу ровно один индекс элемента, то всего придется выполнить порядка dm итераций. На каждой итерации выполняется один обмен, и не более d сравнений (при просмотре соседей). Итого, одна операция подъема (в худшем случае) обойдется нам в O(d2m) действий. Это значит, что n таких операций будут стоить уже O(d2mn) действий. С учетом того, что n=md, получаем следующую оценку сложности сортировки с помощью d-мерной таблицы Юнга: O(d2n1+1/d).
Хорошая новость – с увеличением d уменьшается показатель степени 1+1/d: 2 (одномерная таблица Юнга), 1.5 (стандартная таблица Юнга), 1.33, 1.25, 1.2 и т.д., в пределе этого всего стоит 1 – неужели мы превзойдем быструю сортировку?! Теперь плохая новость – с увеличением d увеличивается и коэффициент перед данной степенью. Несложно показать (используя производную), что оптимальным является выбор параметра d приблизительно равным log2n. Подставляем это значение в формулу O(d2n1+1/d) и после несложных преобразований получаем окончательную оценку O(nlog2n) – все, революция отменяется, т.к. полученная оценка асимптотически чуть-чуть, но хуже оптимальной линейно-лограрифмической…

Двоичные таблицы Юнга


Хотя мы и показали, что даже в лучшем случае сортировка с помощью таблиц Юнга не дотягивает до асимптотической оптимальности, мы все же попытаемся реализовать лучшую из таких таблиц, т.е. таблицу размерности d=log2n, которую будем называть двоичной таблицей Юнга. Пусть такая таблица и не может использоваться для организации эффективной сортировки, тем не менее, возможно кому-нибудь удастся найти ей и полезное применение. А кроме всего прочего, реализация двоичной таблицы Юнга просто является хорошим упражнением по программированию.
Сначала давайте формализуем понятие двоичной таблицы Юнга. Будем называть двоичной таблицу Юнга размерности d, в которой каждый индекс может принимать всего два значения 0 и 1. Если обозначить через n емкость такой таблицы, то получим, что n=2d или d=log2n. Примеры таких таблиц для небольших значений d показаны на следующем рисунке. Ага, скажет проницательный читатель, да ведь это гиперкубы размерности d! И будет совершенно прав.

Теперь давайте развернем такой гиперкуб в линейный массив, используя стандартную схему расположения многомерных массивов в памяти – быстрее всего меняется младший индекс. Для примера рассмотрим таблицу размерности d=3 с предыдущего рисунка.

Что мы видим – индексы, трактуемые как числа в двоичной системе счисления, образуют последовательность 0, 1, 2, 3 и т.д. То есть, мы получили простой алгоритм преобразования координат ячейки в двоичной таблице Юнга в координаты этой же ячейки в линеаризованной таблице. Ну а с битами мы работать-то умеем! Кажется, умеем…
Ключевыми понятиями таблицы Юнга являются верхние и нижние соседи ячеек. Применительно к двоичной таблице Юнга эти понятия определяются следующим образом: ячейка с индексом i (в линеаризованной таблице) называется верхним соседом ячейки с индексом j, если битовое представление числа i совпадает с битовым представлением числа j, за исключением ровно одного бита, который в j равен единице, а в i – нулю. Соответственно, ячейка j в данном определении будет нижним соседом ячейки i. Например, ячейка с номером 6=1102 является верхним соседом ячейки с номером 7=1112, и нижним соседом ячейки с номером 2=0102.

Подъем и спуск элементов


Операции подъема и спуска определяются точно так же, как они были определены выше для обобщенных таблиц. Чтобы реализовать эти операции для двоичных таблиц в силу только что сделанного определения верхних и нижних соседей, нам нужен эффективный алгоритм перебора всех единичных (подъем) или нулевых (спуск) битов заданного целого числа. Специально для тех, кому лень думать в этом направлении, имеется замечательная книжка Генри Уоррена «Алгоритмические трюки для программистов», где имеются интересующие нас формулы. Итак, чтобы обнулить крайний справа единичный бит числа x, используется операция x&(x-1). Для замены крайнего с правого нуля на единицу используется аналогичная операция x|(x+1). Этих операций (плюс немного танцев с бубном) оказывается достаточно для организации перебора всех единиц (нулей) в заданном целом числе.

Реализация


Ниже приведена реализация операций подъема и спуска элементов для двоичной таблицы Юнга, представленной вектором X.
def MoveUp(X, i):
  while True:
    t = i
    j = i
    while j: # цикл по всем единичным битам числа i
      k = j-1
      l = k&i
      if X[t]>X[l]: t = l # нашли нового большего соседа
      j = k&j
    if i==t: return # подъем закончен
    X[i], X[t] = X[t], X[i] # поднимаем элемент
    i = t

При спуске соседи перебираются в порядке возрастания их номеров, поэтому при обнаружении первого пустого соседа (с номером большим размера таблицы) перебор заканчивается.
def MoveDown(X, n):
  i = 0
  while True:
    t = i
    j = i
    while True: # цикл по всем нулевым битам
      k = j+1
      l = k|i
      if l>=n: break # все оставшиеся нижние соседи - пустые
      if X[t]<X[l]: t = l # нашли нового меньшего соседа
      j = k|j
    if i==t: return # приехали
    X[i], X[t] = X[t], X[i]
    i = t

Сама сортировка выполняется по уже стандартной схеме.
def YoungTableauSort(X, n):
  for i in range(1,n): # собираем таблицу Юнга
    MoveUp(X,i)
  for i in range(1,n): # упорядочиваем последовательность
    X[0], X[n-i] = X[n-i], X[0]     
    MoveDown(X,n-i)

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


Итак, чего же мы добились? Кто-то скажет, что ничего особенного, и будет по своему прав. Сортировка явно не дотягивает до оптимальной, проигрывая, например, пирамидальной сортировке, устроенной на аналогичных принципах. По тем же причинам, реализация АТД Очередь с приоритетом на основе двоичных таблиц Юнга уступает аналогичной реализации с помощью пирамид. Ко всему прочему, переход от стандартных таблиц к двоичным убил, наверное, единственное преимущество таблиц Юнга над пирамидами — поиск произвольного элемента. Напомню, что в двумерных таблицах такой поиск выполняется за время O(n1/2), а вот в двоичных таблицах поиск произвольного значения потребует почти полного перебора всей таблицы, т.е. линейного по n времени. С другой стороны, как говорится, кто не рискует, тот не пьет шампанского. Мы попытались придумать новый алгоритм сортировки и нам это удалось. Да еще и с такой редкой производительностью O(nlog2n)! И еще, у автора все-таки теплится надежда, что такая красивая структура данных просто обязана иметь какие-нибудь интересные и полезные свойства, которые возможно удастся открыть кому-нибудь из читателей. Спасибо за внимание!

Литература:
  1. Кормен Т. и др. — Алгоритмы. Построение и анализ, 2009
  2. Фултон У. — Таблицы Юнга, 2006
  3. Уоррен Г. — Алгоритмические трюки для програмистов, 2004

PS: Кстати, вполне допускаю мысль, что все описанное выше уже когда-то кем-то открыто. Буду очень признателен, если у кого-нибудь есть такого рода информация и он готов ей поделиться!
Tags:
Hubs:
+32
Comments 3
Comments Comments 3

Articles