Изменения

оперативной памяти и имеют высокую емкость, они гораздо медленнее из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка <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>M</tex> машинных слов. Внешняя память считается безграничной в рамках рассматриваемой задачи, то есть имеет размер хотя бы порядка <tex>N</tex> машинных слов, где <tex>N</tex> {{---}} размер задачи. Чтение и запись из внешней памяти происходит блоками последовательных данных размера <tex>B</tex> машинных слов. В качестве меры сложности принимается количество операций ввода-вывода, которые выполняет алгоритм, где одна операция ввода-вывода это либо чтение из внешней памяти одного блока размера <tex>B</tex>, либо запись.

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

== Примитивные Базовые задачи ==

На диске записаны <tex>N</tex> чисел, нужно найти их сумму (например, по какому-нибудь модулю). Очевидно, что эта задача равносильна просто считыванию с диска. Сложность линейного сканирования данных с диска {{---}} <tex>\left\lceil\dfrac{N}{B}\right\rceil = Scan(N)</tex>. Важно заметить, что из-за округления, в общем случае <tex>\sum\limits_{i = 1}^{k}Scan(N_i) \neq Scan\left(\sum\limits_{i = 1}^{k}N_i\right)</tex>.

Пусть имеется две упорядоченные последовательности размера <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>3</tex> таблицы вида:

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