Изменения

Пусть имеется две упорядоченные последовательности размера <tex>N_1</tex> и <tex>N_2</tex> соответственно. Чтобы их слить, достаточно завести во внутренней памяти <tex>3 </tex> блока. В первые <tex>2 </tex> мы будем читать сами последовательности, а в третий будем записывать результат слияния, используя стандартный алгоритм с <tex>2 </tex> указателями. Как-то только какой-то из указателей дошел до конца блока необходимо считывать следующий, а когда буфер с результатом слияния заполнился {{---}} необходимо записывать его во внешнюю память и очищать. Сложность алгоритма {{---}} <tex>\mathcal{O}(Scan(N_1 + N_2))</tex>

Поскольку мы легко умеем выполнять слияние упорядоченных последовательностей, логичным шагом будет рассмотреть сортировку во внешней памяти. Рассмотрим некоторую модификацию алгоритма [[Сортировка слиянием|Merge sort]]. В стандартном алгоритме все элементы разбиваются на пары, после чего сливаются в упорядоченные последовательности длины <tex>2</tex>, те в свою очередь сливаются в последовательности длины <tex>4 </tex> и так далее (для простоты описания будем считать что <tex>N </tex> и <tex>B </tex> это степень двойки). Во внешней памяти не выгодно начинать с последовательностей длины <tex>1</tex>, так как чтение происходит блоками длины <tex>B</tex>. Вместо этого можно целиком считать блок и отсортировать его во внутренней памяти. Тогда количество листьев в дереве сортировки будет не <tex>N</tex>, а <tex>\dfrac{N}{B}</tex>. Помимо этого, гораздо выгоднее сливать больше чем <tex>2 </tex> списка за раз, чтобы уменьшить высоту дерева сортировки. Так как оперативная память размера <tex>M</tex>, то можно сливать сразу <tex>\dfrac{M}{B}</tex> списков. Итого, на каждом уровне дерева сортировки мы выполняем <tex>\mathcal{O}\left(\dfrac{N}{B}\right)</tex> операций и итоговая сложность {{---}} <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{B}\right) = Sort(N)</tex>.

В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины <tex>M</tex>, а не <tex>B</tex>. Хотя итоговая сложность и станет <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{M}\right)</tex>, но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.

Пусть во внешней памяти есть <tex>2 последовательности </tex> таблицы вида <tex>(key, value)</tex>. Первая последовательность таблица имеет вид <tex>(k_i, a_{k_i})</tex>, вторая {{---}} <tex>(l_j, b_{l_j})</tex>. Необходимо получить последовательность таблицу вида <tex>(i, a_i, b_i)</tex> (не умоляя общности считаем, что <tex>(k_1 \dots k_N)</tex> и <tex>(l_1 \dots l_N)</tex> являются перестановками чисел от <tex>1 </tex> до <tex>N</tex>). Очевидно, что задача решается просто сортировками последовательностей таблиц по первому аргументу ключу с последующим проходом по ним <tex>2 </tex> указателями. Поэтому сложность алгоритма {{---}} <tex>Sort(N)</tex>. Данный алгоритм хоть и крайне прост, является одним из ключевых примитивов. Когда необходимо совершить какую-то операцию над разбросанными по памяти данными, часто задача сводится к последовательности нескольких Join'ов.

Попробуем решить задачу [[Файл:List.png|300px|thumb|Входные данные]] Данная задача заключается в следующем: дан односвязный список, то есть для каждого элемента известно, какой идет следующим способом {{за ним. Необходимо для каждого элемента определить, каким он является по счету с конца списка. Расстояние до конца списка будем называть ''рангом'' элемента. Не смотря на простоту задачи в ''RAM-машине'', во внешней памяти задача имеет нетривиальное решение. Из-за того что все данные лежат хаотично, мы не можем просто пройтись по списку, это может потребовать слишком много операций ввода-}} вывода. === Идея === Решим задачу следующим способом: выкинем из списка какую-то часть элементов, после чего рекурсивно посчитаем ответ для полученного списка, а затем. Затем, зная промежуточный ответ, восстановим ответ для исходной задачи. Первая проблема с которой мы сталкиваемся {{---}} это то, что в модифицированном списке ранги элементов отличаются. Чтобы решить эту проблему, решим рассмотрим более общую задачу. Будем считать, что у каждого элемента есть вес <tex>w_i</tex>, а ранг элемента это сумма весов до конца списка. Для решения исходной задачи в самом начале присвоим каждому элементу вес <tex>1</tex>.  === Обозначения ===

Теперь, если у нас есть 3 последовательных элемента x, y, z (* <tex>next[x] </tex> {{---}} массив входных данных. <tex>next_x = y</tex>означает, что после элемента <tex>next[y] = zx</tex>), то при удалении элемента идет <tex>y</tex> нужно увеличить вес (<tex>znext_i = 0</tex> на значит, что элемент <tex>w_yi</tex>последний в списке). То есть * <tex>w_z'=w_z + w_yw_i</tex>. После того, как мы посчитаем ответ для модифицированного списка, ранг удаленного {{---}} вес элемента с номером <tex>yi</tex>* <tex>r_i</tex> будет равен {{---}} ранг элемента с номером <tex>r_y=r_z+w_zi</tex>.

