Анпоо колледж воронежского института высоких технологий
 Скачать 440.67 Kb.
|
Раздел 1.1.1 Алгоритмы сортировкиПрежде, чем описывать алгоритмы сортировки, внешней или каскадной, рассмотрим проблему сортировки коллекций записей, слишком больших, чтобы поместиться в основной памяти компьютера. Поскольку записи должны находиться в периферийной или внешней памяти, такие методы сортировки называются внешними сортировками. В отличие от внутренних сортировок, которые предполагают, что сортируемые записи хранятся в основной памяти. Сортировка больших коллекций записей является центральным элементом многих приложений, таких как обработка платежных ведомостей и других больших баз данных бизнеса. Как следствие, было разработано множество алгоритмов внешней сортировки. Много лет назад разработчики алгоритмов сортировки стремились оптимизировать использование конкретных аппаратных конфигураций, таких как несколько ленточных или дисковых накопителей. Сегодня большинство вычислений выполняется на персональных компьютерах и рабочих станциях низкого класса с относительно мощными процессорами, но только одним или максимум двумя дисковыми накопителями. Представленные здесь методы направлены на оптимизацию обработки данных на одном дисковом накопителе. Такой подход позволяет нам охватить наиболее важные вопросы внешней сортировки, пропуская многие менее важные детали, зависящие от машины. Когда коллекция записей слишком велика, чтобы поместиться в основной памяти, единственным практическим способом сортировки является считывание некоторых записей с диска, их перестановка, а затем запись обратно на диск. Этот процесс повторяется до тех пор, пока файл не будет отсортирован, причем каждая запись может быть прочитана много раз. Учитывая высокую стоимость дискового ввода-вывода, неудивительно, что основной целью алгоритма внешней сортировки является минимизация количества считываний информации с диска или записи на него. Определенное количество дополнительной обработки процессора может быть выгодно обменено на уменьшение количества обращений к диску. Прежде чем обсуждать методы внешней сортировки, рассмотрим еще раз базовую модель доступа к информации с диска. Файл, подлежащий сортировке, рассматривается программистом как последовательная серия блоков фиксированного размера. Предположим (для простоты), что каждый блок содержит одинаковое количество записей данных фиксированного размера. В зависимости от приложения, запись может состоять всего из нескольких байт, не содержащих практически ничего, кроме ключа, или может состоять из сотен байт с относительно небольшим ключевым полем. Предполагается, что записи не пересекают границы блоков. Эти допущения могут быть смягчены для специальных приложений сортировки, но игнорирование таких сложностей делает принципы более понятными. Напомним, что сектор - это основная единица ввода-вывода. Другими словами, все чтения и записи на диск выполняются для одного или нескольких полных секторов. Размер сектора обычно равен двум, в диапазоне от 512 до 16K байт, в зависимости от операционной системы, размера и скорости дискового накопителя. Размер блока, используемый для внешних алгоритмов сортировки, должен быть равен или кратен размеру сектора. Согласно этой модели, алгоритм сортировки считывает блок данных в буфер основной памяти, выполняет некоторую обработку и в определенное время записывает его обратно на диск. Напомним, что чтение или запись блока с диска занимает порядка миллиона раз больше времени, чем обращение к памяти. Исходя из этого факта, мы можем обоснованно ожидать, что записи, содержащиеся в одном блоке, могут быть отсортированы внутренним алгоритмом сортировки, за меньшее время, чем требуется для чтения или записи блока. При хороших условиях чтение из файла в последовательном порядке более эффективно, чем чтение блоков в случайном порядке. Учитывая значительное влияние времени поиска на доступ к диску, может показаться очевидным, что последовательная обработка быстрее. Однако важно понять, при каких обстоятельствах последовательная обработка файлов действительно быстрее, чем случайный доступ, поскольку это влияет на наш подход к разработке алгоритма внешней сортировки. Эффективный последовательный доступ основан на том, что время поиска должно быть минимальным. Первое требование заключается в том, чтобы блоки, составляющие файл, действительно хранились на диске в последовательном порядке и близко друг к другу, желательно заполняя небольшое количество смежных дорожек. По крайней мере, количество экстентов, составляющих файл, должно быть небольшим. Пользователи обычно не имеют особого контроля над расположением своего файла на диске, но запись файла сразу в последовательном порядке на диск с большим процентом свободного места увеличивает вероятность такого расположения. Алгоритм сортировки используется для перестановки заданного массива или списка элементов в соответствии с оператором сравнения элементов. Оператор сравнения используется для определения нового порядка элементов в соответствующей структуре данных. Алгоритм сортировки — это алгоритм, упорядочивающий элементы списка в определенном порядке. Наиболее часто используемые порядки - это числовой порядок и лексикографический порядок. Эффективная сортировка важна для оптимизации использования других алгоритмов (например, алгоритмов поиска и слияния), которые требуют, чтобы входные данные находились в отсортированном списке. Это также часто полезно для нормализации данных и создания удобочитаемого вывода. Формально вывод должен удовлетворять двум условиям: 1. Вывод осуществляется в неубывающем порядке (каждый элемент не больше предыдущего, следуя желаемому общему порядку). 2. Выходом является перестановка (перестановка) входных данных. Кроме того, хотя данные часто рассматриваются как массив, допускающий произвольный доступ, а не как список, разрешающий только последовательный доступ, алгоритмы часто могут применяться к любому типу данных, с соответствующими изменениями. |