Алгоритмы внешней сортировки (часть IV, масштабирование аппаратурных средств) Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра. - презентация

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

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

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

4 Недостатки алгоритма естественной сортировки слиянием 4 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a b1b1 + Сортируемая последовательность Вспомогательные последовательности b2b2 b3b3 b N-1 bNbN... ? ? Увеличение числа вспомогательных аппаратурных элементов не позволяет ускорить сортировку!

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

6 Natural Merge (оценка времени чтения и записи) 6 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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=

7 Natural Merge (анализ времени выполнения сортировки) 7 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача Выполнить сортировку элементов. Решение 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 часа

8 Чтение данных с диска (влияние количества потоков) 8 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

9 Запись данных на диск (1 поток, влияние кеширования) 9 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

10 Время записи с кешированием (для 1, 2, 5 и 10 потоков) 10 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

11 Время записи с ожиданием завершения (для 1, 2, 5 и 10 потоков) 11 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

12 Natural Merge, 3 HDD (оценка времени чтения и записи) 12 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a b1b1 b2b2 V ф = 40 ГБ. V общ : х20 = 80 ГБ v =100 Мб/с a V ф = 20 ГБ. V общ : 2х = 80 ГБ v = 100 Мб/с Характеристики входной последовательности Длина серии: max = 12, min = 1, avg = 2, runcount=

13 Natural Merge, 3 HDD (анализ времени выполнения сортировки) 13 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача Выполнить сортировку элементов. Решение s e = sizeof(int) = 4 байта, V ф = ГБ Один проход Распределение: = 80 ГБ Слияние: ГБ = 80 ГБ Количество проходов С макс = log = log / log = 34 C факт = 33 Оценка времени решения Распределение: 2640ГБ/100МБ/с = 7,3 ч. (было 8,7 ч.) Слияние: 2640 ГБ/100Мб/с = 7,3 ч. (было12,9 ч.) Общее время работы: 14,6 ч. (было 21,7 ч.). Ускорение ~ 33%

14 Запись последовательности, состоящей из N серий 14 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Для более простого описания примеров для алгоритмов, которые будут рассматриваться далее, будем представлять последовательность в виде набора серий, а не элементов. При этом количество элементов серий и их содержимое будем опускать, приводя лишь порядковый номер серии. Например: 56 Для изображения последовательности, состоящей из N серий, использовать следующую запись: N-1N Обозначение результата слияния серий i, j, k: i, j, k

15 СБАЛАНСИРОВАННОЕ МНОГОПУТЕВОЕ СЛИЯНИЕ (BALANCED MULTIWAY MERGING) 15 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

16 Сбалансированное многопутевое слияние (balanced multiway merging) 16 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a d1d1 d2d2 d3d3 d4d4 d5d5 d6d6 1, 4, 7, … 2, 5, 8, … 3, 6, 9, …

17 Сбалансированное многопутевое слияние (balanced multiway merging) 17 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» I , 2, 3 4, 5, 6 7, 8, 9 10, 11, 12 13, 14, 15 II III , 2, 3, 4, 5, 6, 7, 8, 9 10, 11, 12, 13, 14,15 IV 1 – 15

18 Сбалансированное многопутевое слияние (balanced multiway merging) 18 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Если для сортировки используется 2N вспомогательных файлов, то говорят о N-путевом слиянии. Сравним работу алгоритма естественного и четырехпутевого слияния при сортировке 64 серий. Естественное слияние (2 вспомогательных файла) I.64/2 = 32 серий II.32/2 = 16 серий III.16/2 = 8 серий IV.8/2 = 4 серии V.4/2 = 2 серии VI.2/2 = 1 серия 4-хпутевое слияние (8 вспомогательных файлов) I.64/4 = 16 серий II.16/4 = 4 серии III.4/4 = 1 серия

19 Multiway Merge, 6 HDD (оценка времени чтения и записи) 19 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» V ф = 40 ГБ. V общ : х20 = 80 ГБ v = 300 Мб/с Характеристики входной последовательности Длина серии: max = 12, min = 1, avg = 2, runcount= a d1d1 d2d2 d3d3 d4d4 d5d5 d6d6 Распределение + слияние V ф = 40 ГБ, v' = 100 МБ/с Начальное распределение

