Дополненная карта - Augmented map

В Информатика, то дополненная карта^[1] является абстрактный тип данных (ADT) на основе заказанного карты, который связывает каждую упорядоченную карту с увеличенная ценность. Для заказанной карты ${\displaystyle m}$ с типом ключа ${\displaystyle K}$, функция сравнения ${\displaystyle <_{K}}$ на ${\displaystyle K}$ и тип значения ${\displaystyle V}$, увеличенное значение определяется на основе двух функций: база функция ${\displaystyle g:K\times V\mapsto A}$ и комбинировать функция ${\displaystyle f:A\times A\mapsto A}$, где ${\displaystyle A}$ это тип увеличиваемого значения. Базовая функция ${\displaystyle g}$ преобразует одну запись в ${\displaystyle m}$ на увеличенное значение, а функция объединения ${\displaystyle f}$ объединяет несколько дополнительных значений. Функция комбинирования ${\displaystyle f}$ требуется быть ассоциативный и иметь идентичность ${\displaystyle I}$ (т.е. ${\displaystyle A,f,I}$ образует моноид ). Расширяем определение ассоциативной функции ${\displaystyle f}$ следующим образом:

${\displaystyle f(\emptyset )=I}$${\displaystyle f(a)=a}$${\displaystyle f(a_{1},a_{2},\dots ,a_{n})=f(f(a_{1},a_{2},\dots ,a_{n-1}),a_{n})}$

Затем увеличенное значение упорядоченной карты ${\displaystyle m=\{(k_{1},v_{1}),(k_{2},v_{2}),\dots (k_{n},v_{n})\}}$ определяется следующим образом:

${\displaystyle A(m)=f(g(k_{1},v_{1}),g(k_{2},v_{2}),\dots ,g(k_{n},v_{n}))}$

Соответственно, расширенную карту можно формально определить как семикортежную ${\displaystyle \mathbb {AM} (K,<_{K},V,A,g,f,I)}$. Например, расширенная карта с целыми ключами и значениями, на которой расширенное значение определяется как сумма всех значений в карте, определяется как:

${\displaystyle M_{1}=\mathbb {AM} (\mathbb {Z} ,<_{\mathbb {Z} },\mathbb {Z} ,\mathbb {Z} ,(k,v)\mapsto v,+_{\mathbb {Z} },0)}$

Как абстрактный тип данных расширенная карта часто используется для моделирования проблем и служит абстракцией с полезным интерфейсом. Он разработан для поддержки быстрых сумм диапазонов, что означает быстрое возвращение увеличенного значения всех записей в определенном ключевом диапазоне.

Интерфейс

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

• aug_left${\displaystyle (m,k)}$: возвращает увеличенное значение всех записей в ${\displaystyle m}$ с ключами не более ${\displaystyle k}$.
• aug_right${\displaystyle (m,k)}$: возвращает увеличенное значение всех записей в ${\displaystyle m}$ с ключами не менее ${\displaystyle k}$.
• aug_left${\displaystyle (m,k_{1},k_{2})}$: возвращает увеличенное значение всех записей в ${\displaystyle m}$ с ключами в диапазоне ${\displaystyle [k_{1},k_{2}]}$.
• aug_val${\displaystyle (m)}$: возвращает увеличенное значение всех записей в ${\displaystyle m}$.

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

