Внешняя сортировка

Cтраница 3

Такие возможности языка ДИОД, как организация вложенных циклов выборки и обработки данных, организация вызова подпрограмм, обращение к внешней сортировке ОС ЕС, предоставление системных функций по работе со статистической информацией, форматированный ввод и обновление информации в БД и некоторые другие возможности, позволяют рассматривать язык ДИОД как язык программирования высокого уровня. Подготовленные администратором задач программы на языке ДИОД позволяют конечному пользователю решать функциональные задачи в диалоговом режиме в виде последовательных шагов, в число которых входит вызов макетов запросов или макетов ввода ( обновления), последовательное заполнение отдельных страниц макетов входными данными, ввод или обновление информации в БД, а также получение различного рода справок и сложных многостраничных отчетов. [31]

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

Библиотека стандартных программ ( БСП) Минск-32 содержит сотни стандартных программ, ориентированных на решение различных задач: перевод чисел из одной системы счисления в другую, редактирование информации, обработка данных, корректировка массивов, внутренняя сортировка, выборка, слияние и внешняя сортировка информации, решение задач линейного программирования, решение задач сетевого планирования, элементарные и специальные функции действительного, чисто мнимого и комплексного аргумента, программированная арифметика, вычисление корней алгебраических и транс-цедентных уравнений, операции с матрицами и векторами, вычисление определителей и решение систем линейных алгебраических уравнений, определение характеристического полинома, собственных значений и собственных векторов матрицы, численное решение обыкновенных дифференциальных уравнений, численное интегрирование, интерполяция и аппроксимация функций, специальные функции действительного и чисто мнимого аргумента, минимизация функции многих переменных, решение задач математической статистики. [33]

Внешняя сортировка составляет часть таких приложений, как обработка расчетов, при которой в работу вовлекается гораздо больше элементов, чем можно сразу запомнить в оперативной памяти. Поэтому методы внешней сортировки, применимые к данным, находящимся на внешних устройствах памяти ( таких, как диски или магнитные ленты), имеют огромное коммерческое значение. [34]

При выборе более производительного метода внешней сортировки больших массивов необходимо учитывать, что основное время приходится на подвод заданных зон носителя информации и обмен между внешней и оперативной памятью. При организации алгоритма внешней сортировки следует учитывать наличие вспомогательных внешних носителей, совмещение подвода с выполнением других операций, очередность использования внешних носителей, возможность их параллельной работы. [35]

Распределение порций файла и областей внешнего накопителя в процессе внешней сортировки. [36]

Совокупность порций, записанных в одной области, можно рассматривать как матрицу, записанную в порядке возрастания номеров строк, в которой индексом строки является номер порции, а индексом столбца - исходный индекс элемента. Каждая стадия этапа внешней сортировки, в связи с этим, представляет собой операцию структурирования - объединения всех матриц, записанных в исходных областях. [37]

Если в среде виртуальной памяти используется внешняя сортировка, управляемая прикладной программой, имеет смысл практически используемое пространство памяти организовать в реальной, а не в виртуальной памяти. Во всяком случае для внешней сортировки должен обеспечиваться достаточный объем реальной памяти. Если это требование не выполняется, использование виртуальной памяти может привести к заметному снижению эффективности сортировки. [38]

Мы переходим к рассмотрению другого аспекта задачи абстрактной сортировки, которая возникает, когда сортируемый файл настолько велик, что не помещается целиком в оперативной памяти Компьютера. Существует множество различных типов устройств внешней сортировки, которые накладывают различные ограничения на атомарные операции, применяемые при реализации таких видов сортировки. Кроме того, будет полезно изучить методы сортировки, использующие две простейшие базовые операции: операция считывания ( read) данных из внешнего запоминающего устройства в оперативную память и операция записи ( write) данных из оперативной памяти на внешнее запоминающее устройство. Мы полагаем, что стоимость этих двух операции настолько выше стоимости простейших примитивных вычислительных операций, что последние в дальнейшем мы можем полностью игнорировать. [39]

Различные абстрактные машины, рассматриваемые в этой главе, достаточно просты, однако заслуживают подробного изучения, поскольку инкапсулируют в себе конкретные ограничения, которые могут оказаться критичными для некоторых приложений сортировки. Аппаратные средства сортировки низкого уровня должны состоять из простых компонентов; внешняя сортировка в общем случае требует поблочного доступа к особо крупным файлам данных, а параллельная сортировка накладывает определенные ограничения на связи с процессорами. С одной стороны, мы не можем в полной мере воспользоваться подробной моделью машины, которая полностью соответствует конкретной реальной машине, с другой стороны, абстракции, которые мы рассматриваем, приводят нас не только к теоретическим формулировкам, содержащим информацию о наиболее важных ограничениях, но также и к весьма интересным алгоритмам, которые можно использовать непосредственно на практике. [40]

Корректировка по таблице применяется тогда, когда число корректировочных записей небольшое и заведомо весь корректировочный файл может разместиться в оперативной памяти машины, образуя таблицу. Достоинство метода состоит в том, что при его использовании можно отказаться от трудоемкой внешней сортировки файла корректуры, заменив ее внутренней сортировкой таблицы. Работа программы разбивается на три этапа: ввод в главную память всех записей файла корректуры с одновременным контролем и формированием таблицы; внутренняя сортировка записей таблицы; корректировка методом слияния последовательности записей в таблице с корректируемым файлом и образованием новой версии файла. Здесь слияние логически выполняется согласно предыдущей схеме ( см. рис. 2.14), только операция чтения корректировочной записи заменяется выборкой очередной записи из таблицы. [41]

Хотя алгоритмы, основанные на слиянии, и приемлемы для внутренней сортировки, более естественно рассматривать их как методы внешней сортировки, и поэтому отнесем их к разд. [42]

Полученная схема более трудоемка, чем предыдущая, поскольку включает две сортировки и два просмотра файлов, но она не накладывает ограничений на длину файлов. Если количество предприятий группы зафиксировано и все выбираемые данные могут разместиться в главной памяти, то вместо промежуточных файлов можно построить выборочные таблицы и заменить внешние сортировки внутренними или подобрать данные сразу в таблицу, просматривая поочередно каждый из файлов. [43]

С одной стороны, они образуют основу более сложных методов, с другой стороны, полезны и сами по себе для малых списков и как внутренние алгоритмы для внешних сортировок. По ряду причин обсуждение факторов, влияющих на производительность сортировки, дано в конце гл. [44]

Составляющая, зависящая от метода - это время операций в АЛУ. По данным [7] разница в значениях этой составляющей, определяемая различием методов, выражается примерно в 30 %, а сама продолжительность этапа че превышает 10 - 15 % от времени внешней сортировки. [45]

Страницы: 1 2 3 4