- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Кэширование
Под термином кэш (cache запас, тайник) понимают некоторый участок памяти, используемый в качестве дополнительного источника памяти для оптимизации процессов обмена. Хорошо известен такой способ кэширования дисковой памяти, как организация виртуального диска. С точки зрения прикладной программы эта область выглядит как обычный, хотя и очень быстрый, диск. А на самом деле – это область оперативной (т. е. энергозависимой) памяти, которая выделяется для временного хранения файлов, что существенно повышает эффективность работы компьютера при интенсивном файловом обмене.
Виртуальную память можно считать кэшированием оперативной памяти за счет дисковой памяти. Виртуализация памяти позволяет компенсировать наличие такого недостатка оперативной памяти, как ее сравнительно небольшой объем.
Все современные компьютеры используют кэш процессора. Обычно это блок высокоскоростной памяти, представляющей собой буфер между процессором и его регистрами и основной памятью. Когда процессору необходимо считать некоторые данные из ОЗУ, кэш проверяет, есть ли эти данные в его памяти, и если требуемых данных нет, считывает их.
Анализ алгоритмов
Быстродействие – основной показатель эффективности алгоритма
Анализ алгоритмов заключается в том, чтобы предсказать требуемые для его выполнения ресурсы. Иногда оценивается потребность в таких ресурсах, как объем памяти, пропускная способность сети или необходимое аппаратное обеспечение, однако чаще всего определяется время вычислений.
Если бы компьютеры были неограниченно быстрыми, подошел бы любой корректный алгоритм решения задачи. Сегодня есть весьма производительные компьютеры, но их быстродействие не может быть бесконечно большим. Память тоже дешевеет, но она не может быть бесплатной. Следовательно, время вычислений – это такой же ограниченный ресурс, как и объем необходимой памяти. Разумному распределению этих ресурсов способствует применение алгоритмов, эффективных с точки зрения расходов памяти и времени. При этом решающим фактором выбора алгоритма является время его выполнения.
Время работы алгоритма зависит от аппаратного обеспечения (процессора, тактовой частоты, размера памяти, объема дискового пространства и т.п.) и программного обеспечения (операционной системы, среды программирования, компилятора), с помощью которых осуществляется реализация, компиляция и выполнение алгоритма. Например, при всех равных условиях время выполнения алгоритма для определенного количества исходных данных будет меньше при использовании более мощного компьютера или при записи алгоритма на машинном коде по сравнению с его исполнением машиной, которая выполняет интерпретацию текста алгоритма. Однако решающим фактором, влияющим на быстродействие, считается размер входных данных алгоритма.
Очевидно, время выполнения алгоритма возрастает при увеличении размера исходных данных (input size). Например, время, затрачиваемое на сортировку числового массива, увеличивается при увеличении количества сортируемых чисел. Для сравнительного анализа нескольких алгоритмов, решающих одну и ту же задачу, целесообразно применить следующую методику:
задать для эксперимента один из сравниваемых алгоритмов;
для заданного алгоритма провести ряд экспериментов, в которых используется различное количество исходных данных N ( );
далее полученные результаты наглядно представляются в виде графика, на котором каждый m-й случай (m = 1, 2, …, M) выполнения алгоритма обозначается с помощью одиночной точки. У этой точки координата по оси абсцисс равна размеру исходных данных , а координата по оси ординат – времени выполнения алгоритма ;
задать следующий проверяемый алгоритм, и если он не является последним в наборе алгоритмов, то перейти к п. 2, если набор сравниваемых алгоритмов исчерпан, то завершить анализ.
Результатом применения такой методики является диаграмма с графиками, число которых равно количеству исследуемых алгоритмов. На рисунке 3.1 показан случай, когда сравниваются два алгоритма.
Рисунок 3.1 – Результаты исследования времени выполнения двух алгоритмов
Результаты, представленные на рисунке 3.1, показывают, что график времени выполнения алгоритма 2 располагается ниже графика для алгоритма 1. Следовательно, алгоритм 2 является более эффективным, нежели алгоритм 1, для заданных наборов исходных данных.
Чтобы сделать более определенные выводы на основе экспериментальных исследований, необходимо использовать не одиночные, а многочисленные корректные экземпляры исходных данных для достаточно большого числа экспериментов. Это позволит определить некоторые статистические характеристики в отношении времени выполнения алгоритмов.
Экспериментальные исследования очень полезны, однако при их проведении существуют три основных ограничения:
эксперименты могут проводиться с использованием ограниченного числа наборов исходных данных;
для сравнения эффективности двух алгоритмов необходимо, чтобы эксперименты проводились на одинаковом аппаратном и программном обеспечении;
для экспериментального изучения необходимо провести реализацию и выполнение алгоритма.
Чтобы провести анализ алгоритма без экспериментов, можно использовать аналитический подход, который заключается в подсчете простейших операций, выполняемых при работе алгоритма.