Самоорганизующийся список
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( январь 2024 г. ) |
— Самоорганизующийся список это список , который меняет порядок своих элементов на основе некоторой самоорганизующейся эвристики для уменьшения среднего времени доступа . Цель самоорганизующегося списка — повысить эффективность линейного поиска за счет перемещения более часто используемых элементов в начало списка. Самоорганизующийся список в лучшем случае обеспечивает почти постоянное время доступа к элементам. Самоорганизующийся список использует алгоритм реорганизации для адаптации к различным распределениям запросов во время выполнения.
История
[ редактировать ]Концепция самоорганизующихся списков уходит корнями в идею организации деятельности записей в файлах, хранящихся на дисках или лентах. [1] Одно из часто цитируемых обсуждений самоорганизующихся файлов и списков принадлежит Кнуту. [2] Джон Маккейб провел первый алгоритмический анализ сложности стратегии «Перемещение вперед» (MTF), при которой элемент перемещается в начало списка после доступа к нему. [3] Он проанализировал среднее время, необходимое для того, чтобы случайно упорядоченный список оказался в оптимальном порядке. Оптимальным упорядочением списка является тот, при котором элементы упорядочены в списке по вероятности того, с какой они понадобятся, причем первым является элемент, к которому чаще всего обращаются. Оптимальный порядок может быть неизвестен заранее, а также может меняться со временем.
Маккейб представил стратегию транспонирования, при которой доступный элемент заменяется элементом, стоящим перед ним в списке. Он выдвинул гипотезу, что в среднем случае транспонирование работает по крайней мере так же хорошо, как MTF, при достижении оптимального порядка записей в пределе. Эту гипотезу позже доказал Ривест. [4] Маккейб также отметил, что с помощью эвристики транспозиции или MTF можно достичь оптимального порядка записей, даже если эвристика применяется только при каждом N-м доступе, и что можно выбрать значение N, которое будет отражать относительную стоимость перемещения записей с помощью эвристики транспозиции или MTF. ценность более быстрого достижения оптимального порядка. Были внесены дальнейшие улучшения и алгоритмы, предложенные исследователями, в том числе: Ривестом, Тененбаумом и Немесом, Кнутом, Бентли и МакГеочом (например, анализ наихудшего случая для самоорганизующейся эвристики последовательного поиска).
Приложения
[ редактировать ]Самоорганизующийся список использует эвристику самоорганизации — алгоритм , который изменяет структуру данных , например связанный список, в ответ на использование структуры данных.
Примеры самоорганизующихся эвристик включают в себя:
- На передний план (или «Переместить наверх») — часто используемые или недавно использованные места, информация находится вверху, поэтому ее можно быстро найти без необходимости просматривать весь список.
- самообучения Список частот (или «Упорядочить по частоте доступа») — переупорядочивает список опций в меню графического интерфейса так, чтобы верхние из них были опциями, которые чаще всего выбираются пользователем.
- Повторно вставьте в случайное положение
- Перейти назад — используется для организации списка зеркальных серверов , чтобы после использования сервера для загрузки он перемещался в конец очереди , чтобы пользователь не мог выбрать его снова.
Примечания
[ редактировать ]- ^ Беккер, Дж.; Хейс, Р.М. (1963), Хранение и поиск информации: инструменты, элементы, теории , Нью-Йорк: Wiley
- ^ Кнут, Дональд (1998), Сортировка и поиск , Искусство компьютерного программирования , том. 3 (Второе изд.), Аддисон-Уэсли, с. 402, ISBN 978-0-201-89685-5
- ^ Маккейб, Джон (1965), «О последовательных файлах с перемещаемыми записями», Operations Research , 13 (4): 609–618, doi : 10.1287/opre.13.4.609
- ^ Ривест, Рональд (1976), «О самоорганизующейся эвристике последовательного поиска», Communications of the ACM , 19 (2): 63–67, doi : 10.1145/359997.360000 , S2CID 498886
Ссылки
[ редактировать ]- Самоорганизация (PDF) , 2004 г., заархивировано из оригинала (PDF) 14 апреля 2012 г. , получено 13 декабря 2011 г.
- NIST DADS Запись
- Дроздек, Структуры данных и алгоритмы в Java Третье издание.
- Амер, Абдельрехман; Б. Джон Ооммен (2006), Списки в списках: структура самоорганизующихся списков в средах с локальностью ссылок , Конспекты лекций по информатике, том. 4007, номер домена : 10.1007/11764298 , ISBN 978-3-540-34597-8