4817
правок
Онлайн-алгоритм обновления списков: различия между версиями
Материал из WEGA
Онлайн-алгоритм обновления списков (посмотреть исходный код)
Версия от 07:27, 25 августа 2025
, 25 август→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 27: | Строка 27: | ||
Сначала рассмотрим алгоритмы Move-To-Front, Transpose и Frequency-Count. Отметим, что Move-To-Front и Transpose – стратегии без памяти, то есть им не требуется дополнительная память для принятия решения о том, куда переместить запрошенный элемент. Таким образом, с практической точки зрения они более привлекательны, чем Frequency-Count. Слейтор и Тарьян [16] проанализировали коэффициенты конкурентоспособности этих трех алгоритмов. | Сначала рассмотрим алгоритмы Move-To-Front, Transpose и Frequency-Count. Отметим, что Move-To-Front и Transpose – стратегии ''без памяти'', то есть им не требуется дополнительная память для принятия решения о том, куда переместить запрошенный элемент. Таким образом, с практической точки зрения они более привлекательны, чем Frequency-Count. Слейтор и Тарьян [16] проанализировали коэффициенты конкурентоспособности этих трех алгоритмов. | ||
| Строка 33: | Строка 33: | ||
Алгоритмы Transpose и Frequency-Count не являются c-конкурентными для любого константного c. | Алгоритмы Transpose и Frequency-Count не являются <math>c</math>-конкурентными для любого константного <math>c</math>. | ||
| Строка 39: | Строка 39: | ||
'''Теорема 2 [13]. Пусть A – детерминированный онлайн-алгоритм для задачи обновления списков. Если A c-конкурентен, то | '''Теорема 2 [13]. Пусть <math>A</math> – детерминированный онлайн-алгоритм для задачи обновления списков. Если A <math>c</math>-конкурентен, то <math>c \ge 2</math>.''' | ||
Интересным вопросом является рандомизация в задаче обновления списков. При наличии адаптивных соперников ни один рандомизированный онлайн-алгоритм обновления списков не может быть лучше чем 2-конкурентный, см. [6, 14]. Поэтому основное внимание уделяется алгоритмам в присутствии рассеянных соперников. Было предложено множество рандомизированных алгоритмов обновления списков [1, 2, 12, 14]. В следующих параграфах описываются два наиболее важных. Райнголд и др. [ ] предложили очень простой алгоритм, названный Bit. | Интересным вопросом является рандомизация в задаче обновления списков. При наличии адаптивных соперников ни один рандомизированный онлайн-алгоритм обновления списков не может быть лучше чем 2-конкурентный, см. [6, 14]. Поэтому основное внимание уделяется алгоритмам в присутствии рассеянных соперников. Было предложено множество рандомизированных алгоритмов обновления списков [1, 2, 12, 14]. В следующих параграфах описываются два наиболее важных. Райнголд и др. [14] предложили очень простой алгоритм, названный Bit. | ||
| Строка 51: | Строка 51: | ||
Райнголд и др. [ ] обобщили алгоритм Bit и доказали верхнюю границу | Райнголд и др. [14] обобщили алгоритм Bit и доказали верхнюю границу <math>\sqrt{3} \approx 1,73</math> относительно рассеянных соперников. Лучший рандомизированный алгоритм из известных на данный момент представляет собой комбинацию алгоритма Bit и детерминированного 2-конкурентного онлайнового алгоритма Timestamp, предложенного в [1]. | ||
'''Алгоритм «Временные метки» (Timestamp)''': вставляет запрашиваемый элемент, например x, перед первым элементом в списке, который предшествует x и который был запрошен не более одного раза с момента последнего запроса x. Если такого элемента нет или если x не был запрошен до сих пор, то позиция x остается без изменений. | '''Алгоритм «Временные метки» (Timestamp)''': вставляет запрашиваемый элемент, например <math>x</math>, перед первым элементом в списке, который предшествует <math>x</math> и который был запрошен не более одного раза с момента последнего запроса <math>x</math>. Если такого элемента нет или если <math>x</math> не был запрошен до сих пор, то позиция <math>x</math> остается без изменений. | ||
В качестве примера рассмотрим список из шести элементов, расположенных в порядке L: | В качестве примера рассмотрим список из шести элементов, расположенных в порядке <math>L: x_1 \to x_2 \to x_3 \to x_4 \to x_5 \to x_6</math>. Предположим, что алгоритм Timestamp должен обработать второй запрос к <math>x_5</math> в последовательности запросов <math>\sigma = x_5, x_2, x_2, x_3, x_1, x_1, x_5</math>. Элементы <math>x_3</math> и <math>x_4</math> были запрошены не более одного раза с момента последнего запроса к <math>x_5</math>, в то время как <math>x_1</math> и <math>x_2</math> были запрошены дважды. Таким образом, алгоритм Timestamp вставит <math>x_5</math> сразу перед <math>x_3</math> в списке. Комбинация алгоритмов Bit и Timestamp была предложена в работе [3]. | ||
'''Алгоритм «Комбинация» (Combination)''': с вероятностью | '''Алгоритм «Комбинация» (Combination)''': с вероятностью <math>\frac{4}{5}</math> алгоритм обрабатывает последовательность запросов, используя Bit, и с вероятностью <math>\frac{1}{5}</math> обрабатывает последовательность запросов, используя Timestamp. | ||
| Строка 69: | Строка 69: | ||
Амбюл и др. [4] представили нижнюю границу для рандомизированных алгоритмов обновления списков. | |||
'''Теорема 5 [4]. Пусть A – рандомизированный онлайн-алгоритм для задачи обновления списков. Если A c-конкурентен относительно любого рассеянного соперника, то с > 1,50084.''' | '''Теорема 5 [4]. Пусть A – рандомизированный онлайн-алгоритм для задачи обновления списков. Если A <math>c</math>-конкурентен относительно любого рассеянного соперника, то с > 1,50084.''' | ||
Используя методы теории обучения, Блам и др. [9] предложили рандомизированный онлайн-алгоритм, который при любом | Используя методы теории обучения, Блам и др. [9] предложили рандомизированный онлайн-алгоритм, который при любом <math>\epsilon > 0</math> является (1,6 + <math>\epsilon</math>)-конкурентным и в то же время (1 + <math>\epsilon</math>)-конкурентным относительно оффлайнового алгоритма, ограниченного обработкой последовательности запросов со статическим списком. | ||
До сих пор в данной статье рассматривались онлайновые алгоритмы. В оффлайновом варианте задачи обновления списков вся последовательность запросов | До сих пор в данной статье рассматривались онлайновые алгоритмы. В оффлайновом варианте задачи обновления списков вся последовательность запросов <math>\sigma</math> известна заранее. Амбюл [3] показал, что оффлайновый вариант является NP-трудным. | ||
Райнголд и др. [ ] исследовали расширенную модель затрат, названную P-моделью, для задачи обновления списков. В модели | Райнголд и др. [14] исследовали расширенную модель затрат, названную P-моделью, для задачи обновления списков. В модели <math>P^d</math> нет бесплатных обменов, а каждый платный обмен стоит <math>d</math>. Рейнгольд и коллеги проанализировали детерминированные и рандомизированные стратегии в этой модели. | ||
Многие из концепций, показанных для самоорганизующихся линейных списков, могут быть распространены на бинарные деревья поиска. Наиболее популярной версией самоорганизующихся бинарных деревьев поиска являются косые деревья [https://ru.wikipedia.org/wiki/Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE], представленные Слейтором и Тарьяном; см. [17]. | Многие из концепций, показанных для самоорганизующихся линейных списков, могут быть распространены на бинарные деревья поиска. Наиболее популярной версией самоорганизующихся бинарных деревьев поиска являются ''косые деревья'' [https://ru.wikipedia.org/wiki/Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE], представленные Слейтором и Тарьяном; см. [17]. | ||
Что касается истории задачи об обновлении списков, то до появления сравнительного анализа алгоритмы обновления списков изучались в сценариях, где последовательности запросов формируются в соответствии с вероятностными распределениями. Асимптотические ожидаемые затраты, понесенные онлайновым алгоритмом при обработке одного запроса, сравнивались с соответствующими затратами, понесенными при оптимальном статическом упорядочивании. Существует большой объем литературы по этой теме. Чанг и др. [ ] показали, что для любого распределения асимптотическая стоимость обработки алгоритма Move-To-Front не более чем в | Что касается истории задачи об обновлении списков, то до появления сравнительного анализа алгоритмы обновления списков изучались в сценариях, где последовательности запросов формируются в соответствии с вероятностными распределениями. Асимптотические ожидаемые затраты, понесенные онлайновым алгоритмом при обработке одного запроса, сравнивались с соответствующими затратами, понесенными при оптимальном статическом упорядочивании. Существует большой объем литературы по этой теме. Чанг и др. [11] показали, что для любого распределения асимптотическая стоимость обработки алгоритма Move-To-Front не более чем в <math>\frac{\pi}{2}</math> раз превышает стоимость обработки оптимального упорядочения. | ||
Эта граница является строгой. Ривест [ ] определил распределения, на которых Transpose работает лучше, чем Move-To-Front. | Эта граница является строгой. Ривест [15] определил распределения, на которых Transpose работает лучше, чем Move-To-Front. | ||
== Применение == | == Применение == | ||
