Рубрики

Самоорганизующийся список | Комплект 1 (Введение)

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

Одной из идей по ускорению поиска связанных списков является Skip List . Другая идея (которая обсуждается в этом посте) состоит в том, чтобы размещать наиболее часто используемые элементы ближе к голове. , Там может быть две возможности. офлайн (мы заранее знаем всю последовательность поиска) и онлайн (мы не знаем последовательность поиска).
В случае офлайн, мы можем расположить узлы в соответствии с уменьшением частоты поиска (на первом месте стоит элемент с максимальным числом поиска). Для многих практических применений может быть трудно получить последовательность поиска заранее. Самоорганизующийся список переупорядочивает свои узлы на основе выполненных поисков. Идея состоит в том, чтобы использовать локальность ссылок (в типичной базе данных 80% доступа составляют 20% элементов). Ниже приведены различные стратегии, используемые самоорганизующимися списками.

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

2) Метод подсчета : каждый узел хранит счетчик количества поисков. Узлы упорядочены по убыванию количества. Эта стратегия требует дополнительного места для хранения счета.

3) Метод транспонирования : любой искомый узел заменяется предыдущим узлом. В отличие от Move-to-front, этот метод не быстро адаптируется к изменяющимся схемам доступа.

Конкурентный анализ:
Наихудшая временная сложность всех методов — O (n). В худшем случае искомый элемент всегда является последним элементом в списке. Для анализа среднего случая нам нужно распределение вероятностей поисковых последовательностей, которое недоступно много раз.
Для онлайн-стратегий и алгоритмов, подобных описанным выше, у нас есть совершенно другой способ их анализа, называемый конкурентным анализом, где производительность онлайн-алгоритма сравнивается с производительностью оптимального автономного алгоритма (который может заранее просматривать последовательность запросов). Конкурентный анализ используется во многих практических алгоритмах, таких как кэширование, разбиение на страницы дисков, высокопроизводительные компьютеры. Самое лучшее в конкурентном анализе — нам не нужно ничего предполагать о вероятностном распределении входных данных. Метод Move-to-front является 4-конкурентным, что означает, что он никогда не выполняет более чем в 4 раза больше операций, чем автономный алгоритм (см. Видео-лекцию MIT для доказательства).

Вскоре мы обсудим реализацию и доказательства анализа, приведенного в видео-лекции.

Ссылки:
http://en.wikipedia.org/wiki/Self-organizing_list
MIT Video Lecture
http://www.eecs.yorku.ca/course_archive/2003-04/F/2011/2011A/DatStr_071_SOLists.pdf
http://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)

Эта статья составлена Абхай Рати . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Самоорганизующийся список | Комплект 1 (Введение)

0.00 (0%) 0 votes