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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Модель)
Строка 7: Строка 7:
  
 
У данной модели есть один существенный недостаток {{---}} мы никак не учитываем время, которое тратится на вычисления, а считаем только ''IO-complexity''. Из-за этого многие задачи в данной модели решаются быстрее, чем в модели с ''RAM-машиной'', потому что например прочитав какой-то блок, далее мы имеем право произвести экспоненциальный по сложности перебор и это никак не будет учитываться. Поэтому нужно иметь в виду, что данная модель стремится эффективно использовать жесткий диск, а не балансировать между использованием процессора и жесткого диска.
 
У данной модели есть один существенный недостаток {{---}} мы никак не учитываем время, которое тратится на вычисления, а считаем только ''IO-complexity''. Из-за этого многие задачи в данной модели решаются быстрее, чем в модели с ''RAM-машиной'', потому что например прочитав какой-то блок, далее мы имеем право произвести экспоненциальный по сложности перебор и это никак не будет учитываться. Поэтому нужно иметь в виду, что данная модель стремится эффективно использовать жесткий диск, а не балансировать между использованием процессора и жесткого диска.
 +
 +
== Размер блока ==
 +
Так как время позиционирования головки внешнего диска весьма непредсказуемо, то необходимо взять размер блока таким, чтобы время чтения самих данных было гораздо больше, чем время позиционирования к этим данным. То есть должно выполняться <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), так как тогда время позиционирования станет не просто существенно меньше времени чтения.

Версия 13:52, 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), так как тогда время позиционирования станет не просто существенно меньше времени чтения.