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

Последовательный поиск в упорядоченной таблице

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

a[0].Кey < a[1].Кey <... < a[HighIndex].Кey, (10.3)

а для вторичных ключей условие упорядоченности выглядит как

a[0].Кey £ a[1].Кey £... £ a[HighIndex].Кey, (104)

Тогда последовательный просмотр ключей таблицы следует завершать при выполнении условия

ArgSearch £ a[i].Кey для первичных ключей, (10.5)

ArgSearch < a[i].Кey для вторичных ключей, (10.6)

где i - индекс первого встретившегося при последовательном просмотре ключа, для которого выполняется одно из приведенных условий.

В случае, когда поиск ведется по первичному ключу, выполнение строгого равенства в (10.5), т. е. когда ArgSearch = a[i].Кey, означает, что поиск завершается с результативным итогом, index = i. Если же выполняется условие ArgSearch < a[i].Кey, то поиск завершается, он неудачен (поскольку a[i+1].Кey, a[i+2].Кey, …, a[HighIndex].Кey заведомо больше ArgSearch), index = -1.

При поиске по вторичному ключу выполнение условия (10.6) приводит к останову алгоритма. Поскольку, согласно (10.4), при этом возможны совпадения аргумента поиска с несколькими значениями ключа (допустим число таких значений равно m), то записи a[i-m], a[i-m+1], …, a[i-1] являются искомыми записями и поиск – результативен. Если же совпадений до выполнения неравенства (10.6) не произошло, то завершившийся поиск неудачен. В любом случае значения a[i+1].Кey, a[i+2].Кey, …, a[HighIndex].Кey не проверяются на совпадение с аргументом ArgSearch, поскольку они заведомо больше ArgSearch.

Таким образом, последовательный поиск в упорядоченной по ключу таблице значительно эффективнее последовательного поиска в неупорядоченной таблице, поскольку при отсутствии в таблице значения (или значений) ключа, совпадающего с аргументом поиска, не следует просматривать все таблицу до конца (если, строго говоря, аргумент не превышает максимального значения ключа).

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

Пусть для значений ключа элементов таблицы выполняется одно из условий (10.3) или (10.4). Список запросов представляет собой набор аргументов поиска Arg[0], Arg[1], …, Arg[L]. Допустим, что массив запросов упорядочен таким же образом, как и таблица, т.е.

Arg[0] £ Arg[1] £... £ Arg[L], (10.7)

Тогда поиск при накоплении запросов целесообразно организовать следующим образом. Вначале в процедуру последовательного поиска передается в качестве аргумента значение Arg[0], и выполняется линейный поиск, начиная с записи a[0]. Допустим, что поиск для аргумента Arg[0] завершился на элементе a[i]. Следующим удовлетворяется запрос на поиск с аргументом Arg[1]. Поскольку, согласно (11.7), этот новый аргумент не меньше, чем предыдущий, не имеет смысла начинать поиск для него с элемента a[0], т. е. с начала таблицы. Последовательный поиск для аргумента Arg[1] начинается с элемента a[i] и, допустим, завершается на элементе a[j]. Новый поиск для следующего аргумента Arg[2] начинается с элемента a[j] и т. д.

Из-за простоты и эффективности последовательной обработки упорядоченной таблицы может иметь смысл отсортировать таблицу прежде, чем осуществлять в ней поиск. Это особенно справедливо для ситуации, описанной в предыдущем абзаце, где мы имели дело с некоторым «главным» файлом и с большим файлом «транзакций», состоящим из запросов.

Дата добавления: 2014-01-07