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

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

Пусть для значений ключа элементов таблицы выполняется одно из условий (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] и т. д.

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