90
правок
Изменения
Нет описания правки
[[Файл: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.
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.
