- •Введение
- •Содержание и структура пособия
- •Задачи поиска в информатике
- •Задача поиска в таблице
- •Поиск в массивах
- •Линейный поиск
- •Бинарный поиск
- •Вопросы и упражнения
- •Алгоритмы сортировки массивов
- •Задачи сортировки таблиц и массивов
- •Простые алгоритмы сортировки
- •Алгоритм пузырька (BubbleSort)
- •Алгоритм выбора (SelectionSort)
- •Алгоритм вставок (InsertionSort)
- •Общая характеристика простых алгоритмов
- •Алгоритм Шелла (ShellSort)
- •Алгоритм быстрой сортировки (QuickSort)
- •Алгоритм пирамидальной сортировки (HeapSort)
- •Алгоритмы сортировки слиянием (MergeSort)
- •Задача внешней сортировки
- •Сравнение алгоритмов сортировки
- •Вопросы и упражнения
- •Сортировка и поиск с использованием деревьев
- •Задача поиска со вставкой
- •Бинарные деревья поиска
- •Var t: Tree; {Кореньдерева}
- •X: KeyType; {Искомый ключ}
- •Var found: Boolean {Найдено или вставлено?}
- •Страничные деревья поиска
- •Использование b-деревьев в базах данных
- •Вопросы и упражнения
- •Специальные методы сортировки и поиска
- •Поразрядная сортировка
- •Поиск в словаре и нагруженные деревья
- •Вопросы и упражнения
- •Хеширование
- •Основные понятия хеширования
- •Способы построения хеш-функций
- •Общие требования к хеш-функциям
- •Алгоритм деления
- •Алгоритм середины квадрата
- •Алгоритм умножения
- •Хеширование строковых ключей
- •Методы разрешения коллизий
- •Алгоритм линейных проб
- •Алгоритм квадратичных проб
- •Алгоритм двойного хеширования
- •Алгоритм списков в динамической памяти
- •Алгоритм Уильямса
- •Эффективность хеширования и сравнение с другими методами поиска
- •Вопросы и упражнения
- •Дополнительные вопросы поиска
- •Определение порядковых статистик
- •Задача поиска в строке
- •Постановка задачи и «прямое» решение
- •Алгоритм Кнута, Морриса и Пратта
- •Алгоритм Бойера – Мура
- •Вопросы и упражнения
- •Заключение
- •Библиографический список
Задача внешней сортировки
Все ранее рассматривавшиеся алгоритмы сортировки были ориентированы на работу с массивом, полностью помещающемся в оперативной памяти компьютера. Между тем, несмотря на постоянное возрастание емкости памяти современных компьютеров, не теряют своей актуальности задачи сортировки и поиска в больших наборах данных, которые хранятся в файлах и не могут быть полностью считаны в оперативную память. В частности, подобные задачи возникают при работе систем управления базами данных.
Задача сортировки данных, расположенных во внешней памяти и только по частям считываемых в оперативную память, называется задачей внешней сортировки(в отличие отзадачи внутренней сортировки, которую мы рассматривали до сих пор).
Формально говоря, любой из описанных алгоритмов может быть применен и к задаче внешней сортировки. Это возможно хотя бы потому, что современные операционные системы позволяют работать с файлами как с виртуальными массивами, т.е. обращаться к их записям по индексу, возложив на систему планирование и выполнение операций чтения и записи данных на внешнее устройство. Однако попытка применить, например, QuickSortилиHeapSortдля сортировки файла вызовет катастрофическое замедление работы, как только файл перестанет целиком помещаться в оперативной памяти, отведенной программе.
Это связано с тем, что алгоритмы внутренней сортировки оптимизированы по количеству операций, выполняемых над данными в оперативной памяти, прежде всего операций сравнения ключей и операций присваивания (перестановки) записей. Делая оценки эффективности алгоритмов, мы подсчитывали количество итераций циклов, а основным содержанием каждой итерации были как раз сравнения и присваивания.
Как известно, операции обмена с внешней памятью (т.е. чтения и записи на устройства) выполняются во много раз медленнее. При этом надо учитывать не только более низкую скорость передачи данных, но и существенное замедление работы при поиске требуемого блока данных (сектора диска). Поэтому при оценке алгоритмов внешней сортировки следует подсчитывать в первую очередь количество операций обращения к устройству, а операциями, выполняемыми в оперативной памяти, можно в большинстве случаев вообще пренебречь.
Если с этой точки зрения посмотреть на алгоритмы QuickSort,HeapSortиShellSort, то картина окажется невеселой. Все эти алгоритмы резво скачут из конца в конец сортируемого массива, обеспечивая высокую эффективность прежде всего за счет дальних пересылок элементов. Для этих алгоритмов чуть ли не каждое обращение к элементу массива может потребовать выполнения операции чтения или записи в файл.
Совершенно по-другому ведет себя сортировка слиянием.
Обычно этот алгоритм для файлов реализуют как чередование двух фаз работы: фазы разделения и фазы слияния (рис. 3.3).
Рис. 3.3. Двухфазное слияние файлов
На фазе разделения исходный файл Aпросматривается от начала до конца и из него выделяются серии записей, упорядоченные по возрастанию. Нечетные по счету серии записываются во вспомогательный файлB1, четные – в файлB2.
На фазе слияния просматриваются файлы B1иB2, прочитанные из них серии попарно сливаются и записываются в файлA.
Фазы разделения и слияния повторяются до тех пор, пока в Aне будет записана единственная серия, содержащая все элементы в отсортированном виде.
Число проходов разделения/слияния может быть значительно сокращено, если на первом проходе сразу после чтения очередной порции данных из файла выполнить внутреннюю сортировку этой порции любым эффективным алгоритмом (например, QuickSort). Это будет эквивалентно созданию очень длинных возрастающих серий, размер которых ограничен только доступным объемом оперативной памяти.
Чтение и запись файлов как на фазе разделения, так и на фазе слияния выполняется только последовательно, от начала к концу. Эта особенность алгоритмов слияния была особенно важна в старые времена, когда основным видом внешних носителей данных были магнитные ленты. Однако и при работе с устройствами произвольного доступа (дисками) желательно как можно меньше пользоваться этим самым произвольным доступом, поскольку он приводит к слишком частым перемещениям читающих головок и, следовательно, к замедлению работы.
Основной недостаток алгоритмов слияния – потребность во вспомогательном массиве – для случая сортировки файлов выступает как потребность в двух вспомогательных файлах B1иB2, суммарный размер которых равен размеру сортируемого файла. Конечно, это не очень приятное свойство, однако дисковое пространство обычно является менее дефицитным ресурсом, чем оперативная память.
Оценка эффективности методов внешней сортировки «в смысле O-большое», приводит к результату, на первый взгляд парадоксальному. Одна и та же оценкаT(n) = O(nlog(n))получается и для «подходящего»MergeSort, и для «неподходящего»QuickSort. Но здесь надо вспомнить, что оценка с точностью доO-большого характеризует только скорость роста времени при увеличенииn, конкретные же значенияT(n)очень сильно различаются для разных алгоритмов. В первом приближении можно считать, что для алгоритмов слияния значениеnкак бы делится на число записей таблицы, помещающихся в одном секторе диска.