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

Бакнелл Джулиан М.

for Inx := 0 to 99 do

if MyArray[Inx] = 42 then begin

FoundIt := true;

Break;

end;

if not FoundIt then

.. значение 42 не было найдено ..

else

.. значение 42 было найдено в элементе с индексом Inx ..

А теперь рассмотрим функцию поиска элемента в массиве TList с помощью функции сравнения (ее реализацию можно найти в файле TDTList.pas на Web-сайте издательства, в разделе сопровождающих материалов). Если искомый элемент не найден, функция возвращает -1, в противном случае возвращается индекс элемента.

Листинг 4.5. Последовательный

поиск в несортированном массиве TList

function TDTListIndexOf(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

Inx : integer;

begin

for Inx := 0 to pred(aList.Count) do

if (aCompare(aList.List^[Inx], aItem) = 0) then begin

Result := Inx;

Exit;

end;

{если мы попали сюда, значит искомый элемент не найден}

Result := -1;

end;

Эта функция работает не так как метод TList.IndexOf, который предназначен для поиска элемента в массиве путем сравнения значений указателей. Фактически он в своем внутреннем списке указателей осуществляет поиск элемента как указателя. С другой стороны, функция TDTListIndexOf осуществляет поиск самого элемента, вызывая для сравнения искомого и текущего элемента функцию сравнения. Функция сравнения может сравнивать просто значения указателей или преобразовывать указатели во что-нибудь более значимое, например, в класс или запись, а затем сравнивать поля.

Обратите внимание, что в реализации функции с целью повышения эффективности применяется небольшая хитрость. Вместо сравнения aItem с aList[Inx] выполняется сравнение с aList.List^[Inx]. Зачем? Компилятор преобразовывает первое сравнение в вызов функции, а затем вызываемая функция, TList.Get, перед возвратом указателя из внутреннего массива указателей проверяет переданный ей индекс на предмет попадания в диапазон от 0 до количества элементов (вызывая исключение, если условие не соблюдается). Но мы знаем, что индекс находится в требуемом диапазоне, поскольку используется цикл от 0 до количества элементов минус 1. Поэтому нам не нужно считывать значение свойства Items и вызывать метод TList.Get. Можно получить доступ непосредственно к массиву указателей (свойство List экземпляра TList).

– ----

Эта хитрость (использование свойства List экземпляра TList) вполне корректна. Если вы уверены, что значения индекса не выходят за пределы допустимого диапазона, можно исключить проверку на предмет попадания в диапазон за счет непосредственного доступа к массиву ListItems. Тем не менее, ее применение при итерации по массиву TList или в коде, который может привести к выходу индекса за пределы допустимого диапазона, не желательно. Лучше обезопасить себя, нежели потом сожалеть.

– ----

В классе TtdRecordList (который описан в главе 2) для организации последовательного поиска можно пользоваться методом IndexOf (см. листинг 4.6).

Листинг 4.6. Последовательный поиск с помощью метода TtdRecordList.IndexOf

function TtdRecordList.IndexOf(aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

ElementPtr : PAnsiChar;

i : integer;

begin

ElementPtr := FArray;

for i := 0 to pred(Count) do begin

if (aCompare(aItem, ElementPtr) = 0) then begin

Result := i;

Exit;

end;

inc(ElementPtr, FElementSize);

end;

Result := -1;

end;

Как

видите, время выполнения алгоритма последовательного поиска напрямую зависит от количества элементов в массиве. В лучшем случае мы можем найти требуемый элемент с первой попытки (если он будет первым в массиве), но вполне вероятно, что мы обнаружим его в самом конце, после просмотра всех элементов. В среднем для массива размером n для обнаружения искомого элемента придется пройти n/2 элементов. В любом случае, если искомого элемента нет в массиве, будут просмотрены все n элементов. Таким образом, операция последовательного поиска принадлежит к классу O(n).

А что можно сказать о сортированном массиве? Первое, что следует отметить, - простой алгоритм последовательного поиска в отсортированном массиве будет работать ничуть не хуже (или не лучше, в зависимости от вашей точки зрения), чем в несортированном. Операция поиска будет принадлежать к классу O(n).

Тем не менее, алгоритм поиска можно улучшить. Если искомого элемента нет в массиве, поиск можно выполнить намного быстрее. Фактически мы выполняем итерации по массиву, как и раньше, но теперь только до тех пор, пока не будет найден элемент, больший или равный искомому. Если обнаружен элемент, равный искомому, поиск завершается успешно. Если же обнаружен элемент больше искомого, значит, искомый элемент в массиве отсутствует, поскольку массив отсортирован, а мы дошли до элемента большего, чем искомый. Все последующие элементы также будут больше искомого. Следовательно, поиск можно прекратить.

Листинг 4.7. Последовательный поиск в отсортированном массиве TList

function TDTListSortedIndexOf(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

Inx, CompareResult : integer;

begin

{искать первый элемент больший или равный элементу aItem}

for Inx := 0 to pred(aList.Count) do begin

CompareResult := aCompare(aList.List^[Inx], aItem);

if (CompareResult >= 0) then begin

if (CompareResult = 0) then

Result := Inx

else

Result := -1;

Exit;

end;

end;

{если мы попали сюда, значит искомый элемент не найден}

Result := -1;

end;

Обратите внимание, что функция сравнения вызывается только один раз при каждом выполнении цикла. Мы не знаем, что делает функция aCompare - для нас это "черный ящик". Следовательно, желательно ее вызывать как можно реже. Поэтому при каждом выполнении цикла мы вызываем ее только один раз и сохраняем полученный результат в переменной целого типа. После этого переменную можно использовать сколько угодно раз, не вызывая функцию.

Как уже говорилось, приведенная функция поиска нисколько не увеличивает скорость обнаружения искомого элемента, если искомый элемент присутствует в массиве (в среднем, как и ранее, для этого потребуется провести n/2 сравнений). Единственным ее преимуществом перед предыдущей функцией является то, что при отсутствии искомого элемента в массиве результат будет получен быстрее. Скоро мы рассмотрим алгоритм бинарного поиска, который позволит повысить быстродействие в обоих случаях.