Алгоритмы внешней сортировки (часть II, естественная сортировка) Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ЯЗЫКИ ПРОГРАММИРОВАНИЯ / ПРОГРАММИРОВАНИЕ

Сортировка данных © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Сортировка – процесс перестановки элементов некоторого множества в определенном порядке. Цель сортировки – упрощение поиска данных в этом множестве. Задача сортировки данных часто возникает при разработке программного обеспечения. Алгоритмы сортировки можно разделить на: алгоритмы внутренней сортировки; алгоритмы внешней сортировки убываниевозрастание

Недостатки алгоритмов простой и сбалансированной сортировки слиянием 3 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Доступ к данным на внешнем устройстве занимает существенное время Рассмотренные алгоритмы сортировки не обладают свойством естественности поведения. Естественность поведения – эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Свойство слияния двух последовательностей 4 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Серия (run) – упорядоченная подпоследовательность { a i, a i+1, … a i+j } максимальной длины, такая что: a k a k + 1, k = i, i+1, … (i + j – 1) a i – 1 > a i, a i + j > a i+j+1 Если последовательность c образована путем слияния a и b, содержащих m a и m b серий, то m c = max(m a, m b ). Если серии распределены по последовательностям a и b равномерно (m a = m b ± 1), то после слияния количество серий уменьшается в два раза. => количество пересылок данных в худшем случае будет равно n[log 2 n]

Доказательство свойства слияния 5 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» m c = max(m a, m b )..., x i x i+1, , y j y j+1, , {x i, y j }{x i +1, y j+1 }, серия kсерия k+1 Пусть выполнено слияние k-х серий a и b в k-ю серию с. Последним элементом k-й серии c будет x i или y j. При этом первым элементом следующей серии будет x i+1 или y j+1. Таким образом количество серий не может уменьшиться. Согласно определению слияния серий их количество не увеличивается a b c

Метод естественной сортировки слиянием (natural merge) 6 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» b c b c Проход 1 Проход 2

3 3 Метод естественной сортировки слиянием (natural merge) 7 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» b c b c Проход 2 Проход 3

Метод естественной сортировки слиянием (natural merge) 8 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Метод Размер массива Проходов Простая сортировка 18 ? Сбалансированная сортировка ? Естественная сортировка 3

Метод естественной сортировки слиянием (natural merge) 9 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Метод Размер массива Проходов Простая сортировка 18 5 Сбалансированная сортировка 5 Естественная сортировка 3

Алгоритм естественной сортировки 10 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

Алгоритм естественной сортировки 11 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ввод n, a do (b, c) DISTRIB_R(a, n) (a, r) MERGE_R(b, c, a) while ( r > 1 ) DISTRIB _R(a, n, k) b, c while a do COPYRUN(a, b) if a then COPYRUN(a, c) return (b, c) MERGE_R(b, c, a) a r 0 while (b ) И (c ) do MERGERUN(b, c, a) r r + 1 while b do COPYRUN(b, a) r r + 1 while c do COPYRUN(c, a) r r + 1 return (r, a)

Алгоритм слияния серий 12 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» b c MERGE_R(b, c, a) a r 0 while (b ) И (c ) do MERGERUN(b, c, a) r r + 1 while b do COPYRUN(b, a) r r + 1 while c do COPYRUN(c, a) r r + 1 return (r, a)

Процедура копирования серии 13 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» COPYRUN(a, b) cur first(a), a rest(a) if a then next first(a) else next cur – 1 while a И next cur do b b & cur cur next a rest(a) if a then next first(a) b b & cur return cur DISTRIB _R(a, n, k) b, c while a do COPYRUN(a, b) if a then COPYRUN(a, c) return (b, c)

Процедура слияния двух серий 14 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» MERGERUN(b 1, b 2, a) for i = 1 to 2 do if b i then f i true, cur i first(b i ), b i rest(b i ), while f 1 И f 2 do i argmin(cur i ; i 1.. 2) a a & cur i if (b i ) И (cur i < first(b i )) then cur i first(b i ), b i rest(b i ) else f i false j (i mod 2) + 1 COPYRUN(a, b j )

Анализ алгоритма естественной сортировки слиянием 15 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество R пересылок данных на одном этапе: этап состоит из двух фаз, в рамках каждой из которых выполняется перемещение всех элементов исходной последовательности a; Количество M пересылок на одном этапе: R = 2n ввод n, a do (b, c) DISTRIB_R(a, n) (a, r) MERGE_R(b, c, a) while ( r > 1 ) b c

