Исследование методов оптимизации поиска
5.1. Цель работы:
- исследовать и изучить методы поиска с перемещением в начало и транспозицией;
- овладеть умениями и навыками написания на С++ программ по исследованию методов поиска с перемещением в начало и транспозицией.
Порядок выполнения работы
- ознакомиться с краткой теорией и примерами решения задач, относящихся к методам оптимизации поиска;
- ответить на контрольные вопросы и получить оценку по знанию теории;
- получить задание на выполнение конкретного варианта лабораторной работы и выполнить его;
- написать и отладить программу решения задачи на языке С++;
- составить отчет по лабораторной работе и защитить его у преподавателя.
Содержание отчета по ЛР
- наименование ЛР и ее цель;
- задание на ЛР согласно варианту;
- листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;
- результаты работы программы.
Краткая теория
Поиск (search) является одной из основ обработки данных в ЭВМ. Его назначение состоит в том, чтобы по заданному аргументу найти среди массива данных те данные, которые соответствуют этому аргументу или определить, что этих данных нет. Если этих данных нет, добавить их в массив данных.
Набор любых данных будем называть таблицей или файлом. Каждое данное или элемент структуры отличается каким-то признаком от других данных. Этот признак называется ключом. Ключ может быть уникальным, т.е. в таблице только одно данное с таким ключом, иначе уникальные ключи называются первичным ключом.
Вторичный ключ в одной таблице может повторяться, но по нему тоже можно организовать поиск. Ключи данных собраны в одном месте (таблице).
Ключи, которые выделены из таблицы данных и организованы в свой файл, называются внешним ключами. Если ключ в записи, то он называется внутренним ключом.
Поиском по заданному аргументу называется алгоритм, определяющий соответствие ключа данного с заданным аргументом. Результатом работы алгоритма поиска может быть нахождение этого данного или отсутствие данного в таблице. В случае отсутствия данного возможны две операции:
1. Индикация того, что данного нет.
2. Вставка данного в таблицу.
Пусть К - массив ключей, тогда для всех К(i) существует R(i) - данное. KEY - аргумент поиска. Ему соответствует информационная запись REC. В зависимости от того, какова структура данных в таблице, различают несколько видов поиска.
Переупорядочение таблицы поиска.
Всегда можно говорить о некотором значении вероятности нахождения того или иного элемента.
P(i) - вероятность нахождения элемента.
В этом случае таблица поиска представляется как система с дискретными состояниями, а искомый элемент характеризуется i -ым состоянием системы, вероятность которого P(i).
P(1) + P(2) +... + P(n) = 1
Количество сравнений Z при поиске в таблице, т.е. количество сравнений, необходимых для поиска по заданному аргументу, представляет собой значение дискретной случайной величины, определяемой номерами состояний и вероятностями состояний системы.
Z=1*P(1) + 2*P(2) + 3*P(3) +... + n*P(n)
Таблица данных должна быть упорядочена таким образом, чтобы в начале таблицы были элементы с большими вероятностями поиска или элементы, к которым чаще всего обращаются в таблице.
P(1) >= P(2) >= P(3) >=... >= P(n)
Имеется два основных метода переупорядочивания таблиц поиска:
1) Переупорядочивание путем перестановки найденного элемента в начало списка.
2) Метод транспозиции.
Переупорядочивание путем перестановки найденного элемента в начало списка.
Найденный элемент сразу оказывается в голове списка.
На рисунке проиллюстрирован случай, когда найденный элемент второй в списке. Первоначально указатель q нулевой, указатель p указывает на начало списка; p перемещается на второй элемент, а q на первый. Указатель начала списка (table) перемещается на второй элемент, а указатель второго элемента на третий. Таким образом, второй элемент перемещается на первое место.
Метод транспозиции
В данном методе найденный элемент переставляется на один элемент к голове списка. Если к этому элементу обращаются часто, то он, постепенно перемещаясь к началу списка, скоро окажется в его голове.
Этот метод удобен тем, что он эффективен не только в списковых структурах, но и в неупорядоченных массивах, т.к. меняются местами только два рядом стоящих элемента.
Будем использовать три указателя:
p - рабочий указатель, указывает на элемент.
q - вспомогательный указатель, отстает на один шаг от p.
s - вспомогательный указатель, отстает на два шага от p.
Рисунок иллюстрирует случай, когда найденный элемент третий в списке. Найденный нами третий элемент передвигается на один шаг к голове списка (т.е. становится вторым). Указатель первого элемента перемещается на третий элемент, указатель второго элемента на четвертый, таким образом, третий элемент перемещается на второе место. Если к данному элементу обратиться еще раз, то он окажется в голове списка.