90
правок
Изменения
Нет описания правки
===Расход памяти===
[[Файл:Table_HAT.JPG|350px|right]]При перераспределении и копировании HAT использует мнеьше памяти, чем в стандартных подходах. Самый плохой случай для HAT - размер элементов равен размеру указателей и число элементов на один больше числа при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значени привидены в таблице:[[Файл:Table_HAT.JPG|400px|left]]
Затраты памяти в самом плохом случае - <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) Добавление и сортировка.
Все стандартные тесты были выполнены на 100Mhz HP 700 series PA-RISC workstation running HPUX 9.01 with 256 MB of memory.
==Заключение==
