Аноним

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

Материал из WEGA
м
Строка 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'' в результате <math>\tau</math> раундов коммуникации, где в каждом раунде Алиса посылает <math>m_A</math> бит, а Боб отвечает с помощью <math>m_B</math> бит.
'''Коммуникативные игры''': предположим, что у Алисы есть запрос ''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].
Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна в случаях, когда важна эффективность. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [7].


== Основные результаты ==
== Основные результаты ==
4551

правка