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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сортировка)
Строка 10: Строка 10:
 
== Размер блока ==
 
== Размер блока ==
 
Так как время позиционирования головки внешнего диска весьма непредсказуемо, то необходимо взять размер блока таким, чтобы время чтения самих данных было гораздо больше, чем время позиционирования к этим данным. То есть должно выполняться <tex>seek\_time \leqslant read\_time</tex>. Если <tex>read\_time = 100</tex> MB/s, то <tex>B \geqslant 1</tex> MB. На практике, размер блока нужно брать больше чем <tex>1</tex> MB (около <tex>8-16</tex> MB), так как тогда время позиционирования станет не просто существенно меньше времени чтения.
 
Так как время позиционирования головки внешнего диска весьма непредсказуемо, то необходимо взять размер блока таким, чтобы время чтения самих данных было гораздо больше, чем время позиционирования к этим данным. То есть должно выполняться <tex>seek\_time \leqslant read\_time</tex>. Если <tex>read\_time = 100</tex> MB/s, то <tex>B \geqslant 1</tex> MB. На практике, размер блока нужно брать больше чем <tex>1</tex> MB (около <tex>8-16</tex> MB), так как тогда время позиционирования станет не просто существенно меньше времени чтения.
 +
 +
== Примитивные задачи ==
 +
=== Scan ===
 +
Рассмотрим следующую задачу {{---}} на диске записаны <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 это степень двойки). Во внешней памяти не выгодно начинать с последовательностей длины 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)</tex>.
 +
 +
В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины M, а не B. Хотя итоговая сложность и станет <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{M}\right)</tex>, но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.

Версия 15:01, 16 июня 2019

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

Обычно оценка сложности рассматриваемых алгоритмов происходит в модели под названием 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)[/math].

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