Изменения

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

Но в таком случае размер данных, с которыми мы работаем, должен помещаться в оперативную память. Предположим, что ее размер порядка <tex>10-100</tex> GB, а обработать нам нужно порядка <tex>10</tex> TB информации. Очевидно, что необходимо использовать какую-то внешнюю память, например {{---}} жесткий диск. Хотя диски существенно дешевле

оперативной памяти и имеют высокую емкость, они гораздо медленнее оперативной памяти из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка <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(\sum\limits_{i = 1}^{k}N_i)</tex>.

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

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

Рассмотрим следующую задачу {{---}} пусть у нас Пусть во внешней памяти есть 2 последовательности вида <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> являются перестановками чисел от 1 до N). Очевидно, что задача решается просто сортировками последовательностей по первому аргументу с последующим проходом по ним 2 указателями. Поэтому сложность алгоритма {{---}} <tex>Sort(N)</tex>.