Внешняя сортировка
Cтраница 4
Другой важной проблемой абстрактной сортировки является проблема внешней сортировки ( external sorting); в этом случае сортируемый файл обладает такими огромными размерами, что не помещается в оперативной памяти. Стоимость доступа к индивидуальным записям может оказаться непомерно высокой, в силу этого обстоятельства мы должны использовать абстрактную модель, в которой записи передаются между внешними устройствами в виде блоков больших размеров. Мы рассмотрим два алгоритма внешней сортировки и воспользуемся соответствующей моделью, чтобы сравнить их между собой. [46]
Виртуальная память отличается от других видов памяти как поддерживающей аппаратурой, так и операционной системой, под управлением которой осуществляется работа с ней. Во-первых, даже при внутренней сортировке в виртуальной памяти реальная обработка выполняется с использованием внешней памяти, поэтому необходимо учитывать ее влияние - неизбежные при этом затраты на запись и считывание. И наоборот, считывание и запись при внешней сортировке почти идентичны перемещениям записей в виртуальной памяти. Из соображений практического удобства обычно гораздо охотнее используют внутреннюю сортировку. При этом важным фактором, влияющим на эффективность, является интенсивность использования массы сильно различающихся адресов за сравнительно короткие временные интервалы. [47]
 |
Сортировка сбалансированным слиянием ( случай р 3, число файлов 6. [48] |
Для данного случая это справедливо, однако, когда р возрастает в процессе сортировки, проблема оказывается несколько сложнее. Трудности, связанные с этим, рассматриваются при обсуждении эффективности внешней сортировки. [49]
Существует несколько различных способов сортировки. Можно выделить два основных этапа: этап внутренней сортировки и этап внешней сортировки, проходящий в несколько стадий. На этапе внутренней сортировки упорядочиваемый файл разбивается на ряд порций, каждая из которых не превосходит первоначально емкости ОЗУ. Каждая такая порция загружается в ОЗУ, где все элементы порции располагаются в порядке возрастания ( или убывания) индексов, а затем переписываются обратно на носитель внешнего накопителя в одну из выделенных для этого областей ( участков носителя), где она располагается вслед за ранее записанными туда порциями. [50]
Первым шагом при создании высокоэффективной программы сортировки файлов сверхбольших размеров является создание копии файла. Вторым шагом может быть представление исходного файла в обратном порядке. Все трудности, с которыми приходится сталкиваться при решении этих задач, возникают и при реализации внешней сортировки. В процессе сортировки иногда приходится выполнять одну из этих операций. Цель использования абстрактной модели состоит в том, чтобы отделить проблемы построения программной реализации от проблем разработки алгоритма. [51]
Если сортируемый файл полностью помещается в оперативной памяти, то используемый в этом случае метод сортировки называется внутренним. Сортировка файлов, хранящихся на магнитной ленте или диске, называется внешней. Основное различие между этими двумя методами заключается в том, что в условиях внутренней сортировки доступ к любому элементу не представляет трудностей, в то время как в условиях внешней сортировки возможен только последовательный метод доступа или, по меньшей мере, доступ к блокам больших размеров. Некоторые из внешних методов сортировки рассматриваются в главе 11, однако большая часть исследуемых алгоритмов принадлежит к категории внутренней сортировки. [52]
В методах сортировки, обсуждавшихся в предыдущем разделе, мы полагали, что таблица умещается в быстродействующей внутренней памяти. Например, часто бывает необходимо сортировать отдельные предметы во время исчерпывающего поиска ( гл. Однако задача сортировки таблицы, которая слишком велика для основной памяти, служит хорошей иллюстрацией работы с данными большого объема, и поэтому в этом разделе мы обсудим важные идеи внешней сортировки. [53]
Язык ПЛ / 1 дает возможность описать все виды редактирования данных, отреагировать на различные виды прерываний и вызвать программу сортировки. Только на этом языке можно эффективно вводить в программу просмотр таблицы вместо обработки файлов, когда выбираемая информация размещается в оперативной памяти. На практике такая возможность часто бывает необходима, поскольку за один просмотр каждой группы файлов можно подготовить данные, относящиеся к важнейшим продуктам и предприятиям отрасли в виде таблицы в оперативной памяти, и заменить внешние сортировки внутренними. [54]
Страницы: 1 2 3 4