20 Natural Merge, 6 HDD (анализ времени выполнения сортировки) 20 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача Выполнить сортировку элементов. Решение s e = sizeof(int) = 4 байта, V ф = ГБ Начальное распределение Распределение: 40 = 40 ГБ Один проход Распределение + слияние: = 80 ГБ Количество проходов С макс = log = log / log = 21 C макс – 1 = 20 Оценка времени решения Распределение: 40ГБ / 100МБ/с = 0,11 ч. Распределение + слияние: 1520ГБ/300МБ/с = 1,5 ч. (было 21,7 ч.) Ускорение ~ 92 %

21 Natural Merge, 6 HDD + предсортировка (анализ времени выполнения сортировки) 21 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Задача Выполнить сортировку элементов. Решение s e = sizeof(int) = 4 байта, V ф = ГБ Размер ОП: 500 МБ Количество серий: 40 ГБ/100МБ = 400 Начальное распределение Распределение: 40 = 40 ГБ Один проход Распределение + слияние: = 80 ГБ Количество проходов С = [log 3 400] + 1 = [log / log 10 3 ] + 1 = 6 Оценка времени решения Распределение: 40ГБ / 100МБ/с = 0,11 ч. Распределение + слияние: 480ГБ/300МБ/с = 0,44 ч. (было 21,7 ч.) Ускорение ~ 97 %

22 Алгоритм N–путевого слияния 22 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ввод N, a k 1 (r, b 1, …, b N ) DISTRIB_RN(a, N) while r > 1 do (r, b N+1, …, b 2N ) MERGE_RN(b 1, …, b N ) (b 1, …, b N ) (b N+1, …, b 2N ) done (r, a, , …, ) MERGE_RN(b 1, …, b N )

23 Распределение серий по N последовательностям 23 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» DISTRIB _RN(a, N) for i = 1 to N do d i i 1 while a do COPYRUN(a, d i ) i (i mod N) + 1 return (d 1, …, d N ) i(i mod N) +1 1(1 mod 5) + 1 = 2 2(2 mod 5) + 1 = 3 3(3 mod 5) + 1 = 4 4(4 mod 5) + 1 = 5 5(5 mod 5) + 1 = 1 6(6 mod 5) + 1 = 2 7(7 mod 5) + 1 = 3 8(8 mod 5) + 1 = 4 9(9 mod 5) + 1 = 5 10(10 mod 5) + 1 = 1 N = 5

24 Процедура слияния двух серий 24 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» MERGE_RN(N, s 1, …, s N ) for i = 1 to N do d i r 1, f true, i 1 while (f = true) do (f, d i ) MERGERUN_N(d i, N, s 1, …, s N ) i (i mod N) + 1 if f = true then r r + 1 return (r, d 1, …, d N )

25 Процедура многопутевого слияния серий 25 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» MERGERUN_N(d, N, s 1, …, s N ) k 0 for i = 1 to N do if s i then c i first(s i ), k k + 1, m k i k' (k > 0) while k > 0 do i' m 1, c' c i' for j = 2 to k do i m j if c i < c' then i' m j, c' c i' d d & c', s i' rest(s i' ) if s i' = ИЛИ c i' first(s i' ) then m k m i', k k – 1 else c i' first(s i' ) return (k', d) m – карта непустых серий m 1 – первая непустая серия m k – последняя непустая серия m – карта непустых серий m 1 – первая непустая серия m k – последняя непустая серия для удаления последовательности с пустой серией достаточно поменять ее местами с последней непустой серией и уменьшить количество k непустых серий для удаления последовательности с пустой серией достаточно поменять ее местами с последней непустой серией и уменьшить количество k непустых серий

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

27 27 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Количество i этапов: в худшем случае, если максимальная длина серии = 1 (массив отсортирован в обратном порядке) на каждом этапе количество серий будет уменьшаться в r раз. Таким образом количество проходов: i = [log N n] ввод n, N, a k 1 (r, b 1, …, b N ) DISTRIB_RN(a, n, N) while r > 1 do (r, b N+1, …, b 2N ) MERGE_RN(b 1, …, b N ) (b 1, …, b N ) (b N+1, …, b 2N ) done (r, a,, …, ) MERGE_RN(b 1, …, b N ) Анализ алгоритма сбалансированного многопутевого слияния

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