Выкидывать по 1 элементу крайне неэффективно, но если выкидывать какую-то весомую часть, то нужно быстро пересчитывать веса === Удаление элементов. Сделать это можно с помощью уже рассмотренного Join, однако необходимо наложить ограничение на множество удаляемых элементов: никакие два удаленных элемента не должны идти подряд в списке. В противном случае может образоваться цепочка из удаленных элементов произвольной длины. Веса всех элементов этой цепочки нужно будет прибавить к первому не удаленному элементу, что равносильно самой задаче List Ranking, которую мы и пытаемся решить. восстановление рангов ===

Рассмотрим Если есть <tex>3</tex> последовательных элемента <tex>x</tex>, <tex>y</tex>, <tex>z</tex> (<tex>next_x = y</tex>, <tex>next_y = z</tex>), то при удалении элемента <tex>y</tex> нужно увеличить вес <tex>z</tex> на <tex>w_y</tex>. То есть <tex>w_z'=w_z + w_y</tex>. После того, как именно изменять веса элементовмы посчитаем ответ для модифицированного списка, ранг удаленного элемента <tex>y</tex> будет равен <tex>r_y=r_z+w_z</tex>. Построим и отсортируем по 1 элементу 3 таблицы:

1) Таблица Conn из пар <tex>(i, j)</tex>, где каждая пара значит что после i[[Файл:List-ого ranking-wr.png|400px|Удаление элемента идет j-ыйи восстановление ответа]]

2) Таблица W из пар Выкидывать по <tex>(i, w_i)1</tex>элементу крайне неэффективно, хранящая но если выкидывать какую-то весомую часть, то нужно быстро пересчитывать веса элементов. Сделать это можно с помощью уже рассмотренного Join, однако необходимо наложить ограничение на множество удаляемых элементов: никакие два удаленных элемента не должны идти подряд в списке. В противном случае может образоваться цепочка из удаленных элементов произвольной длины. Веса всех элементов этой цепочки нужно будет прибавить к первому не удаленному элементу, что равносильно самой задаче List Ranking, которую мы и пытаемся решить.

Рассмотрим как именно изменять веса элементов. Построим и отсортируем по ключу <tex>3) Таблица D, в которой записаны удаляемые элементы</tex> таблицы вида:

Теперь пройдемся 3 указателями по этим таблицам, и если нам встречается триплет вида # Таблица <tex>Conn</tex> из пар <tex>(i, j) \in Conn</tex>, где каждая пара значит что после <tex>i</tex>-ого элемента идет <tex>j</tex>-ый (i, w_iможет быть получена из входных данных за время линейного сканирования) \in # Таблица <tex>W</tex>, из пар <tex>(i, w_i) \in D</tex>, то добавим пару хранящая веса элементов# Таблица <tex>(j, w_i)D</tex>. У нас получится таблица добавок. Теперь из таблицы добавок и таблицы весов можно с помощью того же Join получить таблицу новых весов., в которой записаны удаляемые элементы

По возвращению Теперь пройдемся <tex>3</tex> указателями по этим таблицам. Как только встречается триплет вида <tex>(i, j) \in Conn</tex>, <tex>(i, w_i) \in W</tex>, <tex>(i) \in D</tex>, то добавим в новую таблицу пару <tex>(j, w_i)</tex>. В конце получится таблица добавок весов. Теперь из рекурсии аналогично пересчитываются ранги элементовтаблицы добавок и таблицы весов можно с помощью того же Join получить таблицу новых весов. Рассмотрим 3 таблицы:

1) Таблица RevConn По возвращению из пар рекурсии аналогично пересчитываются ранги элементов. Рассмотрим <tex>(j, i)3</tex>, где каждая пара значит что после i-ого элемента идет j-ыйтаблицы:

2# Таблица <tex>RevConn</tex> из пар <tex>(j, i) </tex>, где каждая пара значит что после <tex>i</tex>-ого элемента идет <tex>j</tex>-ый# Таблица <tex>W </tex> из пар <tex>(i, w_i)</tex>, хранящая веса элементов# Таблица <tex>R</tex> из пар <tex>(i, r_i)</tex>, в которой записаны ранги элементов модифицированного списка

Также пройдемся <tex>3</tex> указателями по этим таблицам. Если нам встречается триплет вида <tex>(i, j) \in Conn</tex>, <tex>(i, w_i) Таблица R из пар \in W</tex>, <tex>(i, r_i)\in D</tex>, то добавим пару <tex>(j, r_i + w_i)</tex> в которой записаны ранги элементов модифицированного спискатаблицу новых рангов. Однако в эту таблицу попадут все элементы, у которых следующий элемент не был удален. Поэтому далее необходимо заменить лишние записи, используя таблицу старых рангов и Join.

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

Подсчитаем матожидание выброшенных элементов {{---}} <tex>E(D) = \sum\limits_{(i, j) \in Conn}\fracdfrac{1}{4} = \fracdfrac{N}{4}</tex>