-
Поиск с барьером
Алгоритм линейного поиска можно упростить, избавившись от проверки дополнительного условия, если быть уверенным, что в массиве обязательно присутствует элемент, совпадающий с образцом. Иногда истинность этого условия следует из знания того, как строился массив и образец поиска. Но можно добиться выполнения этого условия принудительно, соорудив в массиве "барьер", препятствующий выходу поиска за границы массива. С этой целью массив расширяется на один элемент и в качестве последнего элемента записывается "барьер" - образец поиска. В этом случае поиск всегда найдет образец. Если образца нет среди "родных" элементов массива, то он встретится в конце в виде "барьера".
Для упрощения больше подходит вторая версия алгоритма линейного поиска. Приведу реализацию этой схемы:
/// <summary>
/// Линейный поиск с барьером
/// Предусловие: В массиве существует элемент,
/// совпадающий с образцом pattern
/// </summary>
/// <param name="massiv">искомый массив</param>
/// <param name="pattern">образец поиска</param>
/// <returns>
/// индекс первого элемента, совпадающего с образцом
/// </returns>
public static int SearchBarrier(T[] massiv, T pattern)
{
int i = 0;
while (massiv[i].CompareTo(pattern) != 0)
i++;
return (i);
}
Заметьте, сам метод никаких барьеров не строит. Он лишь формулирует предусловие, требующее существование барьерного элемента в массиве. Ответственность за выполнение предусловия лежит на клиенте. Тот, кто вызывает метод, тот и должен заботиться о выполнении предусловия. Таковы принципы проектирования по контракту. Конечно, можно построить другую реализацию, где ответственность за построение барьера берет на себя сам метод.
-
Бинарный поиск
У
этого метода поиска много синонимичных
названий - метод деления пополам, двоичный
или бинарный поиск, метод дихотомии.
Все эти названия отражают тот приятный
факт, что в заранее отсортированном
массиве сравнение с одним элементом
позволяет вдвое уменьшить число
кандидатов. Для этого достаточно сравнить
образец с элементом массива, стоящим в
середине. Если образец совпадает с этим
элементом, то элемент найден и поиск
завершается. Если образец меньше
срединного элемента, то размеры области
поиска сокращаются вдвое: элемент может
находиться лишь в первой половине
массива. Если образец больше срединного
элемента, он находится во второй половине
массива. Введение двух параметров -
start
и finish,
задающих границы области поиска,
позволяет достаточно просто описать
схему алгоритма. Алгоритм бинарного
поиска намного эффективнее линейного
поиска в особенности для больших
массивов. Нетрудно понять, что для
отсортированного массива из n элементов
он требует не более чем
сравнений
образца с элементами массива. Вот его
возможная реализация:
/// <summary>
/// Бинарный поиск образца в упорядоченном массиве
/// Предусловие: Массив упорядочен
/// </summary>
/// <param name="massiv">искомый массив</param>
/// <param name="pattern">образец поиска</param>
/// <returns>
/// индекс элемента, совпадающего с образцом,
/// но не обязательно индекс первого вхождения,
/// -1, если образец не встречается в массиве
/// </returns>
public static int BinSearch(T[] massiv, T pattern)
{
int start = 0, finish = massiv.Length-1, mid = (start+finish)/2;
while (start <= finish)
{
if (massiv[mid].CompareTo(pattern) == 0) return (mid);
if(massiv[mid].CompareTo(pattern) == 1)
finish = mid-1;
else
start = mid+1;
mid = (start+finish)/2;
}
return(-1);
}
Как клиентский класс может пользоваться сервисами универсального класса Service? Приведу примеры работы с методами класса, когда в качестве клиента выступает класс из консольного проекта и класс из Windows проекта. Начнем с консоли. Клиент работает с массивом строк класса string. Он предпочитает использовать метод поиска с барьером и сам заботится об организации барьера до вызова метода:
public void TestSearch()
{
string answer = "yes";
int n;
Console.WriteLine("Введите n - число элементов массива");
n = Convert.ToInt32(Console.ReadLine());
string[] ar1 = new string[n + 1];
for (int i = 0; i < n; i++)
{
Console.WriteLine("Введите строку - элемент" +
" массива с номером {0}", i);
ar1[i] = Console.ReadLine();
}
do
{
string pat1;
Console.WriteLine("Введите строку - образец поиска");
pat1 = Console.ReadLine();
ar1[n] = pat1;
//Выполнено условие метода поиска с барьером
int k = Service<string>.SearchBarrier(ar1, pat1);
if (k != n)
Console.WriteLine("Образец pat1 = {0} найден в массиве!" +
"\nЭто элемент ar[{1}] = {2} ", pat1, k, ar1[k]);
else
Console.WriteLine("Образец pat1 ={0} не найден!", pat1);
Console.WriteLine("Продолжим? (yes/no");
answer = Console.ReadLine();
} while (answer != "no");
}
На рис. 7.8 показаны результаты работы метода.
увеличить изображение Рис. 7.8. Поиск по образцу в консольном проекте
Метод TestSearch включен в класс Testing консольного проекта SymbolsAndStrings, многократно использованного в предыдущих примерах. К консольному проекту присоединена библиотека классов - DLL с именем, содержащая универсальный класс Service<T>. При вызове метода этого класса, реализующего поиск с барьером, задается параметр типа, характеризующий тип элементов массива, в котором ведется поиск:
Service<string>.SearchBarrier(ar1, pat1)
Для проведения более полных экспериментов с методами поиска и проведения сравнения времени работы методов поиска построен Windows-проект с именем SearchAndSort, к которому подключена та же библиотека классов SearchAndSorting. Архитектурно новый проект представляет проект с главной кнопочной формой, которая позволяет перейти к анализу методов поиска либо к анализу методов сортировки, о которых пойдет речь далее. На рис. 7.9 показана форма, которая обеспечивает интерфейс, необходимый при исследовании поведения методов поиска по образцу.
увеличить изображение Рис. 7.9. Интерфейс, поддерживающий работу с методами поиска
На рисунке можно видеть, что интерфейс позволяет пользователю создать массив нужной размерности, заполнить его случайными числами из заданного диапазона, отсортировать массив, показать его текущее состояние. В проекте контролируется корректность задания исходных данных. Главное, что позволяет интерфейс, - анализировать, насколько успешно справляются различные методы с поиском заданного образца. Интерфейс позволяет также оценить время, затрачиваемое каждым из методов на поиск фиксированного образца в одном и том же массиве. На рисунке показано время, измеренное в одном из экспериментов. Как и следовало ожидать, поиск с барьером дает лучшие по времени результаты, чем классический линейный поиск. Поскольку эксперимент велся на отсортированном массиве, где применим и бинарный поиск, то можно видеть, что последний дает на порядок лучший результат.
Приводить полностью код интерфейсного класса не буду, предоставляя читателям восстановить его. Ограничусь лишь приведением некоторых фрагментов кода. Вот код обработчика события Click командной кнопки, ответственной за вызов метода поиска с барьером:
private void buttonBarierSearch_Click(object sender, EventArgs e)
{
int n = arr.Length - 1;
arr[n] = pattern; //барьер
int result;
result = Service<int>.SearchBarrier(arr, pattern);
if (result != n)
textBoxResult.Text = PATTERN_IS_FOUND + result;
else
textBoxResult.Text = PATTERN_IS_NOT_FOUND;
}
Нетрудно видеть, что в сравнении с консольным проектом единственное изменение при вызове метода поиска из класса Service<T> состоит в том, что передается другое значение параметра типа, поскольку поиск ведется в массиве целых чисел.
Рассмотрим теперь подробнее, как оценивается время, затрачиваемое различными методами на поиск образца в массиве. Для этой цели используется стандартный прием, неоднократно используемый в примерах этого курса. В классе Service<T> определяется функциональный тип:
public delegate int SearchMethod(T[] arr, T pattern);
Все рассматриваемые нами методы поиска являются экземплярами этого типа, поскольку их сигнатуры совпадают с сигнатурой, заданной делегатом SearchMethod. В класс Service<T> добавлен следующий метод:
public static long HowLong(SearchMethod search, int count,
T[] arr, T pattern)
{
DateTime start, finish;
start = DateTime.Now;
for(int i =0; i < count; i++)
search(arr,pattern);
finish = DateTime.Now;
return finish.Ticks - start.Ticks;
}
Метод HowLong позволяет оценить время работы метода, переданного в качестве первого аргумента. Это может быть любой метод, принадлежащий типу SearchMethod. Время здесь измеряется в тиках. Напомню, что один тик равен 100 наносекундам или 0.0001 миллисекунды.
Рассмотрим теперь, как вызывается метод HowLong в обработчике события соответствующей командной кнопки интерфейсного класса:
private void buttonBinSearchTime_Click(object sender, EventArgs e)
{
textBoxTimeBinSearch.Text = Service<int>.HowLong
(Service<int>.BinSearch, count, arr, pattern).ToString();
}
-
Задачи
-
44. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа double. Постройте консольный и Windows-проекты, использующие эти методы поиска. Получите оценки времени работы методов поиска.
-
45. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа StringBuilder. Постройте консольный и Windows-проекты, использующие эти методы поиска. Получите оценки времени работы методов поиска.
-
46. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа int. Постройте консольный и Windows-проекты, использующие эти методы поиска. Получите оценки времени работы методов поиска.
-
47. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа Person. Класс Person определите самостоятельно. Реализуйте возможность поиска по различным полям объекта (по имени, возрасту, адресу). Постройте Windows-проект, использующий эти методы поиска.
-
48. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа Point. Класс Point определите самостоятельно. Реализуйте возможность поиска по различным полям объекта (по декартовым координатам точки, по полярным координатам). Постройте Windows-проект, использующий эти методы поиска.
-
49. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа Account. Класс Account определите самостоятельно. Реализуйте возможность поиска по различным полям объекта (по номеру банковского счета, по размеру вклада). Постройте Windows-проект, использующий эти методы поиска.
-
50. На основе приведенного описания класса Service<T> создайте собственный универсальный класс, включающий различные варианты метода поиска. Создайте Windows-интерфейс для работы с этим классом по образцу интерфейса, приведенного на рис. 7.9.