Сортировка Хана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 50: Строка 50:
 
Предположим, что <tex>n</tex> чисел должны быть сортированы, и в каждом <tex>logm</tex> бит. Мы рассматриваем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>log(m/h)</tex> бит. Теперь мы применяем хэширование ко всем сегментам и получаем <tex>2hlogn</tex> бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex>log(m/h)</tex> бит в каждом.
 
Предположим, что <tex>n</tex> чисел должны быть сортированы, и в каждом <tex>logm</tex> бит. Мы рассматриваем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>log(m/h)</tex> бит. Теперь мы применяем хэширование ко всем сегментам и получаем <tex>2hlogn</tex> бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex>log(m/h)</tex> бит в каждом.
  
Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, ..., <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Мы хотим разделить <tex>S</tex> в <tex>p + 1</tex> наборов таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < ... < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Т.к. мы используем signature sorting, до того как делать вышеописанное разделение, мы поделим биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и возьмем некоторые из них. Мы так же поделим биты для каждого числа из <tex>S</tex> и оставим только один в каждом числе. По существу для каждого <tex>a_{i}</tex> мы возьмем все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегменты, которые мы берем для числа в <tex>S</tex>, {{---}} сегмент, который "вылетает" из <tex>a_{i}</tex>. Таким образом мы преобразуем начальную задачу о разделении <tex>n</tex> чисел в <tex>logm</tex>бит в несколько задач на разделение с числами в <tex>log(m/h)</tex> бит.
+
Так же, рассмотрим проблему последующего разделения. Пусть <tex>a_{1}</tex>, <tex>a_{2}</tex>, ..., <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Мы хотим разделить <tex>S</tex> в <tex>p + 1</tex> наборов таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < ... < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Т.к. мы используем signature sorting, до того как делать вышеописанное разделение, мы поделим биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и возьмем некоторые из них. Мы так же поделим биты для каждого числа из <tex>S</tex> и оставим только один в каждом числе. По существу для каждого <tex>a_{i}</tex> мы возьмем все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегменты, которые мы берем для числа в <tex>S</tex>, {{---}} сегмент, который "вылетает" из <tex>a_{i}</tex>. Таким образом мы преобразуем начальную задачу о разделении <tex>n</tex> чисел в <tex>logm</tex> бит в несколько задач на разделение с числами в <tex>log(m/h)</tex> бит.

Версия 00:10, 11 июня 2012

Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью [math]O(nlog(logn))[/math], где [math]n[/math] — количество элементов для сортировки.

Алгоритм

