90
правок
Изменения
Нет описания правки
[[Файл:AlgoF2.gif|400px|right]]
===Добавление элементов===
Благодаря степеням использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Чаще всего при добалении добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)).
Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за О(1).
Самый интересный случай, - когда главный массив и все листья заполнены. Сначала вычислим новый размер 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>. Это означает, что среднее число дополнительных операций копирования - O(N) для последовательного добавления N элементов, а не <math>O(N^2)</math>.
[[Файл:AlgoF3.gif|350px|left|График 1]]
[[Файл:AlgoF4.gif|350px|right| График 2]]
Сравнивая со стандартным массивом переменной длины, реализованным в стандартной библиотеке С++, мы получаем, что благодаря предвычислению (1<<power)-1, разыменование элементов в HAT происходит приблизительно в два раза быстрее, чем разыменование в стандартном массиве С++. Рассотрим Рассмотрим несколько графиков, показывающих скорость работы HAT на некоторых алгоритмах:
*1) Быстрая сортировка(QuickSort). График сравнивает HAT и стандартный массив в С++(левый график).
*2) Добавление и сортировка(правый график).
==Заключение==
HAT - удобная структура данных переменной длины, позволяющая добавить N элементов за O(N) времени и требующая O(sqrt(N)) памяти. HAT обеспечивает все стадартные стандартные возможности обычных массивов, включая произвольный доступ к элементам. Она поддерживает известный объем памяти для любого количества элементов и не требует специальной настроки настройки для эффективной работы приложений. Таким образом , HAT предлагает ряд существенных преимуществ над другими реализациями массивов переменной длины.
==Литература==
*Cline, M.P. and G.A. Lomow, C++ FAQs, Reading, MA: Addison-Wesley, 1995.
*Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.