• aug_filter${\displaystyle (m,h)}$: возвращает все записи в ${\displaystyle m}$ удовлетворяющий показателю ${\displaystyle h:A\mapsto {\text{bool}}}$. Это применимо только когда ${\displaystyle h(a)\vee h(b)\Leftrightarrow h(f(a,b))}$. В этом случае функция aug_filter эквивалентна filter${\displaystyle m,h'}$, где ${\displaystyle h':K\times V\mapsto {\text{bool}}}$ и ${\displaystyle h(g(k,v))\Leftrightarrow h'(k,v)}$. Когда расширенная карта реализуется с использованием расширенных деревьев, эта функция может быть реализована асимптотически более эффективно, чем наивная реализация.
• aug_project${\displaystyle (g',f',m,k_{1},k_{2})}$: возвращает ${\displaystyle g'(aug\_range(m,k_{1},k_{2}))}$. Вот ${\displaystyle g':A\mapsto B}$, ${\displaystyle f':B\times B\mapsto B}$. Это требует ${\displaystyle (B,f',g'(I))}$ быть моноид и ${\displaystyle f'(g'(a),g'(b))=g'(f(a,b))}$. Эта функция полезна, когда расширенные значения

сами являются картами или другими большими структурами данных. Это позволяет проецировать расширенные значения на другой тип с помощью ${\displaystyle g'}$ (например, проецируйте расширенные значения со сложной структурой на такие значения, как их размеры), а затем суммируйте их по ${\displaystyle f'}$, и намного эффективнее, когда это применимо.

Реализация

Дополненные деревья

Расширенная карта может эффективно поддерживаться расширенными деревьями, где каждый узел дерева дополняется расширенным значением всех записей в его поддереве. Из-за ассоциативность функции комбайна ${\displaystyle f}$, увеличенное значение определенного дерева является фиксированным и не зависит от формы дерева, независимо от поворотов. В этом случае, комбинируя частичные суммы в узлах дерева, любая сумма диапазона может быть возвращена в ${\displaystyle O(\log n)}$ время на увеличенной карте размера ${\displaystyle n}$, предполагая, что оба ${\displaystyle f}$ и ${\displaystyle g}$ имеют постоянную стоимость. Для aug_filter древовидная структура использует то преимущество, что если увеличенное значение поддерева не удовлетворяет индикатору ${\displaystyle h}$, все дерево отбрасывается. В этом случае стоимость aug_filter составляет ${\displaystyle O(k\log(1+{\frac {n}{k}})}$ где ${\displaystyle k}$ - размер вывода. Для aug_project, когда все поддерево попадает в диапазон ${\displaystyle [k_{1},k_{2}]}$, его увеличенное значение может быть напрямую объединено с результатом, вместо того, чтобы требовать обхода дерева.

Префиксные структуры

Другая реализация - использовать префиксные структуры,^[2] в котором хранится увеличенное значение всех префиксов карты. Для определенной выше расширенной карты ${\displaystyle M_{1}}$, структура префикса представляет собой массив, в котором хранится сумма префиксов значений, отсортированных по их ключам. Структуры префикса особенно полезны для aug_left, но могут быть неэффективными для реализации других функций в интерфейсе расширенной карты. Это может быть полезно в некоторых геометрических алгоритмах.

Пример приложения

1D колющий запрос

Одномерный колющий запрос принимает в качестве входных данных набор интервалов на одномерной числовой строке. Запрос спрашивает, покрыта ли данная точка каким-либо входным интервалом или всеми интервалами, покрывающими эту точку. Для этой проблемы может быть определена расширенная карта, где ключи - это левые конечные точки всех интервалов, значения - соответствующие правые конечные точки, а увеличенное значение - максимальное значение всех правых конечных точек на карте. Более формально:

${\displaystyle M_{interval}=(\mathbb {R} ,<_{\mathbb {R} },\mathbb {R} ,\mathbb {R} ,(k,v)\mapsto v,{\text{max}}_{\mathbb {R} },-\infty )}$

Чтобы сообщить, покрывает ли какой-либо интервал заданную точку ${\displaystyle p}$, алгоритм запроса просто определяет, если aug_left${\displaystyle (p)>p}$. Это потому, что aug_left просматривает все интервалы, начинающиеся до ${\displaystyle p}$, и если максимальная правая конечная точка среди них превышает ${\displaystyle p}$, тогда ${\displaystyle p}$ При реализации с расширенными деревьями расширенная карта ${\displaystyle M_{\text{interval}}}$ это точно дерево интервалов. Построение такой расширенной древовидной структуры стоит трудозатрат. ${\displaystyle O(n\log n)}$, ${\displaystyle O(\log n)}$ параллельная глубина и ${\displaystyle O(n)}$ Космос. Каждый колющий запрос можно выполнить вовремя ${\displaystyle O(\log n)}$.

2D-запрос диапазона

Запрос 2D-диапазона принимает в качестве входных данных набор точек в двух измерениях. Запрос запрашивает все точки (или число) в определенном прямоугольнике, края которого параллельны оси. Для этой проблемы может быть определена расширенная карта, которая представляет собой двухуровневую вложенную структуру карты. На внешней карте хранятся все точки и отсортированы их по x-координатам. Расширенное значение внешней карты - это внутренняя расширенная структура карты, которая хранит тот же набор точек, что и внешняя карта, но сортирует их по их y-координатам. Увеличение внутренних деревьев накапливает количество точек, то есть увеличиваемое значение внутренней карты - это ее размер. Соответственно, функция объединения внешней карты состоит в объединении двух внутренних расширенных карт. Более формально:

${\displaystyle M_{inner}=(Y,<_{Y},X,\mathbb {Z} ,(k,v)\mapsto 1,+_{\mathbb {Z} },0)}$${\displaystyle M_{outer}=(X,<_{X},Y,M_{\text{inner}},(k,v)\mapsto M_{\text{inner}}.singleton(v,k),M_{\text{inner}}.{\text{union}},M_{\text{inner}}.{\text{empty}})}$

Здесь для простоты предположим, что все координаты уникальны. ${\displaystyle X}$ и ${\displaystyle Y}$ - это типы координат x и y. Чтобы ответить на запрос диапазона в прямоугольнике ${\displaystyle (x_{1},x_{2},y_{1},y_{2})}$, алгоритм запроса извлекает увеличенное значение внешней карты в диапазоне ключей ${\displaystyle [x_{1},x_{2}]}$, которая представляет собой внутреннюю карту всех желаемых точек, отсортированных по y-координатам. Следовательно, алгоритм берет другой aug_range на этой внутренней карте и получает результат. Для подсчета запросов алгоритм может использовать функцию aug_project.

${\displaystyle query(m,x_{1},x_{2},y_{1},y_{2})=M_{\text{outer}}.{\text{aug}}\_{\text{project}}(g',+_{\mathbb {Z} },m,x_{1},x_{2})}$${\displaystyle {\text{where }}g':M_{\text{inner}}\mapsto \mathbb {Z} ,g'(m')=M_{\text{inner}}.{\text{aug}}\_{\text{range}}(m,y_{1},y_{2})}$

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

Другие примеры

Другие примеры^[1][2] включать сегментные запросы, поиск по инвертированному индексу, прямоугольные запросы и т. д.

Поддержка Libaray

Параллельная реализация интерфейса расширенной карты предоставляется в библиотеке. PAM.

Заметки

использованная литература

1. Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2018), "PAM: параллельные дополненные карты", Материалы 23-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, ACM, стр. 290–304.
2. Blelloch, Guy E .; Сунь, Ихан (2018), «Запросы с параллельным диапазоном, сегментами и прямоугольниками с расширенными картами», Запросы с параллельным диапазоном, сегментом и прямоугольником с расширенными картами