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

Вспомогательные материалы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 1.Скачайте с сайта файл search_files_v1.tar.bz, который содержит вспомогательные файлы для выполнения данной практической работы. 2.Распакуйте архив командой: tar –xjvf search_files_v1.tar.bz. 3.В результате в текущем каталоге будет создана директория с именем search_files_v1, содержащая следующие файлы: 1)seqsearch.c 2)test_2^10_rnd 3)test_2^10_seq 4)test_2^13_rnd 5)test_2^13_seq 6)test_2^16_rnd 7)test_2^16_seq 4.Файлы test_2^XX_seq и test_2^XX_rnd – тестовые данные для проверки алгоритмов. Постфикс _seq означает что числа упорядочены, в файле с постфиксом _rnd расположены те же числа, что и в соответствующем _seq файле, но в случайном порядке. 5.Файл seqsearch.c содержит исходный код алгоритма последовательного поиска (функция search) и средства измерения времени его работы.

Тестовые данные и измерение времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 Все тестовые файлы имеют одинаковый формат: n R \n Где n – количество чисел в последовательности a, а R – диапазон возможных значений из которого будут поступать входные данные. При измерении времени работы алгоритм тестируется в двух режимах: internal – поиск каждого элемента из последовательности. external – поиск каждого числа из диапазона [1; R]. Результат работы программы при обработке 210 упорядоченных элементов представлен ниже: $./seqsearch < test_2^10_seq Time for internal search: , avg time: e-06 Time for external search: , avg time: e-06 Поле "Time for search" указывает общее время тестирования, поле "avg time" указывает сколько в среднем потребовалось на поиск одного элемента.

Демонстрационная программа © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 int search(int ptr[], int n, int x) { int i; for(i=0; i= n ) i = -1; return i; } Программа seqsearch.c реализует алгоритм линейного поиска. Он оформлен в виде функции search, на вход которой поступает массив (ptr), в котором осуществляется поиск, размер (n) этого массива и искомое значение (x). В seqsearch.c также реализовано измерение общего времени поиска элементов гарантированно принадлежащих массиву (internal search) и элементов диапазона [1, R] (external search). Измерение времени выполняется при помощи функции gettimeofday(). Результатом измерения является среднее время внутреннего и внешнего поиска одного элемента. Это значение и должно использоваться в работе.

Теоретические оценки вычислительной сложности последовательных алгоритмов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 1. Алгоритмы последовательного поиска (seqsearch.c) и поиска с барьером 1.1 Поиск среди элементов 1.2 Поиск по диапазону [1;R] 2. Алгоритм последовательного поиска с барьером по отсортированной последовательности 2.1 Поиск среди элементов 2.2 Поиск по диапазону [1;R]

Задача 1. Анализ алгоритма последовательного поиска © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 Согласно теоретическому анализу, среднее количество операций последовательного алгоритма при внутреннем поиске составляет (1), а при внешнем – (2): (1) При достаточно большом R второе соотношение может быть записано так: Задание. Используя программу seqsearch.c показать: 1.Сложность последовательного алгоритма линейна, т.е. увеличение размера массива в k раз приводит к k-кратному увеличению времени поиска. 2.Среднее время внешнего и внутреннего поиска отличается примерно в 2 раза, согласно соотношениям (1) и (3). (2) (3)

Задача 2. Анализ алгоритма последовательного поиска с барьером © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Для алгоритма последовательного поиска с барьером справедлива соотношения (1) – (3) предыдущего слайда. Однако поиск с барьером на каждой итерации цикла выполняет на одну операцию меньше. Задание. Изменить функцию search программы seqsearch.c, реализовав поиск с барьером. 1.Являются ли выводы, сделанные для алгоритма последовательного поиска, справедливыми для поиска с барьером. 2.Дает ли выигрыш во времени исключение одной из операции сравнения в алгоритме поиска с барьером (по сравнению с последовательным поиском). Экспериментально сравнить среднее время работы алгоритмов. BARRIER_SEARCH(a, x) 1i 1 2a n+1 x // !!! 3 while a i x do 4 i i if i > n then i 0 6 return i LINEAR_SEARCH(a, x) 1i 1 2 while i n и a i x do 3 i i if i > n then i 0 5 return i

Задача 3. Анализ алгоритма последовательного поиска с барьером в упорядоченной последовательности. © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Согласно теоретическому анализу, среднее количество операций алгоритма поиска с барьером в упорядоченной последовательности при внутреннем поиске составляет (1), а при внешнем – (2): (1) Задание. Доработать имеющуюся программу анализа алгоритма сортировки с барьером, чтобы она учитывала упорядоченность входных данных. С помощью полученной программы ответить на следующие вопросы: 1.Является ли вычислительная сложность данного алгоритма линейной (увеличение размера массива в k раз приводит к k-кратному увеличению времени поиска). 2.Есть ли различия во времени внешнего и внутреннего поиска. 3.Выполнить сравнение данного алгоритма с рассмотренными ранее. (2)

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