Техника частичного каскадирования — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Закончено описание "Ответ на запрос", исправлены недопонимания с головой. Исправлены пункты 1, 2, 5, 7, 8, 12)
(Добавлена часть псевдокода не в tex)
Строка 36: Строка 36:
 
* 1) Мы можем проводить ссылки из каталога номер <tex> i </tex> в <tex> (i + 1) </tex>-ый каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, очевидно, в некоторых случаях уменьшит время поиска. <br>
 
* 1) Мы можем проводить ссылки из каталога номер <tex> i </tex> в <tex> (i + 1) </tex>-ый каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, очевидно, в некоторых случаях уменьшит время поиска. <br>
 
* 2) Мы можем для оптимизации пункта 1 создать модифицированные каталоги <tex> M_i </tex>, где <tex> i </tex>-ый каталог будет представлять каталог <tex> C_i </tex> слитый с <tex> M_{i + 1} </tex>
 
* 2) Мы можем для оптимизации пункта 1 создать модифицированные каталоги <tex> M_i </tex>, где <tex> i </tex>-ый каталог будет представлять каталог <tex> C_i </tex> слитый с <tex> M_{i + 1} </tex>
<br>
 
  
=== Построение ===
+
=== Построение ===  
Рассмотрим подробнее построение каталогов <tex> M_i </tex>.
 
 
Введем определения:  
 
Введем определения:  
 
{{Определение
 
{{Определение
Строка 60: Строка 58:
 
<br> <tex> C_5 = \{1, 2, 4, 6, 9\} </tex>
 
<br> <tex> C_5 = \{1, 2, 4, 6, 9\} </tex>
 
<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой строке <tex> j </tex>-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке.
 
<br> Для наглядности заведем таблицу, где в <tex>i</tex>-ой строке <tex> j </tex>-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге <tex> C_i </tex>. Тогда результатом построения будет таблица, которая представлена на рисунке.
 
+
<br>
 +
Из-за необходимости хранения ссылок будет удобно завести структуру для хранения элементов в модифицированных каталогах.
 +
struct node : 
 +
    element key
 +
    node *left, *right, *down
 +
    bool is_alien
 
=== Ответ на запрос ===
 
=== Ответ на запрос ===
  
 
В первом каталоге ответ на запрос найдем с помощью бинарного поиска по <tex> C_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>. Далее проитерируемся по оставшимся каталогам. Для того, чтобы перейти в новый ''модифицированный каталог'' мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в ''подставную вершину'', а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. Если теперь <tex> cell </tex> {{---}} ''неподставная вершина'', то нам достаточно рассмотреть двух ее соседей справа в <tex> C_i </tex>, так как <tex> cell.key < x </tex>, а каждая вторая ячейка из <tex> M_i </tex> попадает в <tex> M_{i - 1} </tex>, т.е. мы бы встретили ее ранее и перешли мы вниз по ней, но это не случилось. Обновив cell максимальным из подходящих значений нужно проверить, является ли она ''подставным элементом'', если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.
 
В первом каталоге ответ на запрос найдем с помощью бинарного поиска по <tex> C_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>. Далее проитерируемся по оставшимся каталогам. Для того, чтобы перейти в новый ''модифицированный каталог'' мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в ''подставную вершину'', а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. Если теперь <tex> cell </tex> {{---}} ''неподставная вершина'', то нам достаточно рассмотреть двух ее соседей справа в <tex> C_i </tex>, так как <tex> cell.key < x </tex>, а каждая вторая ячейка из <tex> M_i </tex> попадает в <tex> M_{i - 1} </tex>, т.е. мы бы встретили ее ранее и перешли мы вниз по ней, но это не случилось. Обновив cell максимальным из подходящих значений нужно проверить, является ли она ''подставным элементом'', если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.
 +
 +
node cell = binary_search(M[1], x)
 +
if (cell.is_alien)
 +
    cell = cell.left
 +
ans[1] = cell.key;
 +
'''for''' i = 2 '''to''' k
 +
    cell = cell.left.down
 +
    if (cell.right <= x)
 +
          cell = cell.right
 +
    if (cell.right <= x)
 +
          cell = cell.right
 +
    if (cell.is_alien)
 +
          cell = cell.left
 +
    ans[i] = cell.key

Версия 23:08, 7 июня 2017

Определение:
Каталог (англ. catalog)— упорядоченный массив из элементов, на которых введено отношение порядка. В данной статье предполагается, что массив упорядочен по неубыванию.


Определение:
Техника частичного каскадирования (англ. fractional cascading technique) — это способ организации структуры данных, который предназначен для быстрого итеративного поиска в [math] k [/math] каталогах.



Задача:
Дано [math] k [/math] каталогов [math] C_i [/math], каталог [math]C_i[/math] имеет размер [math] n_i [/math]. Поступают запросы, которые представляют собой один элемент [math] x [/math]. Требуется для каждого запроса определить в каждом каталоге максимальный элемент меньше либо равный [math] x [/math].


Различные подходы к решению

Пример ответа на запрос

Пусть [math] n = \sum\limits_{i = 1}^k n_i [/math].
1) Для ответа на запрос последовательно посетим все каталоги. Пусть мы находимся в [math] i[/math]-ом каталоге, тогда мы можем ответить на запрос для данного каталога за [math] O(\log n_i) [/math], используя бинарный поиск. Так как каталогов [math] k [/math] штук, то для ответа на запрос понадобится [math] O(k \log n) [/math] времени. Для хранения всех каталогов понадобится [math] \Theta(n) [/math] памяти.
2) Для второго способа построим сбалансированное бинарное дерево поиска из всех элементов всех каталогов. В каждой вершине дерева будет хранится дополнительно кортеж из [math] k [/math] элементов — максимальных представителей каталогов меньше либо равных ключу вершины. Таким образом такая структура будет занимать [math] O(n) [/math] на дерево поиска и [math] O(kn) [/math] на дополнительные кортежи.Тогда для ответа на запрос найдем в дереве поиска максимальный ключ меньше либо равный [math] x [/math] и выведем [math] k [/math] элементов соответствующего кортежа, итого ответ на запрос производится за [math] O(\log n + k) [/math].

Итого имеем:

Тип подхода к решению Необходимая память Время ответа на один запрос
[math] k [/math] бинарных поисков
[math] \Theta(n) [/math]
[math] O(k \log n) [/math]
Построение бинарного дерева поиска с кортежами
[math] O(kn) [/math]
[math] O(\log n + k) [/math]

Решение с помощью техники частичного каскадирования

Как будет показано далее, эта техника берет лучшее от подходов к решению этой задачи, что были рассмотрены выше, а именно она требует [math] O(n) [/math] памяти и [math] O(\log n + k) [/math] времени для ответа на запрос.
Идея данной техники построена на следующем:

  • 1) Мы можем проводить ссылки из каталога номер [math] i [/math] в [math] (i + 1) [/math]-ый каталог таким образом, что разница между элементами, соединенными ссылками минимальна, что, очевидно, в некоторых случаях уменьшит время поиска.
  • 2) Мы можем для оптимизации пункта 1 создать модифицированные каталоги [math] M_i [/math], где [math] i [/math]-ый каталог будет представлять каталог [math] C_i [/math] слитый с [math] M_{i + 1} [/math]

