ПРОГРАММИРОВАНИЕ/ ЯЗЫКИ ПРОГРАММИРОВАНИЯ Лекция 7 Алгоритмы внешней сортировки (весенний семестр 2012 г.) Доцент Кафедры вычислительных систем, к.т.н. - презентация

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

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

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

4 Алгоритмы внутренней сортировки 4 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Алгоритмы внутренней сортировки (сортировки массивов) предназначены для работы с данными, которые полностью помещаются в оперативную память вычислительной машины, выполняющей данную операцию. Оперативная память характеризуется быстрым произвольным доступом к ее элементам. К алгоритмам внутренней сортировки предъявляются требования экономичности по памяти.

5 Алгоритмы внешней сортировки 5 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Алгоритмы внешней сортировки (сортировки файлов) предназначены для работы с данными, объем которых не позволяет полностью разместить их в оперативную память вычислительной машины, выполняющей данную операцию. Такие данные располагаются на внешних запоминающих устройствах, таких как диски и магнитные ленты. Внешняя память характеризуется последовательным доступом к ее элементам. В каждый момент времени имеется непосредственный доступ только к одному элементу. Основной метод сортировки – слияние.

6 Оценка алгоритмов сортировки 6 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» При оценке эффективности внутреннего алгоритма учитывается: С – количество операций сравнения М – количество операций пересылки данных.

7 Внешние запоминающие устройства (накопители) 7 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Энергонезависимая память, обладающая более низкой (по сравнению с оперативной) пропускной способностью. Виды накопителей: Накопители на магнитных лентах (НМЛ, Tape) Накопители на жестких магнитных дисках (НЖМД, HDD) Накопители на гибких магнитных дисках (НГМД) Накопители на оптических дисках (НОД, CD-ROM) Флеш-память (Flash) Твердотельные накопители (SSD)

8 Накопители на жестких магнитных дисках 8 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

9 Терминология 9 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Фаза – операция однократной обработки всего набора данных Проход (этап) – наименьший процесс, повторение которого образует процесс сортировки.

10 Двухфазный алгоритм сортировки простым слиянием 10 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть выполняется сортировка последователь-ности a, состоящей из n элементов. 1.Параметр k устанавливается в значение 1: k = 1. 2.Последовательность a разбивается на две половины: b и c. 3.Последовательности b и c сливаются обратно в a путем объединения фрагментов, состоящих из k элементов, в упорядоченные фрагменты, состоящие из 2k элементов. 4. k = k 2 5.ЕСЛИ k >= n, то алгоритм ЗАВЕРШЕН; ИНАЧЕ перейти на ШАГ 2.

11 Алгоритм сортировки простым слиянием (пример) 11 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» a = n = 8 1. k = b = , c = a = ' ' ' k = 2 2. b = ' 18 55, c = ' a = ' k = 4 2. b = , c = a = (k = 8) == n. КОНЕЦ

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

13 Оценка двухфазного алгоритма сортировки простым слиянием 13 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Количество проходов: зависит от параметра k n, который удваивается после каждого прохода; общее число проходов: log 2 n. Число M пересылок данных: проход состоит из двух фаз, на каждой из которых выполняется копирование каждого элемента из a; на одном проходе обрабатывается 2n элементов; общее число пересылок M = 2n[log 2 n]; Число C сравнений по ключу: сопоставимо с M; время сравнения значительно ниже времени пересылки.

14 Однофазный алгоритм сортировки простым слиянием 14 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть выполняется сортировка последователь- ности a, состоящей из n элементов. 1.Параметр k устанавливается в значение 1: k = 1. 2.Вторая половина a перемещается в b. 3.Фрагменты последовательностей a и b, состоящие из k элементов попарно распределяются в последовательности c и d. 4.Имена последовательностей меняются местами: c a, d b 5.ЕСЛИ k > n/2, слить a и b в а, ВЫХОД; ИНАЧЕ k = k 2, перейти на ШАГ 3.

15 Однофазный алгоритм сортировки простым слиянием (пример) 15 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» a = n = 8 1. k = a = , b = c = ' 06 12, d = ' a = ' 06 12, b = ' k = 4 3. c = ', d = ' 4. a = ', b = ' 5. k = n/2 a =

16 Анализ однофазного алгоритма сортировки простым слиянием 16 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Однофазный алгоритм простого слияния, получается из двухфазного варианта путем объединения фазы разбиения последовательности пополам и фазы слияния двух последовательностей в одну. Это достигается за счет использования четырех "магнитных лент" или файлов. Поэтому данный алгоритм называется четырехленточным.

