Aлгоритм последовательного поиска в неупорядоченном словаре



Posted by Аркадий Водяник (195.206.226.15) on July 25, 2001 at 09:07:59:

В последнее время все о гигагерцах и гигабайтах думать приходится.
Уже и не понимаешь, чем занимался в то время, когда RAM = 48 Kb, а то и 16 Kb.

Спасибо Анатолию Антоновичу Анимице.
Он подарил мне второе издание трехтомника Д.Кнута "Искусство программирования".
До этого я книгу эту в институтской библиотеке брал (первое издание),
и за 15 лет (по формуляру) был ее вторым читателем :)

Хочу пересказать посетителям ПП кусочек однoй, на мой взгляд интересной главы;
я не буду придерживаться текста Д.Кнута, изложу задачу по-своему
в терминах ФБП.

Итак, задача:
а) словарь - это обычный (неассоциативный) массив, содержащий значения
- как числовые, так и строковые; эти значения никак не упорядочены;
б) исходя из а) - индексы в этом массиве - числа в диапазоне 1..999999
(ограничение массивов ФБП);
в) надо иметь процедуру, находящую последовательным поиском указанное ей значение в этом
словаре; понятно, чем быстрее, тем лучше;
c) в примерах ниже числа в словаре упорядочены - но мы никак не
используем этот факт, более того - будь они неупорядочены, ничего
не изменилось бы:

Решение 1:


* число N содержится в словаре, размер словаря: S
N=100000
S=200000
* заполнение словаря:
for i=1 to S [a i,i]; endfor
* собственно поиск:
i=1
:L
if [a i]=N printstr 'найдено в '+[intsn i]; goto final1; endif
i=i+1
if i <= S goto L; endif
неуспех
:final1

Решение 2: (слегка улучшенное)


* число N содержится в словаре, размер словаря: S
N=100000
S=200000
* заполнение словаря (слегка модифицированное):
for i=1 to S [a i,i]; endfor; [a S+1,N]
* собственно поиск:
i=1
:M
if [a i]=N if i < S+1 printstr 'найдено в '+[intsn i]; endif; goto final2; endif
i=i+1
goto M
:final2

Получается: Решение 2 превосходит Решение 1 в том, что добавляя
искомое N после словаря (в элемент массива, следующего за
последним элементом массива, относящемуся к словарю), мы можем
избавиться от строки:


if i <= S goto L; endif

Ведь теперь N мы найдем всегда - хоть есть N в словаре - хоть нет.
Такой прием экономит от 10 до 40% времени поиска - в зависимости
от языка программирования и степени оптимизации, установленной в
компиляторе.

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




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