Изменения

оперативной памяти и имеют высокую емкость, они гораздо медленнее из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка <tex>100</tex> ns, а к HDD {{---}} порядка <tex>10</tex> ms (<tex>10^{-7}</tex> s и <tex>10^{-2}</tex> s). Однако, основное время тратится на позиционирование головки жесткого диска, из-за чего разрыв в скорости последовательного чтения не такой большой. Из оперативной памяти можно читать со скоростью порядка <tex>10</tex> GB/s, с HDD {{---}} порядка <tex>100</tex> MB/s.

Так как время позиционирования головки внешнего диска весьма непредсказуемо, то необходимо взять размер блока таким, чтобы время чтения самих данных было гораздо больше, чем время позиционирования к этим данным. То есть должно выполняться <tex>seek\_time \leqslant read\_time</tex>. Если <tex>read\_time = 100</tex> MB/s, <tex>seek\_time = 10</tex> ms , то <tex>B \geqslant 1</tex> MB. На практике, размер блока нужно брать больше чем <tex>1</tex> MB (около <tex>8-16</tex> MB), так как тогда время позиционирования станет существенно меньше времени чтения.

Поскольку мы легко умеем выполнять слияние упорядоченных последовательностей, логичным шагом будет рассмотреть сортировку во внешней памяти. Рассмотрим некоторую модификацию алгоритма [[Сортировка слиянием|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>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>.

Данная задача заключается в следующем: дан односвязный список, то есть для каждого элемента известно, какой идет следующим за ним. Необходимо для каждого элемента определить, каким он является по счету с конца списка. Расстояние до конца списка будем называть ''рангом'' элемента. Не смотря Несмотря на простоту задачи в ''RAM-машине'', во внешней памяти задача имеет нетривиальное решение. Из-за того что все данные лежат хаотично, мы не можем просто пройтись по списку, это может потребовать слишком много операций ввода-вывода.

Решим задачу следующим способом: выкинем из списка какую-то часть элементов, после чего рекурсивно посчитаем ответ для полученного списка. Затем, зная промежуточный ответ, восстановим ответ для исходной задачи. Первая проблема {{---}} в модифицированном списке ранги элементов отличаются. Чтобы решить эту проблему, рассмотрим более общую задачу. Будем считать, что у каждого элемента есть вес, а ранг элемента {{---}} это сумма весов до конца списка. Для решения исходной задачи в самом начале присвоим каждому элементу вес <tex>1</tex>.

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

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

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