Re: Aлгоритм поиска и китайская философия



Posted by Владимир Секретев (216.154.6.127) on July 25, 2001 at 12:12:49:

In Reply to: Aлгоритм последовательного поиска в неупорядоченном словаре posted by Аркадий Водяник on July 25, 2001 at 09:07:59:


Авторство этого алгоритма, вероятно, нужно приписать некоему древнему китайскому мудрецу, который сказал, что:

"Трудно искать черную кошку в темной комнате, особенно, если ее там нет."

Уважаемый г. Кнут творчески развил эту идею и предлагает сначала посадить в комнату кошку, а затем начинать ее искать, что, в соответствии с вышеизложенной мыслью, существенно облегчает решение задачи.


Однако приведенный Аркадием пример алгоритма мне не показался достаточно прозрачным и я решил поделиться своими соображениями:

1. Лучше хранить размер всего массива

SS = S + 1


В этом случае мы можем избавится от двух арифметических действий

S+1

немного улучшив скорость.

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

[a SS, N]

3. Не вполне очевидно, что появившейся дополнительный if

if i < S+1

будет выполнен только один раз, при наступлении условий успеха поиска.

Например, если эту строчку изложить в такой редакции:

if (a[i]=N) AND (i < S+1) then ...
(извините за паскалевский синтаксис)

то некоторые компиляторы при некоторых условиях сведут на нет всю оптимизацию.


4. Приведенный оптимизированный алгоритм ничего не скажет, если ничего не найдет.

Исходя из вышеизложенного, я бы переписал его так:


* число N содержится в словаре, размер словаря: S
* номер последнего элемента-заглушки: SS
N=100000
S=200000
SS = S + 1

* заполнение словаря:

for i=1 to S [a i,i]; endfor

* собственно поиск (модифицированный):

[a SS,N]
i=1
:M
if [a i]=N goto final2; endif
i=i+1
goto M

* Проверка результата поиска
:final2
if i < SS
printstr 'найдено в '+[intsn i];
else
неуспех
endif




Пpишедшие ответы: