Геометрическое хеширование

Геометрическое хеширование— широко применяемый в компьютерной графике и вычислительной геометрии метод для решения задач на плоскости или в трёхмерном пространстве, например для нахождения ближайших пар в множестве точек или для поиска одинаковых изображений. Хеш-функция в данном методе обычно получает на вход какое-либо метрическое пространство и разделяет его, создавая сетку из клеток. Таблица в данном случае является массивом с двумя или более индексами и называется файл сетки(англ. Grid file). Геометрическое хеширование также применяется в телекоммуникациях при работе с многомерными сигналами.^[8]

Ускорение поиска данных

Хеш-таблицей называется структура данных, позволяющая хранить пары вида (ключ, хеш-код) и поддерживающая операции поиска, вставки и удаления элемента. Задачей хеш-таблиц является ускорение поиска, например, при записи текстовых полей в базе данных может рассчитываться их хеш код и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста и сразу станет известно, в каком разделе их надо искать, то есть, искать надо будет не по всей базе, а только по одному её разделу (это сильно ускоряет поиск).

Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.

2.Пирамиды

Пирамида — двоичное дерево, в котором каждый родитель не меньше своих сыновей.

Пусть на основе входного массива нам удалось построить пирамиду. Тогда легко найти максимальный элемент (он находится в корне дерева). Этот элемент можно поместить в конец выходного массива, а в корень перенести последний из листьев.

Теперь нам нужно восстановить свойство пирамиды. Для этого меняем корень с наибольшим из его сыновей:

Однако свойство опять не выполнено. Поэтому опять меняем узел, для которого оно не выполнено, с наибольшим из его сыновей и повторяем эту операцию, пока не получим пирамиду:

Теперь мы опять можем взять максимум и поставить его в выходной массив на предпоследнее место и т.д.

Каждый такой шаг выполняется в худшем случае за время ~log₂K, где K — кол-во элементов в пирамиде. Т. о. в худшем случае все шаги выполнятся за время log₂N + log₂(N-1) + ... + log₂1, и т. к.

Nlog₂N > log₂N + log₂(N-1) + ... + log₂1 > log₂(1*N) + log₂(2*N) + ... > N/2*log₂N,

то время сортировки массива при уже построенной на его основе пирамиде есть O(Nlog₂N).

Остаётся вопрос: как построить пирамиду?

Запишем элементы массива в узлы двоичного дерева по порядку. Начинаем проверять выполнение свойства пирамиды с предпоследнего уровня (для листьев оно, очевидно, выполнено). Если для какого-то узла свойство не выполнено, то опускаем его вниз по дереву, меняя его каждый раз с наибольшим из сыновей, пока для поддерева, в котором он был корнем, не будет выполнено свойство пирамиды.

Сколько времени займёт такая процедура? В худшем случае:

0*2^k-1 + 1*2^k-2 + 2*2^k-3 + ... + (i-1)*2^k-i + ... + 2⁰*(k-1), где k — кол-во уровней в дереве (k~log₂N).

Эту сумму (обозначим её S) можно посчитать двумя способами:

1) S = 2^k-2 + 2^k-3 + ... + 1 +

2^k-3 + ... + 1 +

...

+ 1 = (2^k-1 - 1) + (2^k-2 -1) + ... + (2-1) =

= 2^k - 2 - (k -1) = 2^k - k - 1;

2) S = 2S - S = 2^k-1 + 2^k-2 + ... + 2 - (k-1) =

= 2^k - 2 - (k-1) = 2^k - k - 1 ~ N - log₂N - 1 ~ N

Таким образом, время построения пирамиды линейно, а значит время всего алгоритма сортировки ~Nlog₂N.

Куча

Когда речь идёт о структуре данных, пирамиду обычно называют кучей.

Операции:

• построить из массива — за время O(N);

• взять максимум — O(1);

• удалить максимум и перестроить — O(log₂N)

С помощью кучи можно быстро сделать частичную сортировку (например, переставить в конец массива несколько наибольших его элементов)