90
правок
Изменения
Нет описания правки
[[Файл:AlgoF2.gif|400px|right]]
===Добавление элементов===
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку(<math>O(1)</math>). Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <math>О(1)</math>.
Самый интересный случай {{---}} когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT {{---}} следующая степень двойки (главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился).
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины. Копировать элементы мы будем только тогда, когда главный массив полон(достигли соответствующей степени двойки). Например, для N=4, общая сумма перекопирования будет равна 1+4+16+64+256+...+N. Воспользуемся тождеством: <math>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^n)</math>, тогда для нашего случая: <math>1 +4+4^2+4^3+...+4^n = (4^{n+1} -1)/(4-1) = (4N-1)/3</math>, или около <math>4/3N</math>. Это означает, что среднее число дополнительных операций копирования - <math>O(N) </math> для последовательного добавления N элементов, а не <math>O(N^2)</math>.
===Расход памяти===
При перераспределении и копировании HAT использует меньше памяти, чем в стандартных подходах. Самый плохой случай для HAT {{--}} размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значения приведены в таблице.
Затраты памяти в самом плохом случае {{---}} <math>(top+leaf-1) ~= 2*sqrt(N) = O(sqrt(N))</math>. Если последний лист будет половиной полного, то ожидаемая трата памяти уменьшается до <math>(top + leaf/2) ~= 1.5*sqrt(N)</math>, а это все еще <math>O(sqrt (N))</math>.
Сравним с другими структурами, добавляющими элементы за <math> О(1)</math>. Например, отдельно связанные списки требуют O(N) памяти (один указатель для каждого элемента).
===Эффективность===
==Заключение==
HAT {{---}} удобная структура данных переменной длины, позволяющая добавить N элементов за <math>O(N) </math> времени и требующая <math>O(sqrt(N)) </math> памяти. HAT обеспечивает все стандартные возможности обычных массивов, включая произвольный доступ к элементам. Она поддерживает известный объем памяти для любого количества элементов и не требует специальной настройки для эффективной работы приложений.
Таким образом, HAT предлагает ряд существенных преимуществ над другими реализациями массивов переменной длины.
