Структура рабочего набора Иаконоса - Iaconos working set structure

Структура данных рабочего набора Iacono
Изобрел	2001
Изобретенный	Джон Яконо
Асимптотическая сложность в нотация большой O
Космос	О(п)
Поиск	О(бревно ш (х))
Вставлять	О(бревно п)
Удалить	О(бревно п)

В информатике структура рабочего набора Яконо^[1] основано на сравнении толковый словарь. Он поддерживает операции вставки, удаления и доступа для поддержания динамического набора ${\displaystyle n}$ элементы. Рабочий набор изделия ${\displaystyle x}$ это набор элементов, к которым осуществлялся доступ в структуре с момента последнего ${\displaystyle x}$ был осуществлен доступ (или вставлен, если к нему никогда не обращались). Вставка и удаление в структуре рабочего набора требует ${\displaystyle O(\log n)}$ время при доступе к элементу ${\displaystyle x}$ берет ${\displaystyle O(\log w(x))}$. Здесь, ${\displaystyle w(x)}$ представляет собой размер рабочего набора ${\displaystyle x}$.

Структура

Пример поиска ${\displaystyle x}$ в составе рабочего набора. После нахождения ${\displaystyle x}$, он удален из ${\displaystyle T_{4}}$ и вставлен в ${\displaystyle T_{1}}$. Наконец, выполняется переход от 1 к 4, при котором элемент удаляется из ${\displaystyle T_{i}}$ и вставлен в ${\displaystyle T_{i+1}}$ за ${\displaystyle 1\leq i<4}$.

Для хранения динамического набора ${\displaystyle n}$ элементов, эта структура состоит из ряда Красно-черные деревья, или другой Самобалансирующиеся бинарные деревья поиска ${\displaystyle T_{1},T_{2},\ldots ,T_{k}}$, и ряд дек (Двусторонние очереди) ${\displaystyle Q_{1},Q_{2},\ldots Q_{k}}$, куда ${\displaystyle k=\lceil \log \log n\rceil }$. Для каждого ${\displaystyle 1\leq i\leq k}$, дерево ${\displaystyle T_{i}}$ и дек ${\displaystyle Q_{i}}$ разделяют одно и то же содержимое, и между соответствующими элементами поддерживаются указатели. Для каждого ${\displaystyle i<k}$, размер ${\displaystyle T_{i}}$ и ${\displaystyle Q_{i}}$ является ${\displaystyle 2^{2^{i}}}$. Дерево ${\displaystyle T_{k}}$ и дек ${\displaystyle Q_{k}}$ состоят из остальных элементов, т.е. их размер ${\displaystyle n-\sum _{i=1}^{k-1}2^{2^{i}}}$. Таким образом, количество элементов во всех деревьях и количество элементов во всех декадах в сумме составляют ${\displaystyle n}$.Каждый элемент, который был вставлен в структуру данных, сохраняется ровно в одном из деревьев и его соответствующей двухсторонней очереди.

Рабочий набор Инвариант

В декадах этой структуры элементы хранятся в отсортированном порядке в соответствии с размером их рабочего набора. ${\displaystyle x}$ лежит после ${\displaystyle y}$ в дек ${\displaystyle Q_{i}}$ если и только если ${\displaystyle w(x)<w(y)}$. Причем для каждого ${\displaystyle 1\leq i<k}$, элементы в deque ${\displaystyle Q_{i}}$ имеют меньшие рабочие наборы, чем элементы в deque ${\displaystyle Q_{i+1}}$. Это свойство называется инвариантом рабочего набора. Каждая операция в структуре данных поддерживает неизменность рабочего набора.

Операции

Основная операция в этой структуре называется сдвигом с ${\displaystyle h}$ к ${\displaystyle j}$, куда ${\displaystyle h}$ и ${\displaystyle j}$ являются индексами некоторых деревьев в структуре. Два случая рассматриваются в сдвиге от ${\displaystyle h}$ к ${\displaystyle j}$: Если ${\displaystyle h<j}$, то для каждого ${\displaystyle h\leq i<j}$, взятый в порядке возрастания, элемент удаляется из очереди ${\displaystyle Q_{i}}$ и поставлен в очередь ${\displaystyle Q_{i+1}}$. Соответствующий элемент удален из ${\displaystyle T_{i}}$ и вставлен в ${\displaystyle T_{i+1}}$. Продолжительность этой операции составляет ${\displaystyle O(\sum _{i=h}^{j}\log |T_{i}|)=O(\sum _{i=h}^{j}\log 2^{2^{i}})=O(2^{j})}$. Аналогично, если ${\displaystyle j<h}$, то для каждого ${\displaystyle j<i\leq h}$, взятый в порядке убывания, элемент удаляется из очереди ${\displaystyle Q_{i}}$ и поставлен в очередь ${\displaystyle Q_{i-1}}$. Соответствующий элемент удален из ${\displaystyle T_{i}}$ и вставлен в ${\displaystyle T_{i-1}}$. Продолжительность этой операции составляет ${\displaystyle O(\sum _{i=j}^{h}\log |T_{i}|)=O(\sum _{i=j}^{h}\log 2^{2^{i}})=O(2^{h})}$. В любом случае после сменной работы размер ${\displaystyle T_{h}}$ уменьшается на единицу, тогда как размер ${\displaystyle T_{j}}$ увеличивается на единицу. Поскольку элементы в двухсторонней очереди отсортированы по размерам их рабочих наборов, операция сдвига поддерживает неизменность рабочего набора.

