Анпоо колледж воронежского института высоких технологий
 Скачать 440.67 Kb.
|
1.2 Принципы внешней сортировки.Внешняя сортировка - это термин для обозначения класса алгоритмов сортировки, которые могут обрабатывать огромные объемы данных. Внешняя сортировка необходима, когда сортируемые данные не помещаются в основную память вычислительного устройства (обычно оперативную) и вместо этого должны находиться в более медленной внешней памяти (обычно на жестком диске). Внешняя сортировка обычно использует гибридную стратегию сортировки-слияния. На этапе сортировки фрагменты данных, достаточно маленькие, чтобы поместиться в основной памяти, считываются, сортируются и записываются во временный файл. На этапе слияния отсортированные под файлы объединяются в один большой файл. Внешняя сортировка — это метод хранения данных во вторичной памяти, загрузки данных по частям в основную память и последующей сортировки их там. Внешняя сортировка так названа, поскольку предназначен для освобождения буфера памяти при работе с внешними устройствами. Отсортированные данные хранятся в промежуточных файлах. Наконец, эти файлы объединяются для получения отсортированных данных. Таким образом, методы внешней сортировки упрощают сортировку больших объемов данных. Для внешней сортировки невозможно поместить все данные в одну память. В этом случае часть памяти должна храниться на таких носителях, как жесткие диски или компакт-диски. Требования внешней сортировки возникают, когда данные, которые необходимо хранить в основной памяти, не помещаются. Фактически следование за ним состоит из двух фаз. Этап сортировки: на этом этапе большой объем данных сортируется в промежуточный файл. Этап слияния: на этом этапе отсортированные файлы объединяются в один большой файл. Одним из лучших примеров внешней сортировки является внешняя сортировка слиянием. Внешняя сортировка слиянием — это метод, при котором данные хранятся в промежуточных файлах, каждый промежуточный файл сортируется отдельно и объединяется или объединяется для получения отсортированных данных. Пример: Предположим, вы хотите отсортировать 10 000 записей. Для этого нам нужно применить внешний метод сортировки слиянием. Предположим, что основная память способна хранить 500 записей на блок, а размер каждого блока равен 100 записям. Двунаправленная сортировка слиянием — это метод, который работает в два этапа, описанных ниже. Этап 1: Сначала разделите записи на блоки, затем используйте две входные ленты для перестановки отдельных записей. Этап 2: На этом этапе отсортированные блоки объединяются и создается один отсортированный файл с использованием двух выходных лент. Таким образом, мы можем сказать, что двунаправленная сортировка слиянием использует две входные ленты и две выходные ленты для сортировки данных. Алгоритм двусторонней сортировки слиянием: Шаг 1) Разделите элементы на блоки размером M. Отсортируйте каждый блок и запишите его на диск. Шаг 2) Объедините два прогона Прочитайте первое значение в каждом из двух прогонов. Затем сравните и отсортируйте их. Запишите отсортированные записи на выходную ленту. Шаг 3) Повторите шаг 2, чтобы увеличить прогон с чередованием лент. Наконец, мы получаем один отсортированный список. Анализируя вторичные источники по теме внешней сортировки, можно отметить, что наиболее распространена простая сортировка слиянием[ 1]. В нем количество сравнений и перестановок оценивается как O (nlog (n)). Однако он не учитывает тот факт, что последовательность уже может быть частично упорядочена [1 ]. Тот же автор отмечает, что такая внешняя сортировка, как многофазное слияние дает ожидаемый результат, объединяя максимальное количество рядов на каждом этапе, если начальное распределение рядов на вспомогательном файле описывается соседними числами Фибоначчи [1]. 1.3. Каскадная сортировкаПри рассмотрении каскадной сортировки или сортировки методом каскадного слияния следует отметить, что данный метод относится к внешней улучшенной сортировке, не простым слиянием . Каскадное слияние объединяет два списка отсортированных данных за один раз, пока не останется только один отсортированный список, и используется для сортировки в памяти, поскольку оно более эффективно, чем алгоритм дерева поиска. Мы стремимся к тому, чтобы наша реализация имела высокую производительность в памяти, которая плавно снижается по мере превышения лимита доступной памяти. При каскадной сортировке мы объединяем два блока отсортированных данных за один раз, пока не останется только один отсортированный блок. Естественно, мы хотим использовать все доступные потоки для вычисления слияния. Если у нас гораздо больше отсортированных блоков, чем потоков, мы можем назначить каждый поток для слияния двух блоков. Однако по мере слияния блоков у нас не будет достаточно блоков, чтобы все потоки были заняты. Это особенно медленно, когда объединяются последние два блока: Один поток должен обработать все данные. Пересечения на пути слияния можно эффективно вычислить с помощью двоичного поиска. Если мы знаем, где находятся пересечения, мы можем объединять разделы отсортированных данных независимо друг от друга параллельно. Это позволяет нам эффективно использовать все доступные потоки для всей фазы слияния. Простой прием для уменьшения ввода-вывода - это зигзагообразное перемещение по парам блоков для слияния в каскадной сортировке слиянием. Это показано на рисунке ниже (пунктирные стрелки указывают, в каком порядке объединяются блоки). Перебирая блоки зигзагообразно, мы начинаем итерацию с объединения последних блоков, которые были объединены в предыдущей итерации. Эти блоки, вероятно, все еще находятся в памяти, что позволяет нам сэкономить несколько драгоценных операций чтения/записи. При применении различных методов сортировки также стоит не забывать о временных рамках выполения алгоритма. Временная сложность алгоритма определяется количеством входных данных. Для простоты входные данные представляются параметром n. Этот параметр пропорционален величине обрабатываемого набора данных и может обозначать: • размер массива или файла при сортировке или поиске; • степень полинома; • количество символов в строке; Алгоритм каскадной сортировки подробно описан в третьем томе Д. Кнута «Искусство программирования». Как он отмечает в своей книге [6 ],каскадное слияние было открыто раньше многофазной сортировки, в 1959 г. Рассмотрим таблицу данных 1 с прогонами – сортировкой данных. Таблица 1
Каскадное слияние, как и при многофазной сортировке, начинается следующим образом. Каждая строка в таблице представляет собой полный проход над всеми данными. Проход 2, например, получается путем пятистороннего слияния с {Tl, T2, T3, T4, T5} на T6, пока T5 не станет пустым (это помещает 15 прогонов относительной длины 5 на T6), затем четырехстороннего слияния с {Tl, T2, T3, T4} на T5, затем трехстороннего слияния на T4, двухстороннего слияния на T3 и, наконец, одностороннего слияния (операция копирования) с Tl на T2. Проход 3 получается таким же образом, сначала выполняется пятистороннее слияние, пока одна лента не станет пустой, затем четырехстороннее слияние, и так далее. Понятно, что операции копирования не нужны, и их можно было бы исключить. В таблице выше звездочкой отмечены те элементы, которые были просто скопированы; только 25 из 950 обработанных прогонов относятся к этому типу. Большая часть времени посвящена пяти- и четырехстороннему слиянию. Следует отметить, что высокий порядок слияния не гарантирует эффективности. В таблице ниже приведены характеристики производительности каскадного слияния. Идеальные распределения" для каскадного слияния легко получить, работая в обратном направлении от конечного состояния (1,0, ... ,0). Интересно отметить, что относительные величины этих чисел проявляются и в диагоналях правильного (2T - l)-стороннего многоугольника. Например, пять диагоналей в семиугольнике имеют относительные длины, почти равные 190, 175, 146, 105 и 55. Таблица 2
|