4446
правок
Поиск предков: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
'''Бинарные деревья поиска''': поиск предков является одним из фундаментальных мотивов для бинарных деревьев поиска. В рамках этой ограничивающей модели можно рассчитывать на оптимальный (конкурентный) алгоритм. Попытки достичь этого описаны в работе ''O(log log n)-конкурентные бинарные деревья поиска (2004; Demaine, Harmon, Iacono, P˘atra¸scu)''. | '''Бинарные деревья поиска''': поиск предков является одним из фундаментальных мотивов для бинарных деревьев поиска. В рамках этой ограничивающей модели можно рассчитывать на оптимальный (конкурентный) алгоритм. Попытки достичь этого описаны в работе ''[https://link.springer.com/referenceworkentry/10.1007/978-3-642-27848-8_263-2| O(log log n)-конкурентные бинарные деревья поиска (2004; Demaine, Harmon, Iacono, P˘atra¸scu)]''. | ||
| Строка 22: | Строка 22: | ||
Традиционно принято считать, что совокупность имеет вид <math>U = \{ 1, ..., 2^{\ell} \}</math>, т. е. мы имеем дело с <math>\ell</math>-битными целыми числами. Представление с плавающей точкой было разработано таким образом, что порядок сохраняется, когда значения интерпретируются как целые числа, поэтому любой алгоритм будет работать и для <math>\ell</math>-битных чисел с плавающей точкой. | Традиционно принято считать, что совокупность имеет вид <math>U = \{ 1, ..., 2^{\ell} \}</math>, т. е. мы имеем дело с <math>\ell</math>-битными целыми числами. Представление с плавающей точкой было разработано таким образом, что порядок сохраняется, когда значения интерпретируются как целые числа, поэтому любой алгоритм будет работать и для <math>\ell</math>-битных чисел с плавающей точкой. | ||
Стандартное трансдихотомическое предположение состоит в том, что <math>b = \ell</math>, так что входное целое число представляется в виде слова. Из этого следует <math>b \ge lg \; n</math>. | Стандартное ''трансдихотомическое'' предположение состоит в том, что <math>b = \ell</math>, так что входное целое число представляется в виде слова. Из этого следует <math>b \ge lg \; n</math>. | ||
| Строка 28: | Строка 28: | ||
Коммуникативные игры: предположим, что у Алисы есть запрос x, а у Боба – множество T. Они пытаются найти предка x в результате | '''Коммуникативные игры''': предположим, что у Алисы есть запрос ''x'', а у Боба – множество T. Они пытаются найти предка ''x'' в результате <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>, и можно использовать коммуникационную сложность для получения нижних границ клеточного зонда. | ||
Внешняя память: единицей доступа является страница, содержащая B слов по | Внешняя память: единицей доступа является страница, содержащая 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-машины, в котором допустимыми операциями являются функции, имеющие постоянную глубину, неограниченные схемы объединения по входу. Это исключает умножение из стандартного набора операций. | |||
'''RAMBO''': это вариант пословной RAM-машины с нестандартной памятью, в котором биты в словах памяти могут перекрываться. В статическом случае это по сути эквивалентно обычной RAM-машине; в динамическом случае обновление может происходить быстрее из-за перекрытия слов [5]. | |||
Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна, когда эффективность особенно важна. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [7]. | |||
Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна, когда эффективность особенно важна. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [ ]. | |||
== Основные результаты == | == Основные результаты == | ||