29 Недостатки сбалансированного многопутевого слияния 29 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Основным недостатком данного метода является то, что лишь половина вспомогательных последова- тельностей принимает актив- ное участие при выполнении слияний. b1b1 b2b2 b3b3 b1b1 b2b2 b3b3

30 МНОГОФАЗНАЯ СОРТИРОВКА СЛИЯНИЕМ (POLYPHASE MERGING) 30 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

31 Многофазная сортировка слиянием (polyphase merging) 31 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Многофазная сортировка позволяет преодолеть указанный недостаток многопутевого слияния. Данный метод имеет следующие отличительные особенности: допускает использование произвольного числа N вспомогательных последовательностей; при слиянии используется (N – 1) вспомогательная последовательность, при этом результат записывается в свободную (N-ю) последовательность; слияние производится до тех пор пока все последовательности не пусты (стратегия сливать до опустошения – merge-until-empty); требует неравномерного распределения серий по вспомогательным последовательностям.

32 Пример многофазной сортировки (3 вспомогательные последовательности) 32 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» * Указывается только количество серий в последовательности a1a1 a2a2 a3a3 100 t

33 Пример многофазной сортировки (6 вспомогательных последовательностей) 33 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a a2a a3a a4a a5a a6a6 * Указывается только количество серий в последовательности t

34 Многофазная сортировка при сбалансированном распределении 34 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Сбалансированное распределение серий! a1a1 a2a2 a3a3 t

35 Идеальное количество серий при трех вспомогательных последовательностях 35 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» La1(L)a1(L)a2(L)a2(L)Sum a1a1 a2a2 a3a3 Одна последовательность всегда пуста, поэтому количество рабочих последовательностей – 2. t

36 Идеальное количество серий при трех вспомогательных последовательностях 36 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» La1(L)a1(L)a2(L)a2(L)Sum a1a1 a2a2 a3a3 Одна последовательность всегда пуста, поэтому количество рабочих последовательностей – 2.

37 Идеальное количество серий при шести вспомогательных последовательностях 37 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» La1(L)a1(L)a2(L)a2(L)a3(L)a3(L)a4(L)a4(L)a5(L)a5(L)Sum

38 Идеальное количество серий при шести вспомогательных последовательностях 38 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» La1(L)a1(L)a2(L)a2(L)a3(L)a3(L)a4(L)a4(L)a5(L)a5(L)Sum

39 Идеальное распределение серий и числа Фибоначчи 39 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» La1(L)a1(L)a2(L)a2(L)Sum При использовании трех вспомогательных последователь- ностей идеальное количество исходных серий представляет собой числа Фибоначчи. F i = F i – 1 + F i – 2 F 0 = 0, F 1 = 1, F 2 = 1, F 3 = 2, F 4 = 3, F 5 = 5, F 6 = 8, F 7 = 13, F 8 = 21, F 9 = 34, F 10 = 55, ….

40 Идеальное распределение серий и обобщенные числа Фибоначчи 40 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Для произвольного числа N вспомогательных последовательностей количество серий в k-й последовательности на уровне L определяется соотношением: Количество серий в исходной последовательности: Обобщенные числа Фибоначчи порядка p определяются следующими правилами:

41 Идеальное распределение серий N = 6 41 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Запишем последовательность чисел порядка (N – 1): 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31

42 Идеальное распределение серий N = 6 42 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Запишем последовательность чисел порядка (N – 1): 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31

43 Идеальное распределение серий N = 6 43 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» La1(L)a1(L)a2(L)a2(L)a3(L)a3(L)a4(L)a4(L)a5(L)a5(L)Sum

44 Фактическое и идеальное распределение серий 44 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Реальное количество серий в сортируемой последовательности может отличаться от идеального. Если данный факт будет проигнорирован в алгоритме сортировки, основанном на стратегии "сливать до опустошения" (merge- until-empty), то его эффективность будет существенно ниже идеальной. Для решения данной проблемы используется введение фиктивных (пустых) серий. На их слияние не затрачивается времени. Цель фиктивных серий – обеспечить нужное количество слияний на каждом проходе. LSum

45 Применение многофазной сортировки без учета идеального распределения. 45 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ?

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

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

48 48 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3*, 103*, ? Применение многофазной сортировки с фиктивными сериями. 138

