4817
правок
Нижняя граница для динамической связности: различия между версиями
Материал из WEGA
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 11:27, 18 августа 2025
, 18 август→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 58: | Строка 58: | ||
== Основные результаты == | == Основные результаты == | ||
''' | '''Представление об иерархиях''' | ||
'''Эпохи''' | '''Эпохи''' | ||
| Строка 84: | Строка 84: | ||
''' | '''Временные иерархии''' | ||
Несмотря на значительное усовершенствование техники нижних границ, нижняя граница <math>\Omega(lg \; n/lg \; lg \; n)</math> не была улучшена до 2004 года. Тогда Петрашку и Демейн [6] показали оптимальное ограничение <math>t_q^{\Sigma} lg(t_u^{\Sigma}/t_q^{\Sigma}) = \Omega(lg \; n)</math>, что означает <math>max \{ t_u^{\Sigma}, t_q^{\Sigma} \} = \Omega(lg \; n)</math>. Для простоты нижеследующее обсуждение пренебрегает этим компромиссом и просто набрасывает нижнюю границу <math>\Omega(lg \; n)</math>. | Несмотря на значительное усовершенствование техники нижних границ, нижняя граница <math>\Omega(lg \; n/lg \; lg \; n)</math> не была улучшена до 2004 года. Тогда Петрашку и Демейн [6] показали оптимальное ограничение <math>t_q^{\Sigma} lg(t_u^{\Sigma}/t_q^{\Sigma}) = \Omega(lg \; n)</math>, что означает <math>max \{ t_u^{\Sigma}, t_q^{\Sigma} \} = \Omega(lg \; n)</math>. Для простоты нижеследующее обсуждение пренебрегает этим компромиссом и просто набрасывает нижнюю границу <math>\Omega(lg \; n)</math>. | ||
| Строка 97: | Строка 97: | ||
Теперь рассмотрим два «братских» поддерева, каждое из которых содержит <math>k</math> операций. Предполагается, что <math>k/2</math> обновлений в левом поддереве и <math>k/2</math> запросов в правом поддереве будут чередоваться в пространстве индексов. Таким образом, запросы в правом поддереве запрашивают | Теперь рассмотрим два «братских» поддерева, каждое из которых содержит <math>k</math> операций. Предполагается, что <math>k/2</math> обновлений в левом поддереве и <math>k/2</math> запросов в правом поддереве будут чередоваться в пространстве индексов. Таким образом, запросы в правом поддереве запрашивают <math>\Omega(k)</math> различных частных сумм обновлений в левом поддереве. Таким образом, правому поддереву «нужно» <math>\Omega(k \delta)</math> бит информации о левом поддереве, и эта информация может поступать только из ячеек, записанных в левом поддереве и прочитанных в правом. Отсюда следует нижняя граница в <math>\Omega(k)</math>) зондов, связанных с родителем «братских» поддеревьев. Эта граница линейна по числу листьев, так что, суммируя по всему дереву, мы получаем полную нижнюю границу <math>\Omega(n \; lg \; n)</math>, или стоимость <math>\Omega(lg \; n)</math> на операцию. | ||
'''Оптимальное построение эпох''' | '''Оптимальное построение эпох''' | ||
Как ни удивительно, но Петрашку и | Как ни удивительно, но Петрашку и Тарнице [7] удалось воспроизвести оптимальный компромисс теоремы 1 с минимальными изменениями рассуждений об эпохах. В старой версии этих рассуждений информация, раскрываемая эпохами <math>1, ..., i - 1</math> об эпохе <math>i</math>, ограничивалась количеством ячеек, записанных в эти эпохи. Ключевая идея заключается в том, что не менее удачным ограничением является количество ячеек, прочитанных в эпохи <math>1, ..., i - 1</math> и записанных в эпоху <math>i</math>. | ||
В принципе, все операции чтения ячеек из эпохи i - 1 могут читать данные из эпохи i, что делает эти две границы идентичными. Однако можно рандомизировать построение эпох, вставляя запрос после непредсказуемого количества обновлений. Такая рандомизация «сглаживает» распределение эпох, из которых считываются ячейки, то есть запрос считывает O( | В принципе, все операции чтения ячеек из эпохи <math>i - 1</math> могут читать данные из эпохи <math>i</math>, что делает эти две границы идентичными. Однако можно рандомизировать построение эпох, вставляя запрос после непредсказуемого количества обновлений. Такая рандомизация «сглаживает» распределение эпох, из которых считываются ячейки, то есть запрос считывает <math>O(t_q^{\Sigma}/log_r \; n)</math> ячеек из каждой эпохи, что выходит за рамки случайности в построении эпохи. Тогда <math>O(r^{i - 1})</math>обновлений в эпохи <math>1, ..., i - 1</math> читают только <math>O(r^{i-1} \cdot t_u^{\Sigma}/log_r \; n)</math> ячеек из эпохи <math>i</math>. Этой информации недостаточно, если <math>r \gg t_u^{\Sigma}/log_r \; n = \Theta(t_u^{\Sigma}/t_q^{\Sigma})</math>, из чего следует, что <math>t_q^{\Sigma} = \Omega(log_r \; n) = Omega(lg \; n/lg(t_u^{\Sigma}/t_q^{\Sigma}))</math>. | ||
| Строка 118: | Строка 118: | ||
Исходя из вышесказанного, задача состоит в том, чтобы доказать хорошие нижние границы для суммы даже в недетерминистской модели. Недетерминизм поколебал представление о том, что при анализе эпохи i имеют значение только запросы к ячейкам эпохи i. Проблема в том, что запрос может не знать, какие из его зондирований действительно относятся к эпохе i. Зонд, считывающий ячейку из предыдущей эпохи, предоставляет по крайней мере некоторую информацию об эпохе i: ни одно обновление в эту эпоху не решило перезаписать клетку. Ранее это не было проблемой, поскольку целью было только исключить случай, когда в эпоху i существует ноль зондирований. Теперь, однако, различные потоки могут зондировать любую ячейку в памяти, и невозможно определить, какие потоки на самом деле избегают зондирования чего-либо в эпоху i. Другими словами, между эпохой i и запросом существует скрытый канал связи, в котором эпоха может использовать выбор того, какие ячейки записывать, чтобы передать информацию запросу. | Исходя из вышесказанного, задача состоит в том, чтобы доказать хорошие нижние границы для суммы даже в недетерминистской модели. Недетерминизм поколебал представление о том, что при анализе эпохи i имеют значение только запросы к ячейкам эпохи <math>i</math>. Проблема в том, что запрос может не знать, какие из его зондирований действительно относятся к эпохе <math>i</math>. Зонд, считывающий ячейку из предыдущей эпохи, предоставляет по крайней мере некоторую информацию об эпохе <math>i</math>: ни одно обновление в эту эпоху не решило перезаписать клетку. Ранее это не было проблемой, поскольку целью было только исключить случай, когда в эпоху <math>i</math> существует ноль зондирований. Теперь, однако, различные потоки могут зондировать любую ячейку в памяти, и невозможно определить, какие потоки на самом деле избегают зондирования чего-либо в эпоху <math>i</math>. Другими словами, между эпохой <math>i</math> и запросом существует скрытый канал связи, в котором эпоха может использовать выбор того, какие ячейки записывать, чтобы передать информацию запросу. | ||
Существует две основные стратегии для работы с алгоритмами недетерминированных запросов. Хасфельдт и Раухе [4] приводят доказательство, основанное на некоторых интересных наблюдениях о комбинаторике недетерминированных запросов. Петрашку и Демейн [6] используют силу самого недетерминизма для вывода небольшого сертификата, исключающего бесполезные зондирования ячеек. Из последнего результата вытекает оптимальная нижняя граница Теоремы 1 для testsum и, следовательно, логарифмическая нижняя граница для динамической связности. | Существует две основные стратегии для работы с алгоритмами недетерминированных запросов. Хасфельдт и Раухе [4] приводят доказательство, основанное на некоторых интересных наблюдениях о комбинаторике недетерминированных запросов. Петрашку и Демейн [6] используют силу самого недетерминизма для вывода небольшого сертификата, исключающего бесполезные зондирования ячеек. Из последнего результата вытекает оптимальная нижняя граница Теоремы 1 для '''testsum''' и, следовательно, логарифмическая нижняя граница для динамической связности. | ||
'''Альтернативные истории''' | '''Альтернативные истории''' | ||
Описанная выше схема опирается на фиксацию всех обновлений в эпохи, отличные от i, к среднему значению и утверждение, что ответ на запрос все равно имеет большую вариативность, зависящую от обновлений в эпоху i. Это верно для задач агрегирования, но не для задач поиска. Если искомый элемент найден с равной вероятностью в любой эпохе, то фиксация всех остальных эпох делает эпоху i нерелевантной с вероятностью 1 - 1/(logr n). | Описанная выше схема опирается на фиксацию всех обновлений в эпохи, отличные от <math>i</math>, к среднему значению и утверждение, что ответ на запрос все равно имеет большую вариативность, зависящую от обновлений в эпоху <math>i</math>. Это верно для задач агрегирования, но не для задач поиска. Если искомый элемент найден с равной вероятностью в любой эпохе, то фиксация всех остальных эпох делает эпоху <math>i</math> нерелевантной с вероятностью 1 - 1/(logr n). | ||
Олстрап и др. [] предложили очень интересное усовершенствование этой техники, доказав нижние границы Q (lg n/ lg lg n) для впечатляющей коллекции задач поиска. Интуитивно их идея заключается в рассмотрении O(logr n) альтернативных историй обновлений, выбранных независимо друг от друга случайным образом. Эпоха i релевантна хотя бы в одной из историй с константной вероятностью. С другой стороны, даже если известно, что эпохи с 1 по i - 1 узнали об эпохе i во всех историях, ответить на случайный запрос все равно сложно. | Олстрап и др. [] предложили очень интересное усовершенствование этой техники, доказав нижние границы Q (lg n/ lg lg n) для впечатляющей коллекции задач поиска. Интуитивно их идея заключается в рассмотрении O(logr n) альтернативных историй обновлений, выбранных независимо друг от друга случайным образом. Эпоха <math>i</math> релевантна хотя бы в одной из историй с константной вероятностью. С другой стороны, даже если известно, что эпохи с 1 по i - 1 узнали об эпохе <math>i</math> во всех историях, ответить на случайный запрос все равно сложно. | ||
