Алгоритмы во внешней памяти. Базовые конструкции

Модель вычислений во внешней памяти

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

Но в таком случае размер данных, с которыми мы работаем, должен помещаться в оперативную память. Предположим, что ее размер порядка [math]10-100[/math] GB, а обработать нам нужно порядка [math]10[/math] TB информации. Очевидно, что необходимо использовать какую-то внешнюю память, например — жесткий диск. Хотя диски существенно дешевле оперативной памяти и имеют высокую емкость, они гораздо медленнее оперативной памяти из-за механического построения считывания. Для сравнения, время обращения к оперативной памяти порядка [math]100[/math] ns, а к HDD порядка [math]10[/math] ms. Разница колоссальная ([math]10^{-7}[/math] s и [math]10^{-2}[/math] s). Однако, основное время тратится на позиционирование головки жесткого диска, из-за чего разрыв в скорости последовательного чтения не такой большой. Из оперативной памяти можно читать порядка [math]10[/math] GB/s, с HDD — порядка [math]100[/math] MB/s.

Из-за описанного выше, для оценки сложности алгоритмов во внешней памяти была предложена другая модель. Модель говорит следующее — у нас есть какая-то внешняя память и процессор со своей внутренней памятью. Внутренняя память ограничена и имеет размер порядка [math]M[/math] машинных слов. Внешняя память имеет размер хотя бы порядка [math]N[/math] машинных слов, где [math]N[/math] — размер рассматриваемой задачи. Чтение и запись из внешней памяти происходит блоками последовательных данных размера [math]B[/math] — машинных слов. В качестве меры сложности принимается количество операций ввода-вывода, которые выполняет алгоритм, где одна операция ввода-вывода это либо чтение из внешней памяти одного блока размера [math]B[/math], либо запись.

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

Размер блока

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

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

Scan

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

Слияние упорядоченных последовательностей

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

Сортировка

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

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

Join

Рассмотрим следующую задачу — пусть у нас во внешней памяти есть 2 последовательности вида [math](ключ, значение)[/math]. Первая последовательность имеет вид [math](k_i, a_{k_i})[/math], вторая — [math](l_j, b_{l_j})[/math] и мы хотим получить последовательность вида [math](i, a_i, b_i)[/math] (не умоляя общности считаем что [math](k_1 \dots k_n)[/math] и [math](l_1 \dots l_n)[/math] являются перестановками чисел от 1 до n). Очевидно, что задача решается просто сортировками последовательностей по первому аргументу с проходом проходом по ним 2 указателями. Поэтому сложность алгоритма — [math]Sort(N)[/math].