49 Применение многофазной сортировки без учета идеального распределения. 49 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 136*,

50 Применение многофазной сортировки с фиктивными сериями. 50 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6*,

51 Алгоритм "горизонтального" распределения 51 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Алгоритм обеспечивает распределение входных серии по вспомогательным последовательностям. Распределение начинается с первого уровня (L = 1). Если входные серии заполнили все "слоты" текущего уровня, то создается новый уровень. При переходе на новый уровень для него выполняется расчет точного (идеального) распределения серий. Результат записывается в массив A[1… N]. LA[1]A[2]A[3]A[4]A[5]A[6]*Sum * – элемент A[N] всегда нулевой

52 Алгоритм "горизонтального" распределения 52 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Алгоритм обеспечивает распределение входных серии по вспомогательным последовательностям. Распределение начинается с первого уровня (L = 1). Если входные серии заполнили все "слоты" текущего уровня, то создается новый уровень. При переходе на новый уровень для него выполняется расчет точного (идеального) распределения серий. Результат записывается в массив A[1… N]. Целью алгоритма является равномерное распределение серий по вспомогательным последовательностям. Это позволяет быстро избавиться от фиктивных серий в процессе слияний. Для каждой вспомогательной последовательности поддерживается число фиктивных серий (массив F[1…N]).

53 Алгоритм "горизонтального" распределения 53 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» HORIZONT_DISTR(s, N) for i = 1 to N – 1 do A[i] F[i] 1, d[i] A[N] F[N] 0, d[N], l j 1 while a do COPYRUN(a, d[j]), F[j] F[j] – 1 if F[j] < F[j + 1] then j j + 1 else if F[j] 0 then j 1 else l l + 1, x A[1] for i = 1 to N – 1 do F[i] x + A[i + 1] – A[i] A[i] x + A[i + 1] j 1 return (l, F, d)

54 Алгоритм "горизонтального" распределения (переход на новый уровень, N = 6) 54 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» l l + 1, x A[1] for i = 1 to N – 1 do F[i] x + A[i + 1] – A[i] A[i] x + A[i + 1] LA1LA1L A2LA2L A3LA3L A4LA4L A5LA5L Sum A 3 = [4, 4, 4, 3, 2, 0] x = A 3 [1] = 4 A 4 [1] = x + A 3 [2] = 8 A 4 [2] = x + A 3 [3] = 8 A 4 [3] = x + A 3 [4] = 7 A 4 [4] = x + A 3 [5] = 6 A 4 [5] = x + A 3 [6] = 4 F 4 [1] = (x + A 3 [2]) – A 3 [1] = 4 F 4 [2] = (x + A 3 [3]) – A 3 [2] = 4 F 4 [3] = (x + A 3 [4]) – A 3 [3] = 3 F 4 [4] = (x + A 3 [5]) – A 3 [4] = 3 F 4 [5] = (x + A 3 [6]) – A 3 [5] = 2

55 Алгоритм "горизонтального" распределения (заполнение уровня, N = 6) 55 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» j 1 COPYRUN(a, d[j]), F[j] F[j] – 1 if F[j] < F[j + 1] then j j + 1 else if F[j] 0 then j j A 3 = [4, 4, 4, 3, 2, 0] A 4 = [8, 8, 7, 6, 4, 0] F 4 = [4, 4, 3, 3, 2, 0] F 4 = A 4 – A A3A3 F4F

56 Алгоритм "горизонтального" распределения (заполнение уровня, N = 6) 56 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» j 1 while a do COPYRUN(a, d[j]), F[j] F[j] – 1 if F[j] < F[j + 1] then j j + 1 else if F[j] 0 then j j A3A3 F4F A3A3 F4F A3A3 F4F A3A3 F4F4 5.

57 Алгоритм "горизонтального" распределения (заполнение уровня, N = 6) 57 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» j 1 while a do COPYRUN(a, d[j]), F[j] F[j] – 1 if F[j] < F[j + 1] then j j + 1 else if F[j] 0 then j j Закончить самостоятельно!... Закончить самостоятельно!