17 Оценка однофазного алгоритма сортировки простым слиянием 17 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Количество проходов: зависит от параметра k n, который удваивается после каждого прохода; общее число проходов: log 2 n. Число M пересылок данных: проход состоит из одной фазы предусматривающей копирование каждого элемента из a; на одном проходе обрабатывается n элементов; общее число пересылок M = n[log 2 n]; Число C сравнений по ключу: сопоставимо с M; время сравнения значительно ниже времени пересылки.

18 Недостатки алгоритма простого слияния 18 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Не учитывается тот факт, что последовательность может быть частично отсортирована. На k-м проходе выполняется слияние подпоследовательностей длина которых не превышает 2 k, однако возможно существование более длинных подпоследовательностей. Возможно слияние подпоследовательностей длины 2 k m 1 n и 2 k m 2 n, что позволит уменьшить количество проходов и, следовательно, ускорить процесс сортировки.

19 Упорядоченная подпоследовательность – Серия 19 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Следуя терминологии, принятой в [1] будем называть упорядоченную подпоследовательность максимальной длины серией. Серией назовем подпоследовательность ai, ai+1, … ai+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

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

21 Свойство слияния двух последовательностей 21 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Если последовательность c образована путем слияния двух последовательностей a и b, содержащих m a и m b серий соответственно, то количество m с серий в c удовлетворяет условию: m c max(m a, m b ). Если серии распределены по последовательностям a и b равномерно (m a m b ), то после слияния количество серий уменьшается в двое. Таким образом количество пересылок данных в худшем случае будет равно n[log 2 n].

22 Алгоритм естественной сортировки слиянием 22 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть входная последовательность расположена в файле c. Проход состоит из двух фаз: 1.Распределение серий из c поровну во вспомогательные последовательности a и b. 2.Слияние серий из a и b в с.

23 Алгоритм естественной сортировки слиянием (пример) 23 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» c = 17 31' 5 59' ' ' ' ' Проход 1, фаза 1. Распределение: а = 17 31' ' ' b = 5 59' ' Проход 1, фаза 2. Слияние: c = ' ' ' Проход 2, фаза 1. Распределение: а = ' b = ' Проход 2, фаза 2. Слияние: c = '

24 Алгоритм естественной сортировки слиянием (пример) (2) 24 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» c = ' Проход 3, фаза 1. Распределение: а = b = Проход 3, фаза 2. Слияние: c = Для упорядочения последовательности требуется 3 прохода сортировки естественным слиянием. Для сортировки этой же последовательности алгоритмом простого слияния понадобиться 5 проходов.

25 Реализация алгоритма сортировки 25 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» ФайлОписание mergefile.c Основные операции с бинарным файлом последовательности mergefile.h Описание структуры file и прототипы функций из mergefile.c natsort.c Реализация алгоритма естественной сортировки слиянием randgen.c Случайная генерация последова- тельности указанной длины textgen.c Генерация бинарного файла последовательности по текстовому. checksort.c Проверка корректности результатов сортировки.

