Джулиан Бакнелл: Фундаментальные алгоритмы и структуры данных в Delphi

Существуют и другие методы поиска элемента "John Smith" в нашем гипотетическом массиве. Например, если элементы в массиве отсортированы по фамилии, то можно воспользоваться алгоритмом бинарного поиска (binary search). Согласно ему, мы берем средний элемент массива. Это "John Smith"? Если да, то поиск закончен. Если элемент меньше чем "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 Кб.)