Изменения

Перейти к: навигация, поиск

Обсуждение участника:SergeyBud

29 байт убрано, 14:09, 1 июня 2014
Нет описания правки
==Значимость==
Массивы переменной длины - наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при реализации мы можем столкнуться с двумя основными проблемами: чрезмерное копирование элементов и использование памяти. HAT - реализация массива переменной длины, решающая обе проблемы и предоставляющая ряд преимуществ, по сравнению со стандартными реализациями.
==Устройство HAT==
HAT состоит из главного массива указателей и ряда листьев(так же одномерные массивы), в которых хранятся элементы.Число указателей в главном массиве и число элементов в каждом листе - равны между собой, и являются степенями двойки.
[[Файл:AlgoF2.gif|400px|right]]
===Добавление элементов===
Благодаря степеням двойки, мы сможем можем эффективно находить элементы в HAT, используя поразрядные операции. Чаще всего при добалении элемента, в одном из листьев(последний незаполненный последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)). Реже мы столкнемся со случаем, когда необходимо создать новый лист. Необходимо Достаточно всего лишь добавить указатель в свободную ячейку главного массива, а значит что также сможем позволит произвести вставку элемента за О(1).Самый интересный случай, когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT - следующая степень двойки(главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился).Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивв массивов переменной длины. Копировать элементы мы будем только тогда, когда главный массив полон, то есть число элементов превышает квадрат (достигли соответствующей степени 2двойки). Например, для 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>.
===Расход памяти===
[[Файл:Table_HAT.JPG|350px|right]]
При перераспределении и копировании 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>.
Сравним с другими структурами, добавляющими элементы за О(1). Например, отдельно связанные списки требуют O(N) памяти (один указатель для каждого элемента).
[[Файл: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.
90
правок

Навигация