Алгоритм построен на основе экспоненциального поискового дерева (далее — Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.

Andersson's exponential search tree

Э.П.дерево с [math]n[/math] листьями состоит из корня [math]r[/math] и [math]n^e[/math] (0<[math]e[/math]<1) Э.П.поддеревьев, в каждом из которых [math]n^{1 - e}[/math] листьев; каждое Э.П.поддерево является сыном корня [math]r[/math]. В этом дереве [math]O(log(logn))[/math] уровней. При нарушении баланса дерева, необходимо балансирование, которое требует [math]O(nlog(logn))[/math] времени при [math]n[/math] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Необходимая информация

Определение:
Контейнер — объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64, и т.д.


Определение:
Алгоритм сортирующий [math]n[/math] целых чисел из множества {0, 1, ..., [math]m[/math] - 1} называется консервативным, если длина контейнера (число бит в контейнере), является [math]O(log(m + n)).[/math] Если длина больше, то алгоритм не консервативный.


Определение:
Для множества [math]S[/math] определим

min([math]S[/math]) = min([math]a[/math]:[math]a[/math] принадлежит [math]S[/math]) max([math]S[/math]) = max([math]a[/math]:[math]a[/math] принадлежит [math]S[/math])

Набор [math]S1[/math] < [math]S2[/math] если max([math]S1[/math]) <= min([math]S2[/math])


Уменьшение числа бит в числах

Один из способов ускорить сортировку — уменьшить число бит в числе. Один из способов уменьшить число бит в числе — использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий [math]O(m)[/math] памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до [math]O(n)[/math]. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования [math]n[/math] чисел в таблицу размера [math]O(n^2)[/math] за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.

Алгоритм: Пусть целое число [math]b[/math] >= 0 и пусть [math]U[/math] = {0, ..., [math]2^b[/math] - 1}. Класс [math]H_{b,s}[/math] хэш функций из [math]U[/math] в {0, ..., [math]2^s[/math] - 1} определен как [math]H_{b,s}[/math] = {[math]h_{a}[/math]| 0 < [math]a[/math] < [math]2^b[/math], и [math]a[/math] нечетно} и для всех [math]x[/math] из [math]U[/math]: [math]h_{a}(x) = (ax[/math] mod [math]2^b[/math][math])[/math] div [math]2^{b - s}[/math]

Данный алгоритм базируется на следующей лемме:

Лемма:
Даны целые числа [math]b[/math] >= [math]s[/math] >= 0 и [math]T[/math] является подмножеством {0, ..., [math]2^b[/math] - 1}, содержащим [math]n[/math] элементов, и [math]t[/math] >= [math]2^{-s + 1}[/math]С[math]^k_{n}[/math]. Функция [math]h_{a}[/math] принадлежащая [math]H_{b,s}[/math] может быть выбрана за время [math]O(bn^2)[/math] так, что количество коллизий [math]coll(h_{a}, T) \lt = t[/math]

Взяв [math]s = 2logn[/math] мы получим хэш функцию [math]h_{a}[/math] которая захэширует [math]n[/math] чисел из [math]U[/math] в таблицу размера [math]O(n^2)[/math] без коллизий. Очевидно, что [math]h_{a}(x)[/math] может быть посчитана для любого [math]x[/math] за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить [math]h_{a}[/math] ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod [math]2^b[/math]) и (div [math]2^{b - s}[/math]).

Такая хэш функция может быть найдена за [math]O(n^3)[/math].

Следует отметить, что несмотря на размер таблицы [math]O(n^2)[/math], потребность в памяти не превышает [math]O(n)[/math] потому, что хэширование используется только для уменьшения количества бит в числе.

Signature sorting

В данной сортировке используется следующий алгоритм:

Предположим, что [math]n[/math] чисел должны быть сортированы, и в каждом [math]logm[/math] бит. Мы рассматриваем, что в каждом числе есть [math]h[/math] сегментов, в каждом из которых [math]log(m/h)[/math] бит. Теперь мы применяем хэширование ко всем сегментам и получаем [math]2hlogn[/math] бит хэшированных значений для каждого числа. После сортировки на хэшированных значениях для всех начальных чисел начальная задача по сортировке [math]n[/math] чисел по [math]m[/math] бит в каждом стала задачей по сортировке [math]n[/math] чисел по [math]log(m/h)[/math] бит в каждом.

Так же, рассмотрим проблему последующего разделения. Пусть [math]a_{1}[/math], [math]a_{2}[/math], ..., [math]a_{p}[/math][math]p[/math] чисел и [math]S[/math] — множество чисeл. Мы хотим разделить [math]S[/math] в [math]p + 1[/math] наборов таких, что: [math]S_{0}[/math] < {[math]a_{1}[/math]} < [math]S_{1}[/math] < {[math]a_{2}[/math]} < ... < {[math]a_{p}[/math]} < [math]S_{p}[/math]. Т.к. мы используем signature sorting, до того как делать вышеописанное разделение, мы поделим биты в [math]a_{i}[/math] на [math]h[/math] сегментов и возьмем некоторые из них. Мы так же поделим биты для каждого числа из [math]S[/math] и оставим только один в каждом числе. По существу для каждого [math]a_{i}[/math] мы возьмем все [math]h[/math] сегментов. Если соответствующие сегменты [math]a_{i}[/math] и [math]a_{j}[/math] совпадают, то нам понадобится только один. Сегменты, которые мы берем для числа в [math]S[/math], — сегмент, который "вылетает" из [math]a_{i}[/math]. Таким образом мы преобразуем начальную задачу о разделении [math]n[/math] чисел в [math]logm[/math] бит в несколько задач на разделение с числами в [math]log(m/h)[/math] бит.