Обсуждение участника:SergeyBud — различия между версиями
SergeyBud (обсуждение | вклад) |
SergeyBud (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
==Устройство HAT== | ==Устройство HAT== | ||
| − | |||
HAT состоит из главного массива указателей и ряда листьев(так же одномерные массивы), в которых хранятся элементы. | HAT состоит из главного массива указателей и ряда листьев(так же одномерные массивы), в которых хранятся элементы. | ||
Число указателей в главном массиве и число элементов в каждом листе - равны между собой, и являются степенями двойки. | Число указателей в главном массиве и число элементов в каждом листе - равны между собой, и являются степенями двойки. | ||
| − | + | [[Файл:AlgoF2.gif|right]] | |
=Добавление элементов= | =Добавление элементов= | ||
Благодаря степеням двойки, мы сможем эффективно находить элементы в HAT, используя поразрядные операции(см.Пример1). Чаще всего при добалении элемента, в одном из листьев(последний незаполненный на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)). | Благодаря степеням двойки, мы сможем эффективно находить элементы в HAT, используя поразрядные операции(см.Пример1). Чаще всего при добалении элемента, в одном из листьев(последний незаполненный на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)). | ||
Реже мы столкнемся со случаем, когда необходимо создать новый лист. Необходимо всего лишь добавить указатель в свободную ячейку главного массива, а значит также сможем произвести вставку элемента за О(1). | Реже мы столкнемся со случаем, когда необходимо создать новый лист. Необходимо всего лишь добавить указатель в свободную ячейку главного массива, а значит также сможем произвести вставку элемента за О(1). | ||
| + | Самый интересный случай, когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT - следующая степень двойки(главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился). | ||
| + | Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивв переменной длины. Копировать элементы мы будем только тогда, когда главный массив полон, то есть число элементов превышает квадрат степени 2. Например, для N=4, общая сумма перекопирования будет равна 1+4+16+64+256+...+N. Воспользуемся тождеством: (x^(n+1)-1)=(x-1)(1+x+x^2+x^3+... + x^n), тогда для нашего случая: 1 +4+4^2+4^3+...+4^n = (4^(n+1) -1)/(4-1) = (4N-1)/3, или около 4/3N. Это означает это, среднее число дополнительных операций копирования - O(N) для последовательного добавления N элементов, не O(N^2). | ||
Версия 12:35, 1 июня 2014
HAT(Hashed Array Tree) — структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев.
Значимость
Массивы переменной длины - наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при реализации мы можем столкнуться с двумя основными проблемами: черезмерое копирование элементов и использование памяти. Для примера рассмотрим однку из реализаций: /*****/
Устройство HAT
HAT состоит из главного массива указателей и ряда листьев(так же одномерные массивы), в которых хранятся элементы. Число указателей в главном массиве и число элементов в каждом листе - равны между собой, и являются степенями двойки.
Добавление элементов
Благодаря степеням двойки, мы сможем эффективно находить элементы в HAT, используя поразрядные операции(см.Пример1). Чаще всего при добалении элемента, в одном из листьев(последний незаполненный на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)). Реже мы столкнемся со случаем, когда необходимо создать новый лист. Необходимо всего лишь добавить указатель в свободную ячейку главного массива, а значит также сможем произвести вставку элемента за О(1). Самый интересный случай, когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT - следующая степень двойки(главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился). Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивв переменной длины. Копировать элементы мы будем только тогда, когда главный массив полон, то есть число элементов превышает квадрат степени 2. Например, для N=4, общая сумма перекопирования будет равна 1+4+16+64+256+...+N. Воспользуемся тождеством: (x^(n+1)-1)=(x-1)(1+x+x^2+x^3+... + x^n), тогда для нашего случая: 1 +4+4^2+4^3+...+4^n = (4^(n+1) -1)/(4-1) = (4N-1)/3, или около 4/3N. Это означает это, среднее число дополнительных операций копирования - O(N) для последовательного добавления N элементов, не O(N^2).
