Изменения

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

Hashed Array Tree

5 байт добавлено, 18:55, 12 июня 2014
Нет описания правки
==Описание структуры==
HAT состоит из главного массива указателей <tex>top</tex> и ряда листьев <tex>leaf</tex> (так же одномерные массивы), в которых хранятся элементы.
Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки. HAT зполняется заполняется элементами от самого малого листа к самому большому, при этом каждый лист заполняется слева направо.
===Получение элемента по номеру===
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Пусть размер главного массива и каждого листа будет равен <tex>2^{power}</tex>.
'''return''' top[topIndex(j)][leafIndex(j)]
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex>. Получим значения функций для элемент под номером <tex>5</tex>:
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен опреации операции деления (взятию по модулю) <tex>j</tex> на <math>2^{2}</math>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерция нумерация листов с <tex>0</tex>).*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. Тоесть То есть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>.
<tex>5_{10} = 101_2 - 101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация тоже с <tex>0</tex>).
===Расход памяти===
HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.
Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[wikipedia:ru:Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительней дополнительной памяти сразу после перекопирования элементов, и лучше [[wikipedia:ru:Список (информатика) |списка]].
==Эффективность==
Анонимный участник

Навигация