Самоорганизующийся список - Self-organizing list

А самоорганизующийся список это список который меняет порядок элементов на основе некоторых самоорганизующаяся эвристика улучшить средний время доступа. Целью самоорганизующегося списка является повышение эффективности линейного поиска за счет перемещения наиболее часто используемых элементов в начало списка. Самоорганизующийся список в лучшем случае обеспечивает почти постоянное время доступа к элементам. В самоорганизующемся списке используется алгоритм реорганизации для адаптации к различным распределениям запросов во время выполнения.

История

Концепция самоорганизующихся списков уходит корнями в идею организации деятельности.[1] записей в файлах, хранящихся на дисках или лентах. Одно из часто цитируемых обсуждений самоорганизующихся файлов и списков - это обсуждение Кнута.[2] Джон МакКейб провел первый анализ алгоритмической сложности стратегии Move-to-Front (MTF), когда элемент перемещается в начало списка после доступа к нему.[3] Он проанализировал среднее время, необходимое для сортировки произвольно упорядоченного списка в оптимальном порядке. Оптимальный порядок списка - это тот, при котором элементы упорядочены в списке по вероятности, с которой они будут необходимы, с наиболее доступным элементом первым. Оптимальный порядок может быть неизвестен заранее и может измениться со временем.

МакКейб представил стратегию перестановки, при которой элемент, к которому осуществляется доступ, обменивается с элементом перед ним в списке. Он высказал предположение, что в среднем случае транспонирование работает не хуже, чем MTF в приближении к оптимальному упорядочению записей в пределе. Позднее эта гипотеза была доказана Ривестом.[4] МакКейб также отметил, что с помощью эвристики транспонирования или MTF можно было бы приблизиться к оптимальному упорядочению записей, даже если эвристика применялась бы только каждый N-й доступ, и что можно было бы выбрать значение N, которое отразило бы относительную стоимость перемещения записей с ценность более быстрого приближения к оптимальному заказу. Были внесены дальнейшие улучшения, и исследователи предложили алгоритмы, в том числе: Ривест, Тененбаум и Немес, Кнут, Бентли и МакГеоч (например, анализ наихудшего случая для эвристики самоорганизующегося последовательного поиска).

Вступление

Самая простая реализация самоорганизующегося списка - это связанный список и, таким образом, будучи эффективным при вставке случайных узлов и распределении памяти, страдает от неэффективного доступа к случайным узлам. Самоорганизующийся список снижает неэффективность за счет динамического переупорядочивания узлов в списке в зависимости от частоты доступа.

Неэффективность обхода связанного списка

Если в списке нужно найти конкретный узел, каждый узел в списке необходимо последовательно сравнивать, пока не будет достигнут желаемый узел. В связанном списке получение n-го элемента является операцией O (n). Это очень неэффективно по сравнению, например, с массивом, где доступ к nth element - это операция O (1).

Эффективность самоорганизующихся списков

Самоорганизующийся список переупорядочивает узлы, оставляя наиболее часто используемые во главе списка. Как правило, в конкретном запросе шансы получить доступ к узлу, к которому ранее обращались много раз, выше, чем шансы получить доступ к узлу, к которому исторически не обращались так часто. В результате размещение часто используемых узлов во главе списка приводит к уменьшению количества сравнений, необходимых в среднем случае для достижения желаемого узла. Это приводит к повышению эффективности и в целом сокращению времени выполнения запросов.

Реализация самоорганизующегося списка

Реализация и методы самоорганизующегося списка идентичны стандартным. связанный список. Связанный список и самоорганизующийся список различаются только с точки зрения организации узлов; интерфейс остался прежним.

Анализ времени выполнения доступа / поиска в списке

Средний случай

Можно показать, что в среднем случае время, необходимое для поиска в самоорганизующемся списке размера n, равно

где p (i) - это вероятность доступа к i-му элементу в списке, также называемая вероятностью доступа. Если вероятность доступа для каждого элемента одинакова (т.е. p (1) = p (2) = p (3) = ... = p (n) = 1 / n), то порядок элементов не имеет значения, а средняя временная сложность определяется как

и T (n) в этом случае не зависит от индивидуальных вероятностей доступа элементов в списке. Однако в случае поиска по спискам с неоднородными вероятностями доступа к записям (то есть тем спискам, в которых вероятность доступа к одному элементу отличается от другого), средняя временная сложность может быть значительно снижена за счет правильного позиционирования элементов, содержащихся в списке.

