- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Лучший, средний и худший случаи
О-нотация описывает так называемый средний случай скорости выполнения алгоритма.
Алгоритм пузырьковой сортировки завершает работу сразу, как только обнаруживается, что все элементы входного массива поступили на вход в виде последовательности, уже отсортированной в нужном порядке. Такая ситуация называется лучшим случаем. Время сортировки в этом случае будет минимальным.
Алгоритм поиска стремится обнаружить в некоторой таблице определенную запись по первичному ключу. Если искомая запись в таблице отсутствует, то алгоритму приходится просматривать все элементы таблицы от начала до конца. Такой случай связан с максимальными затратами времени поиска, поэтому он называется худшим случаем.
Лучшие случаи, как правило, не интересны, поскольку программисты всегда судят о быстродействии алгоритма, когда он выполняется при наихудших условиях. Поэтому при выборе алгоритма следует учитывать значения в О-нотации для среднего и худшего случаев.
Алгоритмы и платформы
В обсуждении быстродействия алгоритмов до сих пор не затрагивались вопросы, касающиеся операционной системы и оборудования компьютера, на котором выполняется программная реализация алгоритма. О-нотация справедлива только для некоторой виртуальной машины, в которой нет узких мест в операционной системы и оборудовании. На практике приложения и алгоритмы выполняются на реальных физических компьютерах, поэтому при анализе алгоритмов следует учитывать и данный фактор.
Виртуализация памяти
В подразделе 2.3 показано, что виртуальная память разбивается на страницы. Если физическая страница ОЗУ занята виртуальной страницей приложения, то приложение обращается к этой странице по реальным адресам кода или данных. Если страница, к которой пытается обратиться приложение, находится на диске, а свободного места в ОЗУ нет, то возникает ошибка отсутствия страницы (page fault). При этом процессор освобождает физическую страницу, записывает ее на диск, а на освободившееся место в ОЗУ передает с диска запрашиваемую страницу. Эти процессы в 32-разрядной операционной системе происходят постоянно. Физические страницы записываются на диск и считываются с диска. В большинстве случаев пользователь ничего не замечает, за исключением ситуации, которая называется пробуксовкой.
Пробуксовка может негативно сказаться на приложении, основанном на эффективном алгоритме, превращая высокоскоростную программу в медленную. Допустим, некоторое приложение создает большие массивы крупных блоков памяти, выделяя память из кучи. Такое выделение приведет к тому, что будут заниматься новые страницы, а старые будут записываться на диск. Затем приложение считывает эти большие блоки последовательно, начиная с начала массива и в направлении его конца. При этом никаких проблем не возникает.
Если же приложение считывает блоки в произвольном порядке, например, сначала из блока 56, затем из блоков 123, 12, 234 и т. д., то частота ошибок отсутствия страницы увеличивается. Индикатор работы диска будет гореть почти постоянно, а скорость работы приложения заметно упадет. Это и есть пробуксовка – непрерывный обмен страницами между диском и ОЗУ, вызванный запросами приложения страниц в произвольном порядке.
Свести вероятность пробуксовки к минимуму позволяет метод, называемый повышением уровня локальности ссылок. Этот метод предполагает, что элементы одной и той же структуры данных должны находиться в виртуальной памяти как можно ближе друг к другу.
Например, массив записей имеет очень высокий уровень локальности ссылок, так как элемент с индексом i находится в памяти с элементом с индексом i+1. Связанные динамические списки обладают низким уровнем локальности ссылок, поскольку их элементы размещаются в памяти произвольно.
Программист не может управлять конкретным расположением блоков памяти. При многочисленных вставках и удалениях элементов в динамических связных структурах эти элементы могут располагаться на разных страницах. В этих случаях можно рекомендовать использовать не одиночные, а «блочные» элементы, которые на самом деле являются последовательными блоками одиночных элементов и занимают непрерывные участки памяти.
Говоря «один элемент располагается рядом с другим элементом», мы используем понятие локальности в смысле расстояния. С другой стороны это понятие можно трактовать по отношению ко времени. Воплощением локальности ссылок во времени является кэш-память.