286
правок
Изменения
List Ranking
=== Join ===
Рассмотрим следующую задачу {{---}} пусть у нас во внешней памяти есть 2 последовательности вида <tex>(ключ, значение)</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> являются перестановками чисел от 1 до n). Очевидно, что задача решается просто сортировками последовательностей по первому аргументу с проходом последующим проходом по ним 2 указателями. Поэтому сложность алгоритма {{---}} <tex>Sort(Nn)</tex>.
== List Ranking ==
Данная задача заключается в следующем {{---}} нам дан односвязный список, то есть для каждого элемента мы знаем, какой идет следующим за ним в списке. Необходимо для каждого элемента определить, каким он является по счету с конца списка. Расстояние до конца списка будем называть ''рангом'' элемента. Не смотря на простоту задачи в ''RAM-машине'', во внешней памяти задача имеет нетривиальное решение. Из-за того что во внешней памяти все данные лежат хаотично, мы не можем просто пройтись по списку, это может потребовать слишком много операций ввода-вывода.
Попробуем решить задачу следующим способом {{---}} выкинем из списка какую-то часть элементов, после чего рекурсивно посчитаем ответ для полученного списка, а затем, зная промежуточный ответ, восстановим ответ для исходной задачи. Первая проблема с которой мы сталкиваемся {{---}} это то, что в модифицированном списке ранги элементов отличаются. Чтобы решить эту проблему, решим более общую задачу. Будем считать, что у каждого элемента есть вес <tex>w_i</tex>, а ранг элемента это сумма весов до конца списка. Для решения исходной задачи в самом начале присвоим каждому элементу вес 1.
Теперь, если у нас есть 3 последовательных элемента x, y, z (<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 элементу крайне неэффективно, но если выкидывать какую-то весомую часть, то нужно быстро пересчитывать веса элементов. Сделать это можно с помощью уже рассмотренного Join, однако необходимо наложить ограничение на множество удаляемых элементов: никакие два удаленных элемента не должны идти подряд в списке. В противном случае может образоваться цепочка из удаленных элементов произвольной длины. Веса всех элементов этой цепочки нужно будет прибавить к первому не удаленному элементу, что равносильно самой задаче List Ranking, которую мы и пытаемся решить.
Рассмотрим как именно изменять веса элементов. Построим и отсортируем по 1 элементу 3 таблицы:
1) Таблица Conn из пар <tex>(i, j)</tex>, где каждая пара значит что после i-ого элемента идет j-ый
2) Таблица W из пар <tex>(i, w_i)</tex>, хранящая веса элементов
3) Таблица D, в которой записаны удаляемые элементы
Теперь пройдемся 3 указателями по этим таблицам, и если нам встречается триплет вида <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)</tex>, где каждая пара значит что после i-ого элемента идет j-ый
2) Таблица W из пар <tex>(i, w_i)</tex>, хранящая веса элементов
3) Таблица R из пар <tex>(i, r_i)</tex>, в которой записаны ранги элементов модифицированного списка
Также пройдемся 3 указателями по этим таблицам, и если нам встречается триплет вида <tex>(i, j) \in Conn</tex>, <tex>(i, w_i) \in W</tex>, <tex>(i, r_i) \in D</tex>, то добавим пару <tex>(j, r_i + w_i)</tex> в таблицу новых рангов.
Открытым остался только вопрос какие элементы удалять. В идеале было бы удалять каждый второй элемент (больше нельзя, иначе ограничение будет нарушено), но понять какой элемент четный, какой нечетный не проще чем сама задача ранжирования. Один из способов удалять элементы вероятностный. Для каждого элемента в списке бросим монетку. После этого выбросим всех орлов, после которых в списке идет решка (делается опять же с помощью Join). В таком случае никакие два выброшенных элемента не будут идти в списке подряд.
Подсчитаем матожидание выброшенных элементов {{---}} <tex>E(D) = \sum\limits_{(i, j) \in Conn}\frac{1}{4} = \frac{N}{4}</tex>
Тогда время работы алгоритма можно оценить с помощью рекурренты <tex>T(N) = T\left(\dfrac{3N}{4}\right) + Sort(N) = \mathcal{O}(Sort(N))</tex>
