Комбинаторные алгоритмы для программистов



             

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


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

i

1 цикл: if z = xi then найдено if i = n then не найдено i
i + 1 goto цикл

За каждую итерацию выполняется до четырех команд: два сравнения, одна операция увеличения и одна передача управления.

Для ускорения внутреннего цикла общим приемом является добавление в таблицу специальных строк, которые делают необязательной явную проверку того, достиг ли указатель границ таблицы. Это можно сделать в алгоритме 13.1. Если перед поиском мы добавим искомое имя

z
в конце таблицы, то цикл всегда будет завершаться отысканием вхождения
z
; таким образом, нам не нужно в цикле каждый раз делать проверку
i = n
. В конце цикла проверка условия
i > n
, выполняемая лишь однажды, говорит о том, является ли найденное вхождение
z
истинным или специальным элементом таблицы. Это демонстрируется в алгоритме 13.2.

x_{n+1} \leftarrow z

i

1 while z
xi do i
i+1 if i
n then{найдено: i указывает на z} else{не найдено}


Алгоритм 13.2. Улучшенный последовательный поиск

Улучшение алгоритма 13.1 будет наиболее очевидным, если мы перепишем алгоритм 13.2 в тех же близких к языку машины обозначениях, которые использовались раньше:

 x_{n+1} \leftarrow z
i
1 цикл: if z = xi then goto возможно i
i+1 goto цикл возможно: if i
n then {найдено:i указывает на z} else{не найдено}

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

Печально то, что фокус с добавлением

z
в конец таблицы перед поиском удается, только если мы имеем прямой непосредственный доступ к концу таблицы. Это возможно, если таблица хранится в памяти с произвольным доступом, но невозможно в общем случае, когда используется связанное размещение или память с последовательным доступом.




Содержание  Назад  Вперед