58 Распределение номеров серий по вспомогательным последовательностям 58 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» L d1d1 d2d2 d3d3 серийA L-1 FLFL серийA L-1 FLFL серийA L-1 FLFL , 4112, , 4, 6, 7222, 5, 8213, , 4, 6, 7, 10, 12, , 5, 8, 11, 13, ,9, 14, , 4, 6, 7, 10,12,15, 18,19,21, 23, 26, , 5, 8, 11, 13, 16, 20,22,24, 27, , 9,14,17, 25, 28, 3143

59 Распределение номеров серий по вспомогательным последовательностям 59 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Конечное распределение номеров серий по вспомогательным последовательностям для L= 5: d 1 : 1,|4,| 6, 7,|10,|12,|15,|18, 19,|21,|23,|26,|29 d 2 : 2,|5,| 8,|11,|13,|16,|20,|22,|24,|27,|30 d 3 : 3,|9,|14,|17,|25,|28,|31 Пусть дана входная последовательность: 0, 5, 10,|1, 6, 11,|3, 12, 18,|15, 20,|16, 21, 26, |25, 30,|1, 40,|27, 28, 29,|20, 21, 22,... Тогда распределение данных по вспомогательным последовательностям имеет вид: d 1 : 0, 5, 10,|15, 20,|25, 30,| 1, 40 d 2 : 1, 6, 11,|16, 21, 26,|27, 28, 29 d 3 : 3, 12, 18,|20, 21, 22

60 Алгоритм "горизонтального" распределения 60 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» HORIZONT_DISTR_M(s, N) for i = 1 to N – 1 do A[i] F[i] 1, d[i] A[N] F[N] 1, d[N], l j 1 while a do last[j] COPYRUN(a, d[j]), F[j] F[j] – 1 if F[j] < F[j + 1] then j j + 1 else if F[j] 0 then j 1 else l l + 1, x A[1] for i = 1 to N – 1 do F[i] x + A[i + 1] – A[i] A[i] x + A[i + 1] j 1 CHECKMERGE(a, d[j], last[j]) return (l, F, d)

61 Процедура копирования серии 61 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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 CHECKMERGE(a, d, last) if a then if first(a) > last then COPYRUN(a, d)

62 Алгоритм многофазной сортировки 62 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» POLYPHASE_STEP(s, N) (l, F, d) HORIZONT_DISTR_M(s, N) while l > 0 do while d[N – 1] И F[N – 1] 0 do k 1 k 2 0 for i 1 to N – 1 do if F[i] > 0 then k 1 k 1 + 1, m 1 [k 1 ] i else k 2 k 2 + 1, m 2 [k 2 ] i if k 1 = N – 1 then F[N] F[N] + 1 else MERGERUN_N(d[N], k 2, d[m 2 [1]], …, d[m 2 [k 2 ]]) for k 1 to k 1 do F[m 1 [k]] F[m 1 [k]] – 1 l l – 1 (d[1], d[2], d[3],…, d[N]) (d[N], d[1], d[2], …, d[N – 1]) return d[1]

63 КАСКАДНАЯ СОРТИРОВКА (CASCADE MERGE) 63 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

64 Каскадная сортировка (cascade merge) 64 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a a2a a3a a4a a5a a6a6 * Указывается только количество серий в последовательности

65 Каскадная сортировка (2) 65 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a a2a a3a a4a a5a a6a6 * Указывается только количество серий в последовательности

66 Каскадная сортировка (3) 66 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a a2a a3a a4a a5a a6a6 * Указывается только количество серий в последовательности

67 Каскадная сортировка (4) 67 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a a2a a3a a4a a5a a6a6 * Указывается только количество серий в последовательности

68 Каскадная сортировка (5) 68 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a1 a2a2 a3a3 a4a4 a5a5 a6a6 * Указывается только количество серий в последовательности

69 Идеальное количество серий при шести вспомогательных последовательностях 69 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a1 0 b1b1 0 c1c1 0 d1d1 0 e1e a 1 = 1 b 1 = 1 c 1 = 1 d 1 = 1 e 1 = 1

70 Идеальное количество серий при шести вспомогательных последовательностях 70 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a2a2 b2b2 e 1 = 1 c2c2 d 1 = 1 d2d2 c 1 = 1 e2e2 b 1 = 1 0 a 1 = 1 e 2 = a 1 d 2 = a 1 + b 1 = e 2 + b 1 = 2 c 2 = a 1 + b 1 + c 1 = d 2 + c 1 = 3 b 2 = a 1 + b 1 + c 1 + d 1 = c 2 + d 1 = 4 a 2 = a 1 + b 1 + c 1 + d 1 + e 1 = b 2 + e 1 = 5

