Последовательный поиск

Последовательный поиск

Теперь, когда мы определились с функцией сравнения, можно перейти к рассмотрению алгоритмов поиска элемента в массивах и связных списках.

Массивы

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

Если массив не отсортирован, для поиска определенного элемента может использоваться только один единственный алгоритм: выбирать каждый элемент массива и сравнивать его с искомым. Как правило, такой алгоритм реализуется с помощью цикла For. В качестве примера давайте выполним поиск значения 42 в массиве из 100 целых чисел:

var

MyArray : array[0..99] of integer;

Inx : integer;

begin

for Inx := 0 to 99 do

if MyArray[Inx] = 42 then

Break;

if (Inx = 100) then

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

else

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

Довольно просто, не правда ли? Код выполняет цикл по всем элементам массива, начиная с первого и заканчивая последним, используя Break для выхода из цикла при обнаружении первого элемента, значение которого равно искомому 42. (Оператор Break очень удобно использовать, здесь он ничем не отличается от оператора goto.) После цикла, для того чтобы определить, найден ли элемент, проверяется значение счетчика цикла Inx.

Интересно, сколько читателей в приведенном выше коде нашли ошибку? Проблема заключается в том, что в языке Object Pascal при успешном завершении цикла значение переменной цикла будет не определено. С другой стороны, в случае преждевременного завершения цикла, скажем, с помощью оператора Break, значение переменной цикла будет определено.

В коде предполагается, что перемененная цикла Inx после завершения цикла будет на 1 больше конечного значения для цикла For, даже если цикл будет выполнен успешно. Оказывается, что в 32-разрядных компиляторах (в версиях Delphi от 2 до 7) ошибки не возникает: значение переменной цикла после завершения цикла будет на 1 больше, чем при последнем выполнении цикла. В Delphi 1 код будет работать неправильно: после завершения выполнения цикла переменная цикла будет содержать значение, равное своему значению при последнем выполнении цикла (в нашем примере Inx после полного выполнения цикла будет содержать 99). Кто знает, что будет в следующих версиях Delphi? Вполне возможно, что в будущих версиях Delphi будет изменен оптимизатор компилятора, и переменная цикла после завершения цикла будет получать другое значение. В конце концов, разработчики, описав поведение переменной цикла, оставили за собой право изменения ее значения после выхода из цикла.

Тогда каким образом можно реализовать алгоритм последовательного поиска? Цикл For можно использовать (это самый быстрый метод организации последовательного поиска), однако потребуется ввести флаг, который будет указывать, найден ли искомый элемент. Код несколько усложнится, но зато становится корректным с точки зрения языка программирования:

var

MyArray : array[0..99] of integer;

Inx : integer;

FoundIt : boolean;

begin

FoundIt := false;

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 сравнений). Единственным ее преимуществом перед предыдущей функцией является то, что при отсутствии искомого элемента в массиве результат будет получен быстрее. Скоро мы рассмотрим алгоритм бинарного поиска, который позволит повысить быстродействие в обоих случаях.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Поиск

Из книги автора

Поиск Элемент input со значением “search” в атрибуте type будет вести себя примерно так же, как элемент ввода со значением “text” атрибута type:<label for="query">Поиск</label><input id="query" name="query" type="search">Единственная разница между “text” и “search” состоит в том, что браузер может


Поиск

Из книги автора

Поиск Поскольку каналы, на которые вы подписаны, в некотором роде являются вашей базой знаний, в ней нужно уметь эффективно ориентироваться – упорядочивать новости по типам, выделять запомнившиеся сообщения, искать нужные записи. Для этого Reader предлагает сразу


Поиск

Из книги автора

Поиск С количеством фотографий, производимых современными обладателями цифровиков, работа по разбору и классификации фотографий превращается в нетривиальное занятие: легкость съемки и дешевизна карт памяти привела к тому, что мы практически не удаляем снимки, даже


30.4. Последовательный сервер TCP

Из книги автора

