Сбалансированное многопутевое слияние
В основе метода внешней сортировки сбалансированным многопутевым слиянием является распределение серий исходного файла по m вспомогательным файлам B1, B2, ..., Bm и их слияние в m вспомогательных файлов C1, C2, ..., Cm. На следующем шаге производится слияние файлов C1, C2, ..., Cm в файлы B1, B2, ..., Bm и т.д., пока в B1 или C1 не образуется одна серия.
Многопутевое слияние является естественным развитием идеи обычного (двухпутевого) слияния.
Многофазная сортировка
При использовании рассмотренного выше метода сбалансированной многопутевой внешней сортировки на каждом шаге примерно половина вспомогательных файлов используется для ввода данных и примерно столько же для вывода сливаемых серий. Идея многофазной сортировки состоит в том, что из имеющихся m вспомогательных файлов (m-1) файл служит для ввода сливаемых последовательностей, а один - для вывода образуемых серий. Как только один из файлов ввода становится пустым, его начинают использовать для вывода серий, получаемых при слиянии серий нового набора (m-1) файлов. Таким образом, имеется первый шаг, при котором серии исходного файла распределяются по m-1 вспомогательному файлу, а затем выполняется многопутевое слияние серий из (m-1) файла, пока в одном из них не образуется одна серия.
Очевидно, что при произвольном начальном распределении серий по вспомогательным файлам алгоритм может не сойтись, поскольку в единственном непустом файле будет существовать более, чем одна серия. Предположим, например, что используется три файла B1, B2 и B3, и при начальном распределении в файл B1 помещены 10 серий, а в файл B2 - 6. При слиянии B1 и B2 к моменту, когда мы дойдем до конца B2, в B1 останутся 4 серии, а в B3 попадут 6 серий. Продолжится слияние B1 и B3, и при завершении просмотра B1 в B2 будут содержаться 4 серии, а в B3 останутся 2 серии. После слияния B2 и B3 в каждом из файлов B1 и B2 будет содержаться по 2 серии, которые будут слиты и образуют 2 серии в B3 при том, что B1 и B2 - пусты. Тем самым, алгоритм не сошелся.
|
|
|
| Число серий в файле B1 | Число серий в файле B2 | Число серий в файле B3 |
| 10 | 6 | 0 |
| 4 | 0 | 6 |
| 0 | 4 | 2 |
| 2 | 2 | 0 |
| 0 | 0 | 2 |
Рассмотрим, каким должно быть начальное распределение серий, чтобы алгоритм трехфазной сортировки благополучно завершал работу и выполнялся максимально эффективно. Метод трехфазной внешней сортировки дает желаемый результат и работает максимально эффективно (на каждом этапе сливается максимальное число серий), если начальное распределение серий между вспомогательными файлами описывается соседними числами Фибоначчи. Напомним, что последовательность чисел Фибоначчи начинается с 0, 1, а каждое следующее число образуется как сумма двух предыдущих: (0, 1, 1, 2, 3, 5, 8, 13, 21, ....)
|
|
|
При невозможности получить начальное распределение, соответствующее числам Фибоначчи, вводятся, так называемые пустые серии.
Улучшение эффективности внешней сортировки за счет использования основной памяти
Чем более длинные серии содержит файл перед началом применения внешней сортировки, тем меньше потребуется слияний и тем быстрее закончится сортировка. Поэтому до начала применения любого из методов внешней сортировки, основанных на применении серий, начальный файл частями считывается в основную память, к каждой части применяется один из наиболее эффективных алгоритмов внутренней сортировки (обычно Quicksort или Heapsort) и отсортированные части (образующие серии) записываются в новый файл. Кроме того, при выполнении распределений и слияний используется буферизация блоков файла(ов) в основной памяти. Возможный выигрыш в производительности зависит от наличия достаточного числа буферов достаточного размера.
ЛЕКЦИЯ 7. СРАВНЕНИЕ МЕТОДОВ СОРТИРОВКИ. ПОДГОТОВКА К КОНТРОЛЬНОЙ РАБОТЕ ПО ТЕМЕ «МЕТОДЫ СОРТИРОВКИ ДАННЫХ»
Цель лекции: дать обзор и сравнительный анализ методов сортировки.
|
|
|
Рассматриваемые вопросы: сравнительный анализ методов сортировки.
Приведем экспериментальные данные отличия одного метода от другого.
Затраты времени в методах сортировок на сравнения ключей, перенос элементов, управление циклами во многом зависят от отдельной вычислительной системы, но тем не менее результаты экспериментов довольно информативны.
Три столбца содержат времена сортировки уже упорядоченного массива, случайной перестановки и массива, расположенного в обратном порядке.
В начале (таб.1) приводятся цифры для 256 элементов, а ниже(таб.2) - для 2048.
таблица 1
| N=256 | упорядоченный | случайный | в обратном порядке |
| Простое включение | 0.02 | 0.82 | 1.64 |
| Бинарное включение | 0.12 | 0.70 | 1.30 |
| Прямой выбор | 0.94 | 0.96 | 1.18 |
| Пузырек | 1.26 | 2.04 | 2.80 |
| Шейкер | 0.02 | 1.66 | 2.92 |
| Шелл | 0.10 | 0.24 | 0.28 |
| Heap Sort (пирам древ) | 0.20 | 0.20 | 0.20 |
| QuickSort | 0.08 | 0.12 | 0.08 |
| Бинарное слияние | 0.18 | 0.18 | 0.18 |
Таблица 2
| N=2048 | упорядоченный | случайный | в обратном порядке |
| Простое включение | 0.22 | 50.74 | 103.64 |
| Бинарное включение | 1.16 | 37.66 | 76.06 |
| Прямой выбор | 58.18 | 58.34 | 73.46 |
| Пузырек | 80.18 | 128.84 | 178.66 |
| Шейкер | 8.16 | 104.44 | 187.36 |
| Шелл | 0.80 | 7.08 | 12.34 |
| Heap Sort (пирам древ) | 2.32 | 2.22 | 2.12 |
| QuickSort | 0.72 | 1.22 | 0.76 |
| Бинарное слияние | 1.98 | 2.06 | 1.98 |
|
|
|
Некоторые выводы.
1. Улучшение двоичного включения по сравнению с прямым включением почти ничего не дает, а в случае упорядоченного массива даже получается отрицательный эффект.
2. Пузырьковая сортировка определенно наихудшая из всех сравниваемых.
3. Ее усовершенствованная версия, шейкерная сортировка, продолжает оставаться плохой по сравнению с прямым включением и прямым выбором (за исключением случая уже упорядоченного массива).
4. Quicksort лучше в 2-3 раза, чем Heapsort. Она сортирует массив, расположенный в обратном порядке, практически с той же скоростью, что и уже упорядоченный.
Дата добавления: 2018-05-02; просмотров: 1031; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!