71 Идеальное количество серий при шести вспомогательных последовательностях 71 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a3a3 b3b3 e 2 = 1 c3c3 d 2 = 2 d3d3 c 2 = 3 e3e3 b 2 = 4 0 a 2 = 5 e 3 = a 2 = 5 d 3 = a 2 + b 2 = e 3 + b 2 = 9 c 3 = a 2 + b 2 + c 2 = d 3 + c 2 = 12 b 3 = a 2 + b 2 + c 2 + d 2 = c 3 + d 2 = 14 a 3 = a 2 + b 2 + c 2 + d 2 + e 2 = b 3 + e 2 = 15

72 Идеальное количество серий во входной последовательности 72 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Ld1d1 d2d2 d3d3 d4d4 d5d5 Сумма nanan bnbn cncn dndn enen – e n+1 = a n, d n+1 = a n + b n = e n+1 + b n, c n+1 = a n + b n + c n = d n+1 + c n, b n+1 = a n + b n + c n + d n = c n+1 + d n, a n+1 = a n + b n + c n + d n + e n = b n+1 + e n

73 Начальное распределение серий (N = 6) (алгоритм Дэвида Э. Фергюсона) 73 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Пусть в последовательностях d 1 – d 5 сформировано точное распределение (a, b, c, d, e) уровня L. Изменяя логические номера последовательностей, получим реальное распределение (e, d, c, b, a): (d 1, d 2, d 3, d 4, d 5 ) (d 5, d 4, d 3, d 2, d 1 ) Следующее точное распределение: (a+b+c+d+e, a+b+c+d, a+b+c, a+b, a) Если входные серии заканчиваются до достижения следующего уровня, то на распределение фиктивных серий по выходным лентам должно быть организовано следующим образом: F 1 a+b+c+d, F 2 a+b+c, F 3 a+b, F 4 a, F 5 = 0

74 Начальное распределение серий (N = 6) (алгоритм Дэвида Э. Фергюсона) 74 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шаг+ d 1 + d 2 + d 3 + d 4 + d 5 (1,1)90000 (2,2) (2,1)90000 (3,3) (3,2) (3,1)90000 (4,4) (4,3) (4,2) (4,1)90000

75 Начальное распределение серий (N = 6) (алгоритм Дэвида Э. Фергюсона) 75 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шаг+ d 1 + d 2 + d 3 + d 4 + d 5 (1,1)90000 (2,2) (2,1)90000 Шаг d 1 (реальн./фиктивн.) d 2 (реальн./фикт.) d 3 (реал./фикт.) d 4 (р./фикт.) исх.5 / / / / 15 (1,1)5+9 / (2,2)5+12 / / (2,1) / 14+15

76 Начальное распределение серий (N = 6) (алгоритм Дэвида Э. Фергюсона) 76 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шаг d 1 (реальн./фиктивн.) d 2 (реальн./фикт.) d 3 (реал./фикт.) d 4 (р./фикт.) (2,1) / / / / 15 (3,3) / / / 15 (3,2) / / 15 (3,1) / 15 Шаг+ d 1 + d 2 + d 3 + d 4 + d 5 (3,3) (3,2) (3,1)90000

77 Начальное распределение серий (N = 6) (алгоритм Дэвида Э. Фергюсона) 77 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шаг d 1 (реальн./фиктивн.) d 2 (реальн./фикт.) d 3 (реал./фикт.) d 4 (р./фикт.) (3,1) / / / 1514 / 15 (4,4) / / / (4,3) / / (4,2) / (4,1) Шаг+ d 1 + d 2 + d 3 + d 4 + d 5 (4,4) (4,3) (4,2) (4,1)90000

78 Начальное распределение серий (N = 6) (алгоритм Дэвида Э. Фергюсона) 78 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шагd 1 (р./фикт.)d 2 (р./фикт.)d 3 (р./фикт.)d 4 (р./фикт.) исх.5 / / / / 15 (1,1)5+9 / / / / 15 (2,2)5+12 / / / / 15 (2,1) / / / / 15 (3,3) / / / 1514 / 15 (3,2) / / / 1514 / 15 (3,1) / / / 1514 / 15 (4,4) / / / (4,3) / / (4,2) / (4,1)

