13
правок
Изменения
м
Поправка орфографии.
'''return''' top[topIndex(j)][leafIndex(j)]
*
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex>. Получим значения функций для элемент элемента под номером <tex>5</tex>:
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен операции деления (взятию по модулю) <tex>j</tex> на <tex>2^{2}</tex>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерация листов с <tex>0</tex>).
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. То есть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>. Формула для <tex>leafIndex</tex> справедлива, так как элементы, которые находятся в разных листьях и различаются на <tex>2^k</tex>, будут иметь одинаковую позицию в этих листах, а младшие <tex>k</tex> бит у них будут общими. Поэтому сделаем операцию побивое побитовое "и" к запрашиваему запрашиваемому индексу и к <tex> 2^k - 1 </tex> и получим нужный индекс в массиве <tex> leaf </tex>.
<tex>5_{10} = 101_2</tex> , следовательно <tex>101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация тоже с <tex>0</tex>).
*Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <tex>O(1)</tex>.
*Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в <tex>2</tex> раза, то есть <tex>power = power \cdot 2 </tex>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <tex>1+4+16+64+256+...+N</tex>. Воспользуемся тождеством: <tex>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</tex>, тогда для нашего случая: <tex>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</tex>, или около <tex>4N/3</tex>. Это означает, что среднее число дополнительных операций копирования {{---}} <tex>O(N)</tex> для последовательного добавления <tex> N </tex> элементов, а не <tex>O(N^2)</tex>. Мы получили <tex>4N/3</tex> против <tex>2N</tex> в обычном динамическом массиве, то есть константа уменьшилась.
[[Файл:AlgoF2.gif|400px]]
===Расход памяти===
HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.
Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <tex>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</tex> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <tex>(top + leaf/2) \approx 1.5\sqrt{N}</tex>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[wikipedia:ru:Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительной памяти сразу после перекопирования элементов, и лучше [[wikipedia:ru:Список (информатика) |списка]].
==Эффективность==
