Поиск. Абстрактные типы данных

Поиск Абстрактные типы данных Лекция 4 1 Задача поиска элемента по ключу ▪ Имеется последовательность ключей 𝑎1 , 𝑎2 , … , 𝑎𝑖 , … , 𝑎𝑛 ▪ Требуется найти номер элемента, который совпадает с заданным ключом key Пример Дана последовательность из 10 ключей Требуется найти элемент с ключом key = 181 Index 1 2 3 4 5 6 7 8 9 10 Key 178 150 190 177 155 181 179 167 204 175 Data Решение – искомый элемент с индексом 6 2 Линейный поиск (linear search) function LinearSearch(v[1..n], n, value) for i = 1 to n do if v[i] = value then return i end if end for return -1 TLinearSearch = O(n) end function ▪ Просматриваем элементы, начиная с первого, и сравниваем ключи ▪ В худшем случае искомый элемент находится в конце массива или отсутствует ▪ Количество операций в худшем случае (worst case): 𝑻(𝒏) = 𝑶(𝒏) 3 Бинарный поиск (Binary Search) ▪ Имеется упорядоченная последовательность ключей 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎𝑖 ≤ ⋯ ≤ 𝑎𝑛 ▪ Требуется найти позицию элемента, ключ которого совпадает с заданным ключом key ▪ Бинарный поиск (Binary search) 1. Если центральный элемент равен искомому, конец 2. Если центральный меньше, делаем текущей правую половину массива 3. Если центральный больше, делаем текущей левую половину массива 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 Поиск элемента 42 4 Бинарный поиск (Binary Search) ▪ Имеется упорядоченная последовательность ключей 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎𝑖 ≤ ⋯ ≤ 𝑎𝑛 ▪ Требуется найти позицию элемента, ключ которого совпадает с заданным ключом key ▪ Бинарный поиск (Binary search) 1. Если центральный элемент равен искомому, конец 2. Если центральный меньше, делаем текущей правую половину массива 3. Если центральный больше, делаем текущей левую половину массива 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 Поиск элемента 42 5 Бинарный поиск (Binary Search) ▪ Имеется упорядоченная последовательность ключей 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎𝑖 ≤ ⋯ ≤ 𝑎𝑛 ▪ Требуется найти позицию элемента, ключ которого совпадает с заданным ключом key ▪ Бинарный поиск (Binary search) 1. Если центральный элемент равен искомому, конец 2. Если центральный меньше, делаем текущей правую половину массива 3. Если центральный больше, делаем текущей левую половину массива 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 Поиск элемента 42 6 Бинарный поиск (Binary Search) function BinarySearch(v[1..n], n, key) l = 1 // Левая граница массива (low) h = n // Правая граница массива (high) while l <= h do mid = (l + h) / 2 // Возможно переполнение mid, // Решение: mid = l + ((h - l) / 2) if v[mid] = key then return mid else if key > v[mid] then l = mid + 1 else h = mid - 1 end if end while return -1 end function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 key = 100 (worst case) 7 Бинарный поиск (Binary Search) function BinarySearch(v[1..n], n, key) l = 1 // Левая граница массива (low) h = n // Правая граница массива (high) while l <= h do mid = (l + h) / 2 // Возможно переполнение mid, // Решение: mid = l + ((h - l) / 2) if v[mid] = key then return mid else if key > v[mid] then l = mid + 1 else h = mid - 1 end if end while return -1 end function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 key = 100 (worst case) 8 Бинарный поиск (Binary Search) function BinarySearch(v[1..n], n, key) l = 1 // Левая граница массива (low) h = n // Правая граница массива (high) while l <= h do mid = (l + h) / 2 // Возможно переполнение mid, // Решение: mid = l + ((h - l) / 2) if v[mid] = key then return mid else if key > v[mid] then l = mid + 1 else h = mid - 1 end if end while return -1 end function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 key = 100 (worst case) 9 Бинарный поиск (Binary Search) function BinarySearch(v[1..n], n, key) l = 1 // Левая граница массива (low) h = n // Правая граница массива (high) while l <= h do mid = (l + h) / 2 // Возможно переполнение mid, // Решение: mid = l + ((h - l) / 2) if v[mid] = key then return mid else if key > v[mid] then l = mid + 1 else h = mid - 1 end if end while return -1 end function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 key = 100 (worst case) 10 Бинарный поиск (Binary Search) function BinarySearch(v[1..n], n, key) l = 1 // Левая граница массива (low) h = n // Правая граница массива (high) while l <= h do mid = (l + h) / 2 // Возможно переполнение mid, // Решение: mid = l + ((h - l) / 2) if v[mid] = key then return mid else if key > v[mid] then l = mid + 1 else h = mid - 1 end if end while return -1 end function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 key = 100 (worst case) 11 Эффективность бинарного поиска function BinarySearch(v[1..n], n, key) l = 1 // Левая граница массива (low) h = n // Правая граница массива (high) while l <= h do mid = (l + h) / 2 // 2 операции if v[mid] = key then // 2 операции return mid else if key > v[mid] then // 2 операции l = mid + 1 // 1 операция else h = mid - 1 Количество операций в худшем случае end if end while 𝑻(𝒏) = 𝒌𝑻𝒘𝒉𝒊𝒍𝒆 = 𝟕𝒌 return -1 end function ▪ 𝒌 – количество итераций цикла while ▪ 𝑇𝑤ℎ𝑖𝑙𝑒 – количество операций в теле цикла while 𝑻𝒘𝒉𝒊𝒍𝒆 = 2 + 2 + 2 + 1 = 7 12 Эффективность бинарного поиска function BinarySearch(v[1..n], n, key) Количество 𝒌 разбиений массива l = 1 // Левая граница массива (low) ▪ Массив длины 𝑛 h = n // Правая граница массива (high) while l <= h do ▪ Массив длины 𝑛 / 2 mid = (l + h) / 2 2 операции ▪ // Массив длины 𝑛 / 4 if v[mid] = key then ▪ ... // 2 операции return mid ▪ Массив длины 𝒏 / 𝟐𝒌 = 𝟏 else if key > v[mid] then // 2 операции 𝒏 l = mid + 1 // 1 операция = 𝟏, 𝒏 = 𝟐𝒌 , 𝒌 𝟐 else h = mid - 1 𝐥𝐨𝐠 𝟐 𝒏 = 𝐥𝐨𝐠 𝟐 𝟐𝒌 end if 𝒌 = 𝐥𝐨𝐠 𝟐 𝒏 end while return -1 𝑻 𝒏 = 𝒄𝟏𝐥𝐨𝐠 𝟐 𝒏 = 𝑶(𝐥𝐨𝐠 𝒏) end function 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 key = 100 (worst case) 13 Эффективность бинарного поиска function BinarySearch(v[1..n], n, key) Количество 𝒌 разбиений массива l = 1 // Левая граница массива (low) ▪ Массив длины 𝑛 h = n // Правая граница массива (high) while l <= h do ▪ Массив длины 𝑛 / 2 mid = (l + h) / 2 2 операции ▪ // Массив длины 𝑛 / 4 if v[mid] = key then ▪ ... // 2 операции return mid ▪ Массив длины 𝒏 / 𝟐𝒌 = 𝟏 else if key > v[mid] then // 2 операции 𝒏 l = mid + 1 // 1 операция = 𝟏, 𝒏 = 𝟐𝒌 , 𝒌 𝟐 else h = mid - 1 𝐥𝐨𝐠 𝟐 𝒏 = 𝐥𝐨𝐠 𝟐 𝟐𝒌 end if 𝒌 = 𝐥𝐨𝐠 𝟐 𝒏 end while return -1 𝑻 𝒏 = 𝒄𝟏𝐥𝐨𝐠 𝟐 𝒏 = 𝑶(𝐥𝐨𝐠 𝒏) end function Бинарный поиск неэффективно использует кэш-память процессора – доступ к элементам массива непоследовательный (прыжки по массиву) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94 key = 100 (worst case) 14 Galloping search – «поиск от края» ▪ Задан отсортированный массив 𝐴[𝑛] ▪ Алгоритм Galloping проверяет ключи с индексами 1, 3, 7, 15, … , 2𝑖 − 1, … ▪ Проверка идет то тех пор, пока не будет найден элемент 𝐴 2𝑖 − 1 > 𝑘𝑒𝑦 ▪ Далее выполняется бинарный поиск в интервале 2𝑖−1 − 1, … , 2𝑖 − 1 ▪ 𝑻𝑮𝒂𝒍𝒍𝒐𝒑𝒊𝒏𝒈(𝒏) = 𝑶(𝒍𝒐𝒈𝒏) Поиск key = 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 3 3 5 7 9 13 23 25 29 31 33 37 41 42 46 49 50 52 67 73 81 94  Galloping search = One sided binary search, exponential search, doubling search  J. L. Bentley and A. C.-C. Yao. An almost optimal algorithm for unbounded searching // Information processing letters, 5(3):82–87, 1976 15 Поиск в массиве ▪ Задан неупорядоченный массив ключей (новые элементы добавляются крайне редко) ▪ Требуется периодически осуществлять поиск в массиве ▪ Решение 1 – “в лоб” за 𝑶(𝒏) Каждый раз при поиске использовать линейный поиск за 𝑂(𝑛) ▪ Решение 2 – в среднем за 𝑶(𝒍𝒐𝒈𝒏) 1. Один раз отсортировать массив за 𝑂(𝑛𝑙𝑜𝑔𝑛) или за 𝑂(𝑛 + 𝑘) 2. Использовать экспоненциальный поиск (Galloping) – 𝑂(𝑙𝑜𝑔𝑛) function Search(v[1:n], n, key) if issorted = false then Sort(v, n) // Устойчивая сортировка, вызывается редко issorted = true end if return GallopSearch(v, n, key) // Эксп. поиск O(logn) end function 16 Понятие типа данных (data type) ▪ Язык программирования позволяет оперировать с величинами различного вида: строки, числа, логические значения ▪ Тип данных (data type) – это атрибут любого значения, которое встречается в программе ▪ Тип данных определяет две характеристики: • множество допустимых значений, которые могут принимать данные, принадлежащие • набор операций, которые можно выполнять над данными этого типа к этому типу 17 Понятие типа данных (data type) ▪ Базовые (примитивные) типы данных: int, char, bool, string ▪ Cоставные типы данных (агрегатные, структурные, композитные типы) – это типы данных, которые формируются на основе базовых (например, массивы, структуры и классы в языках С и C++) ▪ Структура данных (data structure) – программная единица, реализующая хранение и выполнение операций над совокупностью однотипных элементов ▪ Набор функций для выполнения операций над структурой данных называется её интерф ейсом (interface) 18 Структура данных «связный список» /* Узел односвязного списка */ struct listnode { int value; /* Данные узла */ struct listnode *next; /* Указатель на следующий узел */ }; /* list_addfront: Добавляет узел в начало списка */ struct listnode *list_addfront(struct listnode *list, int value); /* list_lookup: Ищет узел с заданным значением */ struct listnode *list_lookup(struct listnode *list, int value); /* list_delete: Удаляет узел с заданным значением */ struct listnode *list_delete(struct listnode *list, int value); 19 Абстрактные типы данных ▪ Абстрактный тип данных (АТД, abstract data type) – это тип данных, который задан описанием своего интерфейса ▪ Способ хранения данных в памяти компьютера и алгоритмы работы с ними сокрыты внутри функций интерфейса (в этом суть абстракции) ▪ Если описать реализацию функций АТД, получим конкретную структуру данных 20 Абстрактный тип данных «список» ▪ Интерф ейс АТД список (list)  Insert  Delete  Lookup  Next  Prev ▪ Возможные реализации АТД список  Статический массив  Связный список Вычислительная сложность и сложность по памяти функций разных реализаций могут быть различными 21 Линейные типы данных Линейные типы данных (linear data types) Список (list) Стек (stack) Очередь (queue) Дек (deque) Insert() Delete() Lookup() Prev() Next() Push() Pop() Top() Enqueue() Dequeue() Front() PushBack() PushFront() PopFront() PopBack() Front() Back() 22 Нелинейные типы данных 23 Литература • [DSABook] Главы 4-5 24