Изменения

При перераспределении и копировании HAT использует меньше дополнительной памяти, чем в стандартных подходах. Самый плохой случай для HAT {{---}} размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значения приведены в таблице.Затраты доролнительной памяти в самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math>. Если последний лист будет половиной полного, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math> (top {{---}} главный массив, leaf {{---}} листья), а это все еще <math>O(\sqrt{N})</math>. Сравним с другими структурами, добавляющими элементы за <math>O(1)</math>. Например, отдельно связанные списки требуют O(N) дополнительной памяти (один указатель для каждого элемента).

Сравнивая со стандартным массивом переменной длиныБлагодаря преимуществам, реализованным в стандартной библиотеке С++, мы получаем, что благодаря предвычислению предоставляемыми HAT(1<<power)-1, разыменование элементов в HAT так например вычисления адреса происходит приблизительно в два 2 раза быстрее, чем разыменование в стандартном массиве СC++. Рассмотрим несколько графиков), ее можно использовать в любых программах, требующих работу с массивами переменной длинны, показывающих скорость работы HAT на некоторых алгоритмах:*1) Быстрая сортировкагде использование других структур данных (QuickSortнапример списков)не удобно. График сравнивает На многих алгоритмах HAT и стандартный массив в С++(левый график).*2) Добавление и сортировка(правый график)работает значительно быстрее стандартных массивов, результаты тестов можно посмотреть здесь: [http://pmg. Все стандартные тесты были выполнены на 100Mhz HP 700 series PA-RISC workstation running HPUX 9org.01 with 256 MB of memoryru/ai/tree_hash.htm]