Поиск предков: различия между версиями

Рассмотрим упорядоченную совокупность U и множество T <math> \subset</math> U, |T| = n. Целью является предварительная обработка T таким образом, чтобы можно было эффективно отвечать на следующий запрос: пусть задан элемент <math>x \in U</math>, требуется найти предка x, т. е. <math>max \{ y \in T | y < x \}</math>. Также можно рассмотреть динамическую задачу, когда элементы вставляются в T и удаляются из него. Обозначим за <math>t_q</math> время запроса, а за <math>t_u</math> – время обновления.

'''Коммуникативные игры''': предположим, что у Алисы есть запрос ''x'', а у Боба – множество T. Они пытаются найти предка ''x'' в результате <math>\tau</math> раундов коммуникации, где в каждом раунде Алиса посылает <math>m_A</math> бит, а Боб отвечает с помощью <math>m_B</math> бит.

Внешняя память: единицей доступа является страница, содержащая B слов по <math>\ell</math> бит каждое. B-деревья решают задачу со временем запроса и обновления <math>O(log_B \; n)</math>; этого также можно достичь, не обращая внимания на значение B ''(см. [[B-деревья без явного задания параметров кэша]])''. Модель клеточного зонда с <math>b = B \cdot \ell</math> сильнее данной модели.

'''<math>AC^0</math>-RAM''': это вариант пословной RAM-машины, в котором допустимыми операциями являются функции, имеющие постоянную глубину, неограниченные схемы объединения по входу. Это исключает умножение из стандартного набора операций.

Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна, когда эффективность особенно важна. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [7].

Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи в моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры.

Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время <math>t_q + O(S/n)</math>. Таким образом, помимо нахождения элемента за один запрос предка, обновления изменяют минимальную часть структуры данных.

Нижние границы справедливы для мощной модели клеточного зонда и выполняются для рандомизированных алгоритмов. Когда <math>S \ge n^{1 + \varepsilon}</math>, оптимальный компромисс для коммуникативных игр совпадает с (1). Заметим, что случай <math>S = n^{1 + o(1)}</math> практически устраняется при сведении к коммуникационной сложности, поскольку сообщения Алисы зависят только от lg S. Таким образом, нет асимптотической разницы между <math>S = O(n)</math> и, скажем, <math>S = O(n^2)</math>.

Возможно, наиболее важным применением задачи поиска предков является просмотр информации об IP-адресах. Эту задачу решают маршрутизаторы для каждого пакета в Интернете, когда выбирают, в какую подсеть направить пакет. Таким образом, это, вероятно, самая часто выполняемая алгоритмическая задача в мире. Формально это запрос о поиске в интервале, который эквивалентен поиску предка в статическом случае [ ]. Поскольку при решении этой задачи эффективность исключитель важна, необходимо отметить, что самые быстро внедряемые программные решения [ ] используют стратегии целочисленного поиска (не основанные на сравнении), как и предсказывают теоретические результаты.

Кроме того, поиск предков широко используется в структурах данных при редукции задач к пространству рангов. Пусть имеется множество T. Часто требуется переразметить его в более простое f1...: ; ng («пространство рангов»), сохранив при этом отношения порядка. Если новые значения представляются динамически, возникает необходимость в запросе на поиск предка. Вот несколько наглядных примеров:

• При запросах в ортогональном диапазоне поддерживается набор точек в Ud и выполняются запросы на точки в некотором прямоугольнике [a1; b1] x - - - x [ad; bd]. Хотя границы обычно растут экспоненциально с увеличением размерности, зависимость от совокупности можно факторизовать. Во время запроса сначала выполняются 2d запросов предков, преобразующих совокупность в 1...nd.

Наконец, любопытно отметить, что нижние границы в задаче поиска предка оказываются применимы, путем редукции, ко всем описанным выше приложениям. Чтобы сделать такие редукции возможными, нижние границы на самом деле показаны для более слабой задачи поиска цвета предка. В этой задаче значения множества T окрашены в красный или синий цвет, и запрос должен найти только цвет предшественника.

Подход к реализации деревьев слияния с инструкциями AC0 известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины AC0? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций AC0?

Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить tu = o(tq), сохранив при этом эффективное время запроса?