Модель ввода-вывода: различия между версиями

Несколько границ сложности особенно важны почти для всех алгоритмов и структур данных, эффективных с точки зрения модели ввода-вывода. ''Граница поиска'' в <math>\Theta (log_B \; n)</math> операций ввода-вывода, достижимая при использовании [[B-дерево (дерево многоканального поиска)|B-дерева]] [4], равна стоимости поиска элемента в упорядоченном наборе из n элементов, использующего только сравнения.

Сканирование списка из n последовательных элементов данных, очевидно, требует <math>\left \lceil \frac{n}{B} \right \rceil</math> операций ввода-вывода или, в модели PDM, <math>\left \lceil \frac{n}{DB} \right \rceil</math> операций. Такая ''граница сканирования'' обычно определяется как «линейное количество операций ввода-вывода», поскольку она эквивалентна временной границе O(n), необходимой для выполнения того же действия во внутренней памяти.

''Граница сортировки'' <math>sort(n) = \Theta \bigg( ( \frac{n}{B}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) </math> операций ввода-вывода обозначает стоимость сортировки n элементов, использующей только сравнения. Таким образом, она эквивалентна границе сортировки во внутренней памяти, составляющей <math>\Theta (n \; log \; n)</math>. В модели PDM граница сортировки составляет <math>\Theta \bigg( ( \frac{n}{DB}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) </math>. Эта граница может быть достигнута при помощи различных алгоритмов сортировки, включая алгоритмы внешнего слияния [1, 6] и сортировки распределением [1, 5].

Возможно, наибольший интерес представляет ''граница перестановки'', а именно – стоимость перегруппировки n элементов в заданном порядке, составляющая <math>\Theta (min(sort(n), n)) \;</math> [1] или <math>\Theta (min(sort(n), \frac{n}{D})) \;</math> в модели PDM [10]. Для всех практических целей она совпадает с границей сортировки. Отметим контраст с использованием внутренней памяти, при котором с поправкой на константный коэффициент перестановка имеет ту же стоимость, что и линейное сканирование. Поскольку почти все нетривиальные алгоритмические задачи включают задачу перестановки, в результате только самые простые задачи могут быть решены при помощи <math>O(scan(n)) \;</math> операций ввода-вывода; большинство задач требуют <math>\Omega (perm(n)) \;</math>, что, в сущности, представляет собой нижнюю границу <math>\Omega (sort(n)) \;</math>. Таким образом, в то время как алгоритмы на базе внутренней памяти, стремящиеся к линейному времени, должны максимально избегать использования сортировки как инструмента, алгоритмы на базе внешней памяти могут использовать сортировку, не опасаясь значительного превышения нижней границы. Это делает разработку оптимальных алгоритмов на базе ввода-вывода потенциально более простой, чем разработка алгоритмов на базе внутренней памяти. Однако это компенсируется тем обстоятельством, что, в отличие от работы во внутренней памяти, граница сортировки ''не'' равна границе поиска, умноженной на n, из чего следует, что алгоритмы, основанные на опросе поисковой структуры на базе дерева O(n) раз, обычно не переводятся в эффективные с точки зрения операций ввода-вывода алгоритмы. [[Буферные деревья]] [3] обеспечивают амортизированную границу поиска в <math>O \bigg( ( \frac{1}{B}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) </math> операций ввода-вывода, но могут использоваться только в случае, если вся последовательность обновлений и запросов известна заранее, и потому представляют собой ограниченное решение данной задачи.

В современных компьютерах применяется иерархическая память, включающая несколько уровней кэша, оперативную память (RAM) и один или несколько дисков. По мере увеличения расстояния от процессора возрастают задержки обращений к памяти, а также ее объемы. Для сглаживания этих возрастающих задержек данные перемещаются между уровнями памяти в виде блоков последовательных элементов данных. В результате стоимость обращения к памяти зависит от уровня иерархии, хранящего в этот момент элемент данных – разница между задержками обращения к кэшу L1 и к диску составляет примерно <math>10^6 \;</math> – а стоимость последовательности обращений к элементам данных, хранящимся на одном и том же уровне иерархии, зависит от количества блоков, по которым эти элементы распределены.

Традиционно алгоритмы разрабатывались с прицелом на минимизацию количества этапов вычислений; локальность обращений к памяти, необходимая для решения задачи с использованием возможно меньшего количества перемещений между уровнями памяти, в основном игнорировалась. Таким образом, эти алгоритмы хорошо работают на наборах данных небольшой величины, но не пользуются значительным преимуществом кэш-памяти и обычно не справляются с вычислениями во внешней памяти. Поскольку разница в задержке обращений к оперативной памяти и к диску максимально велика, модель ввода-вывода уделяет основное внимание устранению этого «затора». Двухуровневое представление иерархии памяти сохраняет простоту модели и хорошо подходит для анализа тщательно разработанных алгоритмов, обеспечивая наряду с этим неплохую практическую эффективность работы.

Много усилий было вложено в преобразование доказуемо эффективных с точки зрения операций ввода-вывода алгоритмов в высокоэффективные реализации. Можно привести в пример TPIE [8] и STXXL [7] – две библиотеки, содержащие высокооптимизированные и мощные примитивы для реализации алгоритмов, эффективных с точки зрения операций ввода-вывода. Но, несмотря на эти усилия, между теорией и практикой по-прежнему сохраняется значительный разрыв.

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

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

4. Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Inform. 1,173-189 (1972)