Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Существуют и другие методы поиска элемента "John Smith" в нашем гипотетическом массиве. Например, если элементы в массиве отсортированы по фамилии, то можно воспользоваться алгоритмом бинарного поиска (binary search). Согласно ему, мы берем средний элемент массива. Это "John Smith"? Если да, то поиск закончен. Если элемент меньше чем "John Smith" (под "меньше" здесь понимается, что он стоит "раньше" в алфавитном порядке), то можно сказать, что искомый элемент находится во второй половине массива, если же он больше, то нужный нам элемент находится в первой половине массива. Далее операции повторяются (т.е. мы снова берем средний элемент
Такой алгоритм кажется более сложным, чем первый рассмотренный алгоритм. Последовательный поиск можно очень просто и удобно организовать с помощью цикла For, вызвав в нужный момент оператор Break. Бинарный поиск требует выполнения более сложный операций с локальными переменными. Таким образом, может показаться, что последовательный поиск быстрее только потому, что его реализация проще.
Что ж, добро пожаловать в мир анализа алгоритмов, в котором мы постоянно проводим эксперименты и пытаемся сформулировать законы работы различных алгоритмов!
Анализ алгоритмов
Рассмотрим два возможных варианта поиска в массиве элемента "John Smith": последовательный поиск и бинарный поиск. Мы напишем код для обоих вариантов, а затем определим производительность каждого из них. Реализация простого алгоритма последовательного поиска приведена в листинге 1.1.
Листинг 1.1. Последовательный поиск имени в массиве элементов
function SeqSearch( aStrs : PStringArray;
aCount : integer; const aName : string5): integer;
var
i : integer;
begin
for i := 0 to pred(aCount) do
if CompareText(aStrs^[i], aName) = 0 then begin
Result := i;
Exit;
end;
Result := -1;
end;
В листинге 1.2 содержится код более сложного бинарного поиска. (пока что мы не будем объяснять, что происходит в этом коде. Алгоритм бинарного поиска подробно рассматривается в главе 4.)
Очень трудно оценить быстродействие каждого из приведенных кодов только по самому их виду. Это основной принцип, которому мы должны всегда следовать: нельзя оценивать скорость работы кода по его виду. Единственным методом определения быстродействия должно быть его выполнение. И только. Если есть возможность выбирать между несколькими алгоритмами, как в рассматриваемом случае, то для выбора более эффективного алгоритма с нашей точки зрения нужно оценить время выполнения кода в различных условиях и на различных исходных данных.
Традиционно для оценки времени работы кода используется профилировщик (profiler). Профилировщик загружает тестируемое приложение и точно измеряет время выполнения отдельных подпрограмм. Профилировщик рекомендуется использовать во всех случаях. Только профилировщик поможет определить, на что тратится большая часть времени выполнения кода, а, следовательно, над какими подпрограммами стоит поработать с целью увеличения быстродействия всего приложения.
Листинг 1.2. Бинарный поиск имени в массиве элементов
function BinarySearch( aStrs : PStringArray;
aCount : integer; const aName : string5): integer;
var
L, R, M : integer;
CompareResult : integer;
begin
L := 0;
R := pred(aCount);
while (L <= R) do begin
M := (L + R) div 2;
CompareResult := CompareText(aStrs^[M], aName);
if (CompareResult = 0) then begin
Result := M;
Exit;
end
else
if (CompareResult < 0) then
L :=M + 1
else
R := M - 1;
end;
Result := -1;
end;
В компании TurboPower Software, где работает автор книги, используется профессиональный профилировщик из пакета Sleuth QA Suite. Все коды, приведенные в книге, были протестированы как с помощью StopWatch (название профилировщика из пакета Sleuth QA Suite), так и с помощью Code Watch (название отладчика использования ресурсов и утечки памяти из пакета Sleuth QA Suite). Тем не менее, даже если у вас нет своего профилировщика, вы можете проводить тестирование и определять время выполнения. Просто это не совсем удобно, поскольку в код приходится помещать вызовы функций работы со временем. Нормальные профилировщики не требуют внесения в код изменений, они оценивают время за счет изменения выполняемого файла в памяти компьютера непосредственно в процессе выполнения.
Для тестирования и определения времени выполнения алгоритмов поиска была написана специальная программа. Фактически она определяет системное время вначале перед, а затем и после выполнения кода. По результатам определения времени вычисляется время выполнения. Принимая во внимание, что в настоящее время компьютеры стали достаточно мощными, а часы системного времени характеризуются сравнительно низкой точностью, как правило, для более точной оценки быстродействия код выполняется несколько сот раз, а затем определяется среднее значение. (Кстати, эта программа была написана в среде 32-разрядной Delphi и не будет компилироваться под Delphi1, поскольку она выделяет память для массивов из кучи, которая превышает граничное для Delphi1 значение 64 Кб.)
Эксперименты по оценке быстродействия алгоритмов проводились различными способами. Сначала для обоих алгоритмов было определено время, необходимое для поиска фамилии "Smith" в массивах из 100, 1000, 10000 и 100000 элементов, которые содержали искомый элемент. В следующей серии экспериментов осуществлялся поиск того же элемента в массивах того же размера, но при отсутствии в них искомого элемента. Результаты экспериментов приведены в таблице 1.1.
Таблица 1.1. Времена выполнения последовательного и бинарного поиска
Как видно из таблицы, эксперименты показали очень интересные результаты. Время выполнения последовательного поиска пропорционально количеству элементов в массиве. Таким образом, можно сказать, что характеристики выполнения последовательного поиска линейны.
Результаты выполнения бинарного поиска проанализировать сложнее. Может даже показаться, что из-за очень быстрого выполнения алгоритма при определении времени мы столкнулись с проблемой потери точности. Очевидно, что зависимость между количеством элементов в массиве и временем выполнения алгоритма не является линейной. Но по приведенным данным трудно определить тип зависимости.