Это достигается путем объединения меньшего i с большей вероятностью доступа, чтобы уменьшить общую среднюю временную сложность. Это можно продемонстрировать следующим образом:

Данный список: A (0,1), B (0,1), C (0,3), D (0,1), E (0,4)
Среднее время поиска без перегруппировки составляет:

Теперь предположим, что узлы переупорядочены так, что узлы с наибольшей вероятностью доступа расположены ближе всего к началу, так что теперь переупорядоченный список:
E (0,4), C (0,3), D (0,1), A (0,1), B (0,1)
Здесь среднее время поиска:

Таким образом, среднее время, необходимое для поиска в организованном списке (в данном случае) примерно на 40% меньше, чем время, необходимое для поиска в случайно организованном списке. Это концепция самоорганизующегося списка, заключающаяся в том, что средняя скорость извлечения данных увеличивается за счет переупорядочения узлов в соответствии с частотой доступа.

Худший случай

В худшем случае элемент, который нужно разместить, находится в самом конце списка, будь то обычный список или самоорганизующийся, и, следовательно, для его достижения необходимо провести n сравнений. Следовательно, в худшем случае время выполнения линейного поиска в списке равно O (n) независимо от типа используемого списка. Обратите внимание, что выражение для среднего времени поиска в предыдущем разделе является вероятностным. Сохранение часто используемых элементов в начале списка просто снижает вероятность наихудшего случая, но не устраняет его полностью. Даже в самоорганизующемся списке, если требуется получить доступ к элементу с наименьшей вероятностью доступа (который, очевидно, находится в конце списка), для его извлечения необходимо полностью просмотреть весь список. Это наихудший поиск.

Лучший случай

В лучшем случае поиск должен быть узлом, к которому обычно обращались, и, таким образом, он был идентифицирован списком и оставался в начале. Это приведет к работе с почти постоянным временем. В нотации большого числа в лучшем случае доступ к элементу представляет собой операцию O (1).

Методы перестановки узлов

При упорядочивании элементов в списке вероятности доступа к элементам обычно не известны заранее. Это привело к разработке различных эвристик для определения оптимального поведения. Основные эвристики, используемые для изменения порядка элементов в списке:

Метод перехода на передний план (MTF)

Этот метод перемещает элемент, к которому осуществляется доступ, в начало списка. Это имеет то преимущество, что оно легко реализуется и не требует дополнительной памяти. Эта эвристика также быстро адаптируется к быстрым изменениям в распределении запросов. С другой стороны, этот метод может отдавать приоритет редко используемым узлам - например, если к необычному узлу обращаются хотя бы один раз, он перемещается в начало списка и получает максимальный приоритет, даже если он не будет часто использоваться в будущее. Эти узлы с «избыточным вознаграждением» нарушают оптимальный порядок списка и приводят к более медленному времени доступа к часто используемым элементам. Другой недостаток заключается в том, что этот метод может стать слишком гибким, что приведет к слишком быстрому изменению шаблонов доступа. Это означает, что из-за очень короткой памяти шаблонов доступа даже оптимальное расположение списка может быть немедленно нарушено путем доступа к нечастому узлу в списке.

Переместить на передний план
Если выбран 5-й узел, он перемещается на передний план.
При выборе t-го пункта: если элемент i выбран: переместить элемент i в начало списка

Метод подсчета

В этом методе подсчитывается количество поисков каждого узла, т.е. каждый узел хранит отдельную переменную счетчика, которая увеличивается каждый раз при вызове. Затем узлы переупорядочиваются по убыванию количества. Таким образом, узлы с наибольшим количеством, то есть наиболее часто используемые, остаются во главе списка. Основное преимущество этого метода состоит в том, что он более реалистично отображает фактический шаблон доступа. Однако существует дополнительное требование к памяти, а именно поддержание переменной счетчика для каждого узла в списке. Кроме того, этот метод не может быстро адаптироваться к быстрым изменениям в схемах доступа. Например: если счетчик элемента заголовка говорит, что A равен 100, а для любого узла после него говорят, что B равен 40, то даже если B становится новым, наиболее часто используемым элементом, он все равно должен быть доступен как минимум (100-40 = 60 ) раз, прежде чем он станет головным элементом и, таким образом, сделает порядок в списке оптимальным.


Алгоритм подсчета

Если 5-й узел в списке ищется дважды, он будет заменен на 4-й.