26 Реализация алгоритма сортировки (фаза распределения – natmegre.c) 26 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int distribute(struct file *in, struct file *out1, struct file *out2) { while( !fend(in) ){ copyrun(in,out1); if( !fend(in) ) copyrun(in,out2); }

27 Функция copyrun 27 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» void copyrun(struct file *in, struct file *out) { int cond = 0; loadfirst(in); while( condition(in) > 0 ){ save(in,out); load(in); }

28 Реализация алгоритма сортировки (фаза распределения – natmegre.c) 28 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» uint merge(struct file *out, struct file *in1, struct file *in2) { uint l = 0; while( !fend(in1) && !fend(in2) ){ mergerun(out,in1,in2); l++; } while( !fend(in1) ){ copyrun(in1,out); l++; } while( !fend(in2) ){ copyrun(in2,out); l++; }

29 Функция mergerun 29 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» void mergerun(struct file *out, struct file *in1, struct file *in2) { int eor = 0, cmp; loadfirst(in1); loadfirst(in2); do{ cmp = compare(in1,in2); if( cmp == 0 ){ save(in1,out); load(in1); } else if( cmp == 1 ){ save(in2,out); load(in2);} if( condition(in1)

30 Функция сортировки алгоритмом естественного слияния 30 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» void naturalmerge(char *fname) {... while( l != 1 ){ reset(&main); rewrite(&tmp1); rewrite(&tmp2); distribute(&main,&tmp1,&tmp2); reset(&tmp1); reset(&tmp2); rewrite(&main); l = merge(&main,&tmp1,&tmp2); }

31 Недостатки алгоритма естественной сортировки слиянием 31 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Затраты на последовательную сортировку пропорциональны числу проходов. На каждом проходе выполняется изменение всего множества данных во внешней памяти (например, на жестком диске). Для уменьшения числа проходов и, следовательно, временных затрат на сортировку можно использовать при распределении и слиянии более двух лент (файлов).

32 Алгоритм сбалансированного многопутевого слияния 32 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Алгоритм сбалансированного многопутевого слияния основан на алгоритме естественного слияния и имеет следующие особенности: 1.Для сортировки используется N лент (файлов), доступных для хранения промежуточных результатов. (значение N предполагается четным: N % 2 = 0). 2.Алгоритм имеет одну фазу (алгоритм естественного слияния – 2). 3.Серии распределяются по первым N/2 файлам, далее производится их слияние на вторые N/2 файлов.

33 Анализ алгоритма сбалансированного многопутевого слияния (пример) 33 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Входная последовательность: Распределение по сериям

34 Анализ алгоритма сбалансированного многопутевого слияния (проход 1) 34 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6:

35 Анализ алгоритма сбалансированного многопутевого слияния (проход 2) 35 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: 1, 2, 3 4, 5, , 8, , 11, 12

36 Анализ алгоритма сбалансированного многопутевого слияния (проход 2) 36 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: 1, 2, 3 4, 5, , 8, , 11, 12 1, 2, 34, 5, 67, 8, 9 10, 11, 12 1, 2, 3, 4, 5, 6, 7, 8, 9

37 Анализ алгоритма сбалансированного многопутевого слияния (проход 3) 37 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: 1, 2, 34, 5, 67, 8, 9 1, 2, 3, 4, 5, 6, 7, 8, 9 10, 11, 12 1, 2, 3, 4, 5, 6, 7, 8, 910, 11, 12 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

38 Анализ алгоритма сбалансированного многопутевого слияния 38 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Пусть во входном файле имеетcя r серий, для сортировки используется N файлов, N h = N/2. Серии поровну распределяются по N h файлам. Следовательно в каждом из них образуется r/N h серий. При слияния файлов первые серии в каждом из них объединяются в одну, тоже самое происходит со вторыми, третьими, … N h -ми сериями. В итоге количество серий будет сокращено с r до r/N h. Таким образом, каждый проход уменьшает число серий в N h раз. Число проходов не превышает log N h n

39 Реализация алгоритма сбалансированного многопутевого слияния 39 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Файл представляется в программе через структуру struct file, описанную ранее. Для управления набором из N файлов необходимо использовать массив: struct file tapes[N]; N-файловый набор F разбивается пополам(F 1 и F 2 ): F 1 содержит промежуточный результат (серии равномерно распределены по файлам) Серии из F 1 сливаются в F 2. Переключение ролей: F 1 F 2. Для переключения требуется отображение файлов на их роли на данном проходе алгоритма.

40 Отображение файлов 40 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Отображение реализуется с помощью целочисленного массива: int map[N]; // (N % 2) == 0 Массив map содержит индексы элементов массива tapes ( struct file tapes[N] ). Первая половина map: map[0]...map[N/2–1] содержит индексы файлов, из которых производится слияние. Вторая половина map: map[N/2]...map[N-1] хранит индексы файлов в которые производится.

41 Анализ алгоритма сбалансированного многопутевого слияния (проход 1) 41 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: map k1k1 k2k2

42 Анализ алгоритма сбалансированного многопутевого слияния (проход 2) 42 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: 1, 2, 3 4, 5, , 8, , 11, map k1k1 k2k2

43 Анализ алгоритма сбалансированного многопутевого слияния (проход 2) 43 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: 1, 2, 3 4, 5, , 8, , 11, 12 1, 2, 34, 5, 67, 8, 9 10, 11, 12 1, 2, 3, 4, 5, 6, 7, 8, map k1k1 k2k2

44 Анализ алгоритма сбалансированного многопутевого слияния (проход 3) 44 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: 1, 2, 34, 5, 67, 8, 9 1, 2, 3, 4, 5, 6, 7, 8, 9 10, 11, 12 1, 2, 3, 4, 5, 6, 7, 8, 910, 11, 12 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, map k1k1 k2k2

45 Анализ алгоритма сбалансированного многопутевого слияния (проход 3) 45 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» : 2: 3: 4: 5: 6: 1, 2, 3, 4, 5, 6, 7, 8, 910, 11, 12 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, map k1k1 k2k2

46 Процедура слияния серий из N файлов 46 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1. k - номер выходного файла (изначально k = N/2) 2. Проверяется пустота каждого файла tapes[map[i]], i = 0... k Если i-й файл пуст, тo: map[i] = map[k 1 -1], k 1 =k Определяется наименьший элемент среди входных файлов v=min(tapes[map[i]], i = 0... k 1 ) 4. write(v, tapes[map[k]) 5. k = k+1, если k N k = N/2

47 Литература 47 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1.Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - М.: Мир, с., ил. 2.Кнут, Д.Э. Искусство программирования. Том 1. Основные алгоритмы. – Вильямс, – (Серия: Искусство программирования). – ISBN