16 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество i этапов: зависит от количества серий в исходной последоватльности; в худшем случае (массив отсортирован в обратном порядке) количество этапов будет совпадать с числом этапов алгоритмов простой сортировки слиянием: i = [log 2 n] I II III ввод n, a do (b, c) DISTRIB_R(a, n) (a, r) MERGE_R(b, c, a) while ( r > 1 ) Анализ алгоритма естественной сортировки слиянием

17 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество M пересылок: M = i R = 2n[log 2 n] = O(nlog 2 n) Число C сравнений по ключу: сопоставимо с M; время сравнения значительно ниже времени пересылки. Алгоритм требует n = O(n) дополнительной памяти ввод n, a do (b, c) DISTRIB_R(a, n) (a, r) MERGE_R(b, c, a) while ( r > 1 ) Анализ алгоритма естественной сортировки слиянием

Эксперименты (характеристики вычислительного средства) 18 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ХарактеристикаЗначение Процессор ПроизводительIntel(R) МодельCore(TM) i Частота3.40GHz Оперативная память Объем8GB Скорость доступа95 ГБ/с Жесткий диск Объем1,2 ТB Скорость чтения Скорость записи

Кеширование дискового ввода-вывода 19 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Программа GLIBC User-space cache fwrite(buf) Kernel-space cache Ядро ОС

20 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Экспериментальные данные Natural Merge (Ось у – линейная шкала)

Экспериментальные данные Natural Merge (Ось у – логарифмич. шкала) 21 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Intel(R) Core(TM) i5-3570, 8 GB RAM x = log 2 n = (log 10 n)/log 10 2 = C log 10 n

22 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Intel(R) Core(TM) i5-3570, 8 GB RAM Экспериментальные данные Quick Sort (Ось у – линейная шкала)

Экспериментальные данные Natural Merge (Ось у – логарифмич. шкала) 23 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Intel(R) Core(TM) i5-3570, 8 GB RAM x = log 2 n = (log 10 n)/log 10 2 = C log 10 n

Экспериментальные данные 24 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество элементов Время, с Quick SortNatural Merge , , ,010, ,051, ,524, , – 10 –76 012

Время чтения и записи 25 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a b1b1 b2b2 V ф = 40 ГБ. V общ : х20 = 80 ГБ t = 16m = 960 c v = 80000/960 = 83 Мб/с a V ф = 20 ГБ. V общ : 2х = 80 ГБ t = 23m 28 = 1408 с v = 80000/1408 = 57 Мб/с Характеристики входной последовательности Длина серии: max = 12, min = 1, avg = 2, runcount=

Анализ времени выполнения сортировки методом естественных слияний 26 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача Выполнить сортировку элементов. Решение s e = sizeof(int) = 4 байта, V ф = ГБ Один проход Распределение: = 80 ГБ Слияние: ГБ = 80 ГБ Количество проходов С макс = log = log / log = 10/0,3 +1 = 34 C факт = 33 Оценка времени решения Распределение: 2640ГБ/84МБ/с = /84 с = 8,7 часа Слияние: 2640 ГБ/57Мб/с = /57 = 12,9 часа Общее время работы: 21,7 часа. Фактическое: /3600 = 21,11 часа

27 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Размер последовательности: n элементов Оперативная память способна хранить k элементов Применение внутренней сортировки позволит сформировать серии размером не менее k элементов. Количество серий после внутренней сортировки: n/k Количество проходов: log 2 (n/k) Число проходов сокращается в log 2 n/log 2 (n/k)=log (n/k) n раз. Недостатки алгоритма естественной сортировки слиянием (2)

Литература 28 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 1.Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона / Пер. с англ. Ткачев Ф.В. – М.: ДМК Пресс, 2012 г. – 272 с., 2.Кнут, Д.Э. Искусство программирования: в 3 т. Т. 3. Сортировка и поиск [Текст] : [учеб. пособие]; пер. с англ. / под общ. ред. Ю.В. Казаченко. - 3-е изд. – М.: Издат.дом "Вильямс", – 822с. 3.Седжвик Р. Алгоритмы на C++ (Algorithms in C++): Пер. с англ. – М.: Издательский дом "Вильямс", 2011 г. – 1056 c. – ISBN , ;