4430
правок
Поиск предков: различия между версиями
Материал из WEGA
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим упорядоченную совокупность 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> – время обновления. | Рассмотрим упорядоченную совокупность U и множество T <math> \subset</math> U, |T| = n. Целью является предварительная обработка T таким образом, чтобы можно было эффективно отвечать на следующий запрос: пусть задан элемент <math>x \in U</math>, требуется найти предка <math>x</math>, т. е. <math>max \{ y \in T | y < x \}</math>. Также можно рассмотреть динамическую задачу, когда элементы вставляются в T и удаляются из него. Обозначим за <math>t_q</math> время выполнения запроса, а за <math>t_u</math> – время обновления. | ||
| Строка 28: | Строка 28: | ||
'''Коммуникативные игры''': предположим, что у Алисы есть запрос ''x'', а у Боба – множество T. Они пытаются найти предка | '''Коммуникативные игры''': предположим, что у Алисы есть запрос ''x'', а у Боба – множество T. Они пытаются найти предка <math>x</math> с помощью <math>\tau</math> раундов коммуникации, где в каждом раунде Алиса посылает <math>m_A</math> бит, а Боб отвечает с использованием <math>m_B</math> бит. | ||
Этот подход может имитировать модель клеточного зонда, когда <math>m_B = b</math>, а <math>m_A</math> – логарифм от объема памяти. Тогда <math>\tau \le t_q</math>, и можно использовать коммуникационную сложность для получения нижних границ клеточного зонда. | Этот подход может имитировать модель клеточного зонда, когда <math>m_B = b</math>, а <math>m_A</math> – логарифм от объема памяти. Тогда <math>\tau \le t_q</math>, и можно использовать коммуникационную сложность для получения нижних границ клеточного зонда. | ||
Внешняя память: единицей доступа является страница, содержащая B слов по <math>\ell</math> бит каждое. B-деревья решают задачу со временем запроса и обновления <math>O(log_B \; n)</math>; этого также можно достичь, не обращая внимания на значение B ''(см. [[B-деревья без явного задания параметров кэша]])''. Модель клеточного зонда с <math>b = B \cdot \ell</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-машины, в котором допустимыми операциями являются функции, имеющие постоянную глубину, | '''<math>AC^0</math>-RAM''': это вариант пословной RAM-машины, в котором допустимыми операциями являются функции, имеющие постоянную глубину, с неограниченными схемами объединения по входу. Это исключает умножение из стандартного набора операций. | ||
| Строка 42: | Строка 42: | ||
Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна, когда эффективность | Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна в ситуациях, когда важна эффективность. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [7]. | ||
== Основные результаты == | == Основные результаты == | ||
Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи | Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи на моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры. | ||
| Строка 60: | Строка 60: | ||
\end{cases}</math> | \end{cases}</math> | ||
Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время <math>t_q + O(S/n)</math>. Таким образом, помимо нахождения элемента за один запрос | Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства 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>. | Нижние границы справедливы для мощной модели клеточного зонда и выполняются даже для рандомизированных алгоритмов. Когда <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>. | ||
| Строка 99: | Строка 99: | ||
Полный результат Петрашку и Торупа [ ] представляет собой компромисс (1). Первоначально он был показан только для детерминированных алгоритмов запросов, но со временем был распространен и на нижнюю границу рандомизированного алгоритма [16]. Среди удивительных последствий этого результата было то, что классический поиск ван Эмде Боаса является оптимальным для почти линейного объема памяти (и, следовательно, для динамических структур данных), тогда как при наличии квадратичного объема памяти он может уступать технике Бима и Фич. | Полный результат Петрашку и Торупа [15] представляет собой компромисс (1). Первоначально он был показан только для детерминированных алгоритмов запросов, но со временем был распространен и на нижнюю границу рандомизированного алгоритма [16]. Среди удивительных последствий этого результата было то, что классический поиск ван Эмде Боаса является оптимальным для почти линейного объема памяти (и, следовательно, для динамических структур данных), тогда как при наличии квадратичного объема памяти он может уступать технике Бима и Фич. | ||
С технической точки зрения идея [ ] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается ''отклонить'' большую часть запросов, прежде чем приступить к зондированию. | С технической точки зрения идея работы [15] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается ''отклонить'' большую часть запросов, прежде чем приступить к зондированию. | ||
| Строка 110: | Строка 110: | ||
Поскольку блоки размером | Поскольку блоки размером <math>w^{(O(1)}</math> могут обрабатываться деревьями слияния за константное время, из этого следует, что коэффициенты w объема памяти не имеют значения. Более экстремальное применение этой идеи дают ''экспоненциальные деревья'' [3]. Здесь блоки имеют размер <math>\Theta(n^{1 - \gamma})</math>, где <math>\gamma</math> – достаточно небольшая константа. Блоки обрабатываются рекурсивно таким же образом, что дает в итоге O(lg lg n) уровней. Если начальное время запроса не меньше <math>t_q \ge lg^{\varepsilon} \; n</math>, то время запроса на каждом уровне уменьшается в геометрической прогрессии, так что общее время растет только на постоянный коэффициент. Однако при соответствующем выборе <math>\gamma</math> любое полиномиальное требование к памяти сводится к линейному. Кроме того, экспоненциальное дерево может быть обновлено за время <math>O(t_q</math>), даже если исходная структура данных была статической. | ||
== Применение == | == Применение == | ||
Возможно, наиболее важным применением задачи поиска предков является просмотр информации об IP-адресах. Эту задачу решают маршрутизаторы для каждого пакета в Интернете, когда выбирают, в какую подсеть направить пакет. Таким образом, это, вероятно, самая часто выполняемая алгоритмическая задача в мире. Формально это запрос о поиске в интервале, который эквивалентен поиску предка в статическом случае [ ]. Поскольку при решении этой задачи эффективность | Возможно, наиболее важным применением задачи поиска предков является просмотр информации об IP-адресах. Эту задачу решают маршрутизаторы для каждого пакета в Интернете, когда выбирают, в какую подсеть направить пакет. Таким образом, это, вероятно, самая часто выполняемая алгоритмическая задача в мире. Формально это ''запрос о поиске в интервале'', который эквивалентен поиску предка в статическом случае [9]. Поскольку при решении этой задачи эффективность исключительно важна, необходимо отметить, что самые быстро внедряемые программные решения [7] используют стратегии целочисленного поиска (не основанные на сравнении), как и предсказывают теоретические результаты. | ||
Кроме того, поиск предков широко используется в структурах данных при редукции задач к пространству рангов. Пусть имеется множество T. Часто требуется переразметить его в более простое | Кроме того, поиск предков широко используется в структурах данных при редукции задач к ''пространству рангов''. Пусть имеется множество T. Часто требуется переразметить его в более простое {1, ..., n} «пространство рангов», сохранив при этом отношения порядка. Если новые значения представляются динамически, возникает необходимость в запросе на поиск предка. Вот несколько наглядных примеров: | ||
• При запросах в ортогональном диапазоне поддерживается набор точек в | • При запросах в ортогональном диапазоне поддерживается набор точек в <math>U^d</math> и выполняются запросы на точки в некотором прямоугольнике <math>[a_1, b_1] \times \cdot \cdot \cdot \times [a_d, b_d]</math>. Хотя границы обычно растут экспоненциально с увеличением размерности, зависимость от совокупности можно факторизовать. Во время запроса сначала выполняются 2d запросов предков, преобразующих совокупность в <math>\{1, ..., n \}^d</math>. | ||
• Чтобы сделать структуры данных с указателями постоянными [8], исходящая ссылка заменяется вектором указателей, каждый из которых действителен в течение некоторого периода времени. Решение о том, по какой ссылке идти (учитывая время запроса), представляет собой задачу поиска предка. | • Чтобы сделать структуры данных с указателями постоянными [8], исходящая ссылка заменяется вектором указателей, каждый из которых действителен в течение некоторого периода времени. Решение о том, по какой ссылке идти (учитывая время запроса), представляет собой задачу поиска предка. | ||
Наконец, любопытно отметить, что нижние границы в задаче поиска предка оказываются применимы, путем редукции, ко всем описанным выше приложениям. Чтобы сделать такие редукции возможными, нижние границы на самом деле показаны для более слабой задачи поиска цвета предка. В этой задаче значения множества T окрашены в красный или синий цвет, и запрос должен найти только цвет предшественника. | Наконец, любопытно отметить, что нижние границы в задаче поиска предка оказываются применимы, путем редукции, ко всем описанным выше приложениям. Чтобы сделать такие редукции возможными, нижние границы на самом деле показаны для более слабой задачи ''поиска цвета предка''. В этой задаче значения множества T окрашены в красный или синий цвет, и запрос должен найти только цвет предшественника. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Подход к реализации деревьев слияния с инструкциями | Подход к реализации деревьев слияния с инструкциями <math>AC^0</math> известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины <math>AC^0</math>? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций <math>AC^0</math>? | ||
Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить | Можно ли сделать время обновления детерминированным при решении динамической задачи? В частности, можно ли реализовать поиск ван Эмде Боаса с быстрым детерминированным обновлением? Это очень интересная задача, находящая применение в детерминированных словарях [14]. Кроме того, можно ли детерминированным образом обновлять узлы слияния за константное время? Атомарные кучи [11] достигают этого результата при поиске только среди <math>(lg \; n)^{\varepsilon}</math> элементов, а не <math>b^{\varepsilon}</math>. | ||
Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить <math>t_u = o(t_q)</math>, сохранив при этом эффективное время запроса? | |||
== См. также == | == См. также == | ||
