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

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

История

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

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

Введение

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ Tavg = 1 * p(1) + 2 * p(2) + 3 * p(3) + . . . + n * p(n). }[/math]

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

[math]\displaystyle{ T(n) = 1/n + 2/n + 3/n + ... + n/n = (1 + 2 + 3 + ... + n)/n = (n+1)/2 }[/math]

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

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

Дан список: A (0,1), B (0,1), C (0,3), D (0,1), E (0,4)

Без переупорядочивания среднее необходимое время поиска составляет:

[math]\displaystyle{ T(n) = 1*0.1 + 2*0.1 + 3*0.3 + 4*0.1 + 5*0.4 = 3.6 }[/math]

Теперь предположим, что узлы переупорядочены так, что узлы с наибольшей вероятностью доступа расположены ближе всего к передней части, так что теперь переупорядоченный список:

E (0,4), C (0,3), D (0,1), A (0,1), B (0.1)

Здесь среднее время поиска:

[math]\displaystyle{ T(n) = 1*0.4 + 2*0.3 + 3*0.1 + 4*0.1 + 5*0.1 = 2.2 }[/math]

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

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

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

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

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

Способы перестановки узлов

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

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

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

At the t-th item selection:
    if item i is selected:
        move item i to head of the list

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

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

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

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

At the t-th item selection:
    if item i is selected:
        if i is not the head of list:
            swap item i with item (i - 1)

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

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

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

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