Построение

Введем определения:

Определение:
Подставной элемент — элемент каталога [math] M_i [/math], который пришел из каталога [math] M_{i + 1} [/math]. А также каталоги [math] M_i [/math] будем называть модифицированными каталогами.
Построение модифицированных каталогов


Первый этап построения:

  • [math] i = k [/math] : Данный каталог не имеет никаких ссылок и равен [math] C_i [/math].
  • [math] i \lt k [/math] : Для построения данного каталога будем сливать каталог [math] C_i [/math] с каждым вторым элементом каталога [math] M_{i + 1} [/math]. Каждый элемент из каталога [math] M_{i + 1} [/math] оснастим ссылкой на позицию, откуда мы его взяли, такие ссылки будет называть ссылками вниз.


Второй этап построения:
В каждом модифицированном каталоге для каждого элемента заведем две ссылки. Для неподставных элементов это будут ссылки на максимальныйподставной элемент меньше текущего и на минимальный любого типа больше текущего. Если элемент подставной, то ссылки будут на минимальный неподставной элемент" больше текущего и на максимальный неподставной элемент меньше текущего. Назовем их ссылками влево и вправо.


Рассмотрим на процесс построения на примере.
Пусть дано [math] k = 5 [/math] каталогов:
[math] C_1 = \{1, 3, 6, 7, 11, 12\} [/math]
[math] C_2 = \{4, 9, 10\} [/math]
[math] C_3 = \{1, 2, 7, 8, 11, 12\} [/math]
[math] C_4 = \{3, 4, 8, 10, 12\} [/math]
[math] C_5 = \{1, 2, 4, 6, 9\} [/math]
Для наглядности заведем таблицу, где в [math]i[/math]-ой строке [math] j [/math]-ая ячейка будет окрашена в зеленый цвет, если она присутствует в каталоге [math] C_i [/math]. Тогда результатом построения будет таблица, которая представлена на рисунке.
Из-за необходимости хранения ссылок будет удобно завести структуру для хранения элементов в модифицированных каталогах.

struct node :  
    element key 
    node *left, *right, *down 
    bool is_alien

Ответ на запрос

В первом каталоге ответ на запрос найдем с помощью бинарного поиска по [math] C_1 [/math]. Пусть ответом для этого каталога будет ячейка [math] cell [/math]. Далее проитерируемся по оставшимся каталогам. Для того, чтобы перейти в новый модифицированный каталог мы перейдем из [math] cell [/math] по ссылке влево, чтобы попасть в подставную вершину, а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. Если теперь [math] cell [/math]неподставная вершина, то нам достаточно рассмотреть двух ее соседей справа в [math] C_i [/math], так как [math] cell.key \lt x [/math], а каждая вторая ячейка из [math] M_i [/math] попадает в [math] M_{i - 1} [/math], т.е. мы бы встретили ее ранее и перешли мы вниз по ней, но это не случилось. Обновив cell максимальным из подходящих значений нужно проверить, является ли она подставным элементом, если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.

node cell = binary_search(M[1], x)
if (cell.is_alien) 
    cell = cell.left
ans[1] = cell.key;
for i = 2 to k
    cell = cell.left.down
    if (cell.right <= x)
         cell = cell.right
    if (cell.right <= x)
         cell = cell.right
    if (cell.is_alien)
         cell = cell.left
    ans[i] = cell.key