30.4. Последовательный сервер TCP Последовательный сервер TCP полностью обрабатывает запрос каждого клиента, прежде чем перейти к следующему клиенту. Последовательные серверы редко используются, но один из них, простой сервер времени и даты, мы показали в листинге 1.5.Тем не


Поиск на научных сайтах с использованием платформы Flexum «Поиск по научным сайтам»

Из книги автора

Поиск на научных сайтах с использованием платформы Flexum «Поиск по научным сайтам» Тема научного поиска не прошла мимо разработчиков персональных поисковиков. Подробному рассказу о возможностях таких поисковых систем посвящена отдельная глава нашей книги (см. главу 6).


RSS-поиск

Из книги автора

RSS-поиск Пополнять список своего RSS-агрегатора можно различными способами. Первый и наиболее распространенный – простой поиск сайтов по интересующим темам, а затем подписка на их RSS-ленты, если, конечно таковые имеются. Способ несложный, однако на редкость медленный и


Поиск

Из книги автора

Поиск Классический видЧтобы использовать классический вид поиска файлов без анимированного персонажа, то присвойте строковому параметру Use Search Asst значение no в разделе HKCUSoftwareMicrosoftWindowsCurrentVersionExplorerCabinetStateОчистка истории раннее вводимых словЕсли вы часто пользуетесь


Поиск

Из книги автора

Поиск Строка поискаЧтобы скрыть строку поиска из IE7, в разделе HKCUSoftwarePoliciesMicrosoftInternet ExplorerInfoDeliveryRestrictionsсоздайте параметр типа DWORD ·NoSearchBox· со значением 1. Перезапустите IE7, чтобы изменения вступили в силу. Кнопка Поиск (IE6)Чтобы изменить адрес поисковика, который у вас


Поиск

Из книги автора

Поиск На всех страницах сайта обязательно должно быть поле для поиска товаров. Удивительно, но в некоторых интернет-магазинах отсутствует поддержка поиска по сайту. Убедитесь, что на вашем сайте есть поиск. Более того, сделайте функцию поиска максимально заметной. Чаще


Последовательный резонанс

Из книги автора

Последовательный резонанс В предыдущем примере значения L и C были выбраны такими, чтобы обеспечить резонанс на частоте f=1 кГц. Во многих схемах резонансная частота неизвестна, и ее необходимо определить при анализе схемы. Создайте в Capture схему, подобную приведенной на


2.4.5.2. Последовательный файл регистрации Falcon

Из книги автора

2.4.5.2. Последовательный файл регистрации Falcon Falcon использует последовательный файл регистрации, чтобы сохранить некоторые типы информации до того, как данные окончательно сохранятся в базе данных. Файл регистрации используется, чтобы сохранить следующие типы


Яндекс. Поиск – быстрый поиск документов

Из книги автора

Яндекс. Поиск – быстрый поиск документов Документы, как известно, имеют премерзкое свойство накапливаться. И чем больше документов, тем труднее в их залежах найти нужный. Электронные документы здесь не слишком отличаются от бумажных. Проблема места для хранения, правда,


6.4. Как определить последовательный контейнер?

Из книги автора

6.4. Как определить последовательный контейнер? Для того чтобы определить объект контейнерного типа, необходимо сначала включить соответствующий заголовочный файл:#include vector#inclnde list#include deque#include map#include setОпределение контейнера начинается именем его типа, за которым в


Поиск

Из книги автора

Поиск Управление отображением команды Поиск, которая также по умолчанию входит в состав меню кнопки Пуск, осуществляется в системном реестре в разделе HKEY_CURRENT_USERSoftwareMicrosoftWindowsCurrentVersionPoliciesExplorer с помощью REG_DWORD-параметра NoFind. Чтобы удалить данную функцию, следует присвоить


Глава 12 Поиск с предпочтением: эвристический поиск

Из книги автора

Глава 12 Поиск с предпочтением: эвристический поиск Поиск в графах при решении задач, как правило, невозможен без решения проблемы комбинаторной сложности, возникающей из-за быстрого роста числа альтернатив. Эффективным средством борьбы с этим служит эвристический