286
правок
Изменения
Модель
== Модель вычислений во внешней памяти ==
Обычно оценка сложности рассматриваемых алгоритмов происходит в модели под названием ''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-машиной'', потому что например прочитав какой-то блок, далее мы имеем право произвести экспоненциальный по сложности перебор и это никак не будет учитываться. Поэтому нужно иметь в виду, что данная модель стремится эффективно использовать жесткий диск, а не балансировать между использованием процессора и жесткого диска.
