90
правок
Изменения
Нет описания правки
'''HAT(Hashed Array Tree)''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. В действительности HAT {{---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <math>O(N)</math>, чтобы добавить <math>N</math> элементов к пустому массиву и требует всего лишь <math>O(\sqrt({N)})</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>44N/3N3</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) памяти (один указатель для каждого элемента).
===Эффективность===
Сравнивая со стандартным массивом переменной длины, реализованным в стандартной библиотеке С++, мы получаем, что благодаря предвычислению (1<<power)-1, разыменование элементов в HAT происходит приблизительно в два раза быстрее, чем разыменование в стандартном массиве С++. Рассмотрим несколько графиков, показывающих скорость работы HAT на некоторых алгоритмах:
*1) Быстрая сортировка(QuickSort). График сравнивает HAT и стандартный массив в С++(левый график).
==Заключение==
HAT {{---}} удобная структура данных переменной длины, позволяющая добавить N элементов за <math>O(N)</math> времени и требующая <math>O(\sqrt({N)})</math> памяти. HAT обеспечивает все стандартные возможности обычных массивов, включая произвольный доступ к элементам. Она поддерживает известный объем памяти для любого количества элементов и не требует специальной настройки для эффективной работы приложений.
Таким образом, HAT предлагает ряд существенных преимуществ над другими реализациями массивов переменной длины.