в этом: count (i) = 0 для каждого элемента i при выборе t-го элемента: если элемент i ищется: count (i) = count (i) + 1 переупорядочить элементы на основе количества

Метод транспонирования

Этот метод включает замену узла, к которому осуществляется доступ, его предшественником. Следовательно, если осуществляется доступ к какому-либо узлу, он заменяется на узел впереди, если он не является головным узлом, тем самым повышая его приоритет. Этот алгоритм снова легко реализовать, он занимает мало места и, скорее всего, будет держать часто используемые узлы в начале списка. Однако метод транспонирования более осторожен. то есть потребуется много обращений, чтобы переместить элемент в начало списка. Этот метод также не позволяет быстро реагировать на изменения в распределении запросов по узлам в списке.

Алгоритм транспонирования

Если выбран 5-й узел в списке, он будет заменен на 4-й.

При выборе t-го пункта: если элемент i выбран: если i не является главой списка: замените элемент i на элемент (i - 1)

Другие методы

Исследования были сосредоточены на объединении вышеуказанных алгоритмов для повышения эффективности.[5] Алгоритм Битнера сначала использует MTF, а затем использует метод транспонирования для более тонких перестановок. Некоторые алгоритмы рандомизированы и пытаются предотвратить чрезмерное вознаграждение редко используемых узлов, которое может возникнуть в алгоритме MTF. Другие методы включают реорганизацию узлов на основе вышеупомянутых алгоритмов после каждого n обращений к списку в целом или после n обращений подряд к конкретному узлу и так далее. Некоторые алгоритмы переупорядочивают узлы, к которым осуществляется доступ, в зависимости от их близости к головному узлу, например: алгоритмы Swap-With-Parent или Move-To-Parent. Другой класс алгоритмов используется, когда шаблон поиска демонстрирует свойство, называемое локальностью ссылки, посредством чего в заданный интервал времени вероятностно наиболее вероятно получить доступ только к меньшему подмножеству списка. Это также называется зависимым доступом, когда вероятность доступа конкретного элемента зависит от вероятности доступа его соседних элементов. Такие модели распространены в реальных приложениях, таких как базы данных или файловые системы, а также управление памятью и кэширование. Обычная структура для алгоритмов, работающих с такими зависимыми средами, состоит в том, чтобы переупорядочить список не только на основе доступной записи, но и на основе записей рядом с ней. Это фактически включает реорганизацию подсписка списка, которому принадлежит запись.

Приложения самоорганизующихся списков

Переводчики языков, такие как компиляторы и интерпретаторы, используют самоорганизующиеся списки для поддержки таблицы символов при компиляции или интерпретации исходного кода программы. В настоящее время ведутся исследования по включению структуры данных самоорганизующегося списка в встроенные системы для снижения активности переключения шины, которая приводит к рассеянию мощности в этих цепях. Эти списки также используются в искусственный интеллект и нейронные сети а также саморегулирующиеся программы. Алгоритмы, используемые в самоорганизующихся списках, также используются как алгоритмы кеширования как и в случае алгоритма LFU.

Простые методы «Переместить на передний план» и «транспонировать» также применимы в реальных коллекциях: например, организация ящика для специй путем замены использованных предметов на переднюю часть ящика или перенос чистящего элемента на его передний сосед, когда он используется.

Примечания

  1. ^ Беккер, Дж .; Хейс, Р. (1963), Хранение и поиск информации: инструменты, элементы, теории, Нью-Йорк: Wiley
  2. ^ Кнут, Дональд (1998), Сортировка и поиск, Искусство программирования, Том 3 (второе изд.), Addison-Wesley, p. 402, г. ISBN  978-0-201-89685-5
  3. ^ Маккейб, Джон (1965), "О последовательных файлах с перемещаемыми записями", Исследование операций, 13 (4): 609–618, Дои:10.1287 / opre.13.4.609
  4. ^ Ривест, Рональд (1976), "Об эвристике самоорганизующегося последовательного поиска", Коммуникации ACM, 19 (2): 63–67, Дои:10.1145/359997.360000
  5. ^ Амер, Абдельрахман; Оммен, Б. Джон (2006). «Списки в списках: структура для самоорганизующихся списков в средах с указанием местонахождения». Экспериментальные алгоритмы. Конспект лекций по информатике. 4007. С. 109–120. Дои:10.1007/11764298_10. ISBN  978-3-540-34597-8.

Рекомендации