79 Процедура первого прохода (обеспечивает удаление всех фиктивных серий) 79 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 1.Пусть количество вспомогательных лент – N, тогда данных находятся на (N – 1) последовательности, N-я последовательность пуста. A n [1,…,(N–1)] – текущее идеальное распределение, а F[1,…, (N–1)] – количество фиктивных серий. 2.На i-м шаге алгоритма осуществляется слияние из (1,2,…,N–i) в (N+1–i)-ю последовательность. Если F[N–(i+1)] = A n [N–i] (достаточно фиктивных серий), тогда F[k] F[k] – A n [N–i] (изменяется число фиктивных серий). Если F[N–(i+1)] < A n [N–i], то слияние осуществляется с минимально возможным числом фиктивных серий так, чтобы: 55 d1d1 50 d2d2 41 d3d3 29 d4d4 15 d5d5 0 d6d6

80 Первый проход каскадного слияния 80 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Ld1d1 d2d2 d3d3 d4d4 d5d5 Сумма … … Если, при достижении идеального распределения, входные данные не исчерпаны, то инициируется заполнение следующего уровня. Для этого вспомогательные последовательности размещают в обратном порядке так, чтобы количество серий в последней последовательности (d 5 ) удовлетворяло условиям идеального распределения.

81 Первый проход каскадного слияния 81 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Ld1d1 d2d2 d3d3 d4d4 d5d5 Сумма … …

82 Первый проход каскадного слияния 82 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Ld1d1 d2d2 d3d3 d4d4 d5d5 Сумма … … : 5 2: 9 3: 8 4: 3 5: 15 4: 14 3: 12 2: 9 1: 5

83 Первый проход каскадного слияния (пример I) 83 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шагd 1 (р./фикт.)d 2 (р./фикт.)d 3 (р./фикт.)d 4 (р./фикт.) исх.5 / / / / 15 (1,1)5+9 / / / / 15 (2,2)5+12 / / / / 15 (2,1) / / / / 15 (3,3) / / / 1514 / 15 (3,2) / / / 1514 / 15 *(3,1) / / / 1514 / 15 Входные данные иссякли после завершения шага (3,1).

84 Первый проход каскадного слияния (пример I) 84 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шагd 1 (р./фикт.)d 2 (р./фикт.)d 3 (р./фикт.)d 4 (р./фикт.) *(3,1) / / / 1514 / /15 d1d /15 d2d /15 d3d3 14/15 d4d4 15 d5d5 0 d6d

85 Первый проход каскадного слияния (пример II) 85 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шагd 1 (р./фикт.)d 2 (р./фикт.)d 3 (р./фикт.)d 4 (р./фикт.) исх.5 / / / / 15 (1,1)5+9 / / / / 15 (2,2)5+12 / / / / 15 (2,1) / / / / 15 (3,3) / / / 1514 / 15 Входные данные иссякли на шаге (3,3). Их хватило только на d 3 и d 2

86 Первый проход каскадного слияния (пример II) 86 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» /14+15 d1d1 9+14/12+15 d2d /15 d3d3 14/15 d4d4 15 d5d5 0 d6d /149+14/ /12+29/ / Шагd 1 (р./фикт.)d 2 (р./фикт.)d 3 (р./фикт.)d 4 (р./фикт.) (3,3) / / / 1514 / 15

87 Первый проход каскадного слияния (пример III) 87 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шагd 1 (р./фикт.)d 2 (р./фикт.)d 3 (р./фикт.)d 4 (р./фикт.) исх.5 / / / / 15 (1,1)5+9 / / / / 15 (2,2)5+12 / / / / 15 (2,1) / / / / 15 (3,3) / / / / 15 Входные данные иссякли на шаге (3,3). вместо требуемых 18 было получено только 5 элементов

88 Первый проход каскадного слияния (пример III) 88 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» /14+15 d1d1 9+12/14+15 d2d2 12+5/9+15 d3d3 14/15 d4d4 15 d5d5 0 d6d6 Шагd 1 (р./фикт.)d 2 (р./фикт.)d 3 (р./фикт.)d 4 (р./фикт.) (3,3) / / / / /149+12/ / /12+29/ /