Поиск

Для поиска элемента ${\displaystyle x}$, ищи ${\displaystyle x}$ в ${\displaystyle T_{1},T_{2},\ldots T_{k}}$, в порядке возрастания, пока не будет найдено дерево ${\displaystyle T_{j}}$ содержащий ${\displaystyle x}$. Если дерево не найдено, поиск неуспешен. Если ${\displaystyle x}$ найден, он удален из ${\displaystyle T_{j}}$ а затем вставлен в ${\displaystyle T_{1}}$, т.е. перемещается к передней части конструкции. Поиск заканчивается выполнением сдвига с ${\displaystyle 1}$ к ${\displaystyle j}$ который восстанавливает размер каждого дерева и каждой двухсторонней очереди до их размера до операции поиска. Время выполнения этого поиска равно ${\displaystyle O(\sum _{i=1}^{j}\log 2^{2^{i}})=O(2^{j})}$ если поиск был успешным, или ${\displaystyle O(\sum _{i=j}^{k}\log 2^{2^{i}})=O(2^{k})=O(\log n)}$ в противном случае. По свойству рабочего набора каждый элемент в деревьях ${\displaystyle T_{1},T_{2},\ldots ,T_{j-1}}$ принадлежит к рабочему набору ${\displaystyle x}$. В частности, каждый элемент в ${\displaystyle T_{j-1}}$ принадлежит к рабочему набору ${\displaystyle x}$ и поэтому, ${\displaystyle w(x)>|T_{j-1}|=2^{2^{j-1}}}$. Таким образом, время успешного поиска составляет ${\displaystyle O(2^{j})=O(\log 2^{2^{j-1}})=O(\log w(x))}$.

Вставлять

Вставка элемента ${\displaystyle x}$ в конструкцию выполняется вставкой ${\displaystyle x}$ в ${\displaystyle T_{1}}$ и помещая его в ${\displaystyle Q_{1}}$. Вставка завершается выполнением сдвига с ${\displaystyle 1}$ к ${\displaystyle k}$. Чтобы избежать переполнения, если ${\displaystyle |T_{k}|=2^{2^{k}}}$ перед сдвигом, т.е. если последнее дерево заполнено, то ${\displaystyle k}$ увеличивается и новый пустой ${\displaystyle T_{k}}$ и ${\displaystyle Q_{k}}$ создано. Во время выполнения этой операции преобладает сдвиг с ${\displaystyle 1}$ к ${\displaystyle k}$ чье время работы ${\displaystyle O(2^{k})=O(2^{\log \log n})=O(\log n)}$.Since элемент ${\displaystyle x}$, чей рабочий набор наименьший, ставится в очередь в ${\displaystyle Q_{1}}$, инвариант рабочего набора сохраняется после сдвига.

Удалить

Удаление элемента ${\displaystyle x}$ выполняется путем поиска ${\displaystyle x}$ на каждом дереве в структуре в порядке возрастания, пока не будет найдено дерево ${\displaystyle T_{j}}$ который содержит его (если не найдено, удаление неуспешно). Элемент ${\displaystyle x}$ удален из ${\displaystyle T_{j}}$ и ${\displaystyle Q_{j}}$. Наконец, переход от ${\displaystyle k}$ к ${\displaystyle j}$ сохраняет размер ${\displaystyle T_{j}}$ равно ${\displaystyle 2^{2^{j}}}$. Продолжительность этой операции составляет ${\displaystyle O(2^{k})=O(\log n)}$. Инвариант рабочего набора сохраняется, поскольку удаление элемента не меняет порядок рабочего набора элементов.

Обсуждение

Раскидистые деревья - это самонастраивающиеся деревья поиска, представленные Слеатором и Тарьяном^[2] в 1985 году. Используя эвристику реструктуризации, расширяемые деревья могут выполнять операции вставки и удаления в ${\displaystyle O(\log n)}$ амортизированный раз, без сохранения информации о балансе на узлах. Более того, теорема о рабочем множестве для расширяемых деревьев утверждает, что стоимость доступа к элементу в расширяемом дереве равна ${\displaystyle O(\log w(x))}$ амортизированный. Структура рабочего набора Iacono обеспечивает одинаковое время работы для поиска, вставки и удаления в худшем случае. Поэтому предлагаю альтернативу растопленным деревьям.

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

1. Яконо, Джон (2001). "Альтернативы расширению деревьев с временем доступа O (log n) в худшем случае" (PDF). Материалы двенадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам: 516–522.
2. Sleator, Daniel D .; Тарджан, Роберт Э. (1985), «Самонастраивающиеся деревья двоичного поиска» (PDF), Журнал ACM, 32 (3): 652–686, Дои:10.1145/3828.3835