89 Первый проход каскадного слияния (самостоятельно) 89 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Шагd 1 (р./ф.)d 2 (р./ф.)d 3 (р./ф.)d 4 (р./ф.) исх.5 / / / / 15 (1,1)5+9 / / / / 15 (2,2)5+12 / / / / 15 (2,1) / / / / 15 (3,3) / / / 1514 / 15 (3,2) / / / 1514 / 15 (3,1) / / / 1514 / 15 (4,4) / / / (4,3) / / (4,2) / (4,1)

90 Начальное распределение серий (алгоритм Дэвида Э. Фергюсона) 90 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» FERGUSON_DISTR(a, N) FERGUSON_INIT(A c, A n, I, F) while a do NEXT_LEVEL(N, A c, A n, F), l l + 1, i 1 (d[1], d[2], …, d[N-1], d[N]) (d[N–1], …, d[2], d[1], d[N]) while i (N – 1) И a do j i while (j > 0) И (a ) do k j, m A c [N – j – 1] while m > 0 И a do d[k] d[k] & first(a), a rest(a) F[k – 1] F[k – 1] – 1, m m – 1 if m = 0 then k k – 1 if k = 0 then m A c [N – j – 1] – A c [N – j]; return (d[1,…, N], l, F, A n )

91 Инициализация данных (алгоритм Дэвида Э. Фергюсона) 91 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» N – количество вспомогательных последовательностей a – входная последовательность d– первая вспомогательная последовательность A с – текущее идеальное распределение серий A n – следующее идеальное распределение F : F[i] – количество фиктивных серий на i-й вспомогательной последовательности FERGUSON_INIT(a, d, A c, A n, I, F) for i 0 to N + 1 do A c [i] A n [i] F[i] 0 A n [1] = F[1] = 1; d[1] d[1] & first(a) a rest(a)

92 Переход на следующий уровень (алгоритм Дэвида Э. Фергюсона) 92 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» N – количество вспомогательных последовательностей A с – текущее идеальное распределение серий A n – следующее идеальное распределение F : F[i] – количество фиктивных серий на i-й вспомогательной последовательности NEXT_LEVEL(N, A c, A n, F) for i 0 to N do A c [i] A n [i] for i 0 to (N – 1) do A n [N – i] A n [N – i + 1] + A c [i] for i 0 to N do F[i] A n [i + 1]

93 Алгоритм сортировки каскадным слиянием 93 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» CASCADE_SORT(a, N) (d[1,…, N], l, F, A n ) FERGUSON_DISTR(a, N) for k 1 to N – 1 do M[k] A n [k+1] FIRST true while l > 0 do for i (N – 1) downto 2 do if FIRST И F[i – 1] = M[i – 1] then d[i+1] d[i] for j 1 to i do F[j] F[j]–M[i – 1], M[j] M[j] – M[i – 1] else for j 1 to i do M[j] M[j] – M[i – 1] while d[i] do MERGERUN_NF(i, d[1,…,i+1], F, M) d[1] d[2] (d[1], d[2], …, d[N – 1], d[N]) (d[N], d[N – 1], …, d[N]) l l – 1, FIRST false

94 Процедура первого прохода 94 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» MERGERUN_NF(i, d[1, …, i+1], F, M) k 0 for j 1 to i do if F[j] M[j] then k k + 1 s[k] j else F[j] F[j] – 1 MERGERUN_N(d[i+1], k, d[s[1]], …, d[s[k]]) источники слияния

95 Заключение 95 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» В рамках данной лекции были рассмотрены вопросы сортировки больших объемов данных. Были рассмотрены следующие алгоритмы сортировки: 1. Простая сортировка методом слияния (straight merge). 2. Метод сбалансированных слияний (balanced merge). 3. Естественная сортировка слиянием (natural merge). 4. Сбалансированное многопутевое слияние (balanced multiway merging). 5. Многофазная сортировка слиянием (polyphase merging). 6. Каскадная сортировка (cascade merge). Также были рассмотрены алгоритмы подготовки начальных серий максимально возможной длины: 1. Применение внутренних алгоритмов сортировки. 2. Выбор с замещением (replacement selection).

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