У меня молодой коллега, мой студент, основательно поучился сам по Потопахину и по "красной книжечке" и сразу как-то привык "любить ЦД".
Недавно вместе составляли кое-какие алгоритмы - и я по инерции начинал с вложенных циклов, а он сразу шёл от ЦД. И в итоге мы сравнили и оставили, за явным преимуществом, его варианты.
Привожу как примеры, где ЦД хорошо сработал.
Алгоритм 1. Мультипоиск. В последовательности байт найти первое вхождение какого-либо из искомых слов.
Код:
PROCEDURE MultiFind* (IN s: ARRAY OF BYTE; beg, end: INTEGER; wordCount: INTEGER; IN words: ARRAY OF ARRAY OF BYTE; IN lens: ARRAY OF INTEGER; OUT word, pos: INTEGER);
VAR i, w, wlen, j: INTEGER;
BEGIN
ASSERT(wordCount >= 1, 20);
i := beg; w := 0; wlen := lens[0]; j := 0;
LOOP IF (i + j < end) & (j < wlen) & (s[i + j] = words[w][j]) THEN
(* продолжаем сравнение с текущим словом *)
INC(j)
ELSIF (i + j < end) & (j < wlen) & (w < wordCount - 1) THEN
(* если нашли несовпадение с текущим словом и есть ещё слова *)
INC(w); wlen := lens[w]; j := 0
ELSIF (i + j < end) & (j < wlen) THEN
(* нашли несовпадение с последним словом *)
INC(i); w := 0; wlen := lens[0]; j := 0
ELSE EXIT END END;
IF j = wlen THEN
word := w; pos := i
ELSE
word := -1; pos := -1
END
END MultiFind;
Я попытался переписать без ЦД, чисто из любопытства, чтобы понять, почему не получается нормально без ЦД.
В этой задаче громоздкость возникает из-за того, что в (детерминированном!) ЦД мы можем выбирать порядок проверки условий, какой необходим, а при вложенных WHILE всегда сначала будет проверено условие внешнего цикла. Обратим внимание, что в нашем ЦД условия проверяются в порядке, обратном тому, в каком мы бы вкладывали циклы. Условие самой "быстрообращающейся" ветки поставлено первым.
Поэтому вложенные WHILE для данной задачи - громоздки. Приходится брать WHILE и REPEAT. Как, в частности, и было у Вирта в тех примерах, которые в редакции Фёдора Васильевича переделаны на ЦД. Видимо, вот она и одна из причин существования REPEAT в языке, в котором нет ЦД. Но вложенные циклы и с WHILE, и c REPEAT, особенно тройной вложенности - это уже... бр...
Алгоритм 2. В потоке данных (ридере к потоку) мы стоим после открывающего тега. Нужно найти соответствующий закрывающий тег (пропуская, разумеется, вложенные). В принципе, часто встречающаяся задача поиска соответствующей "скобки".
Код:
PROCEDURE FindCloseTag*(VAR fc: Data.FindContext; IN tag: ARRAY OF SHORTCHAR);
VAR words: ARRAY 2 OF ARRAY Data.maxWordLen OF BYTE;
lens: ARRAY 2 OF INTEGER;
depth: INTEGER;
res: INTEGER;
BEGIN
O2libData.StringToBytes('<' + tag, lens[0], words[0]);
O2libData.StringToBytes('</' + tag, lens[1], words[1]);
depth := 0;
Data.MultiFind(fc, 2, words, lens);
LOOP IF (fc.word = 0) THEN
INC(depth);
SkipTag(fc);
Data.MultiFind(fc, 2, words, lens)
ELSIF (fc.word = 1) & (depth > 0) THEN
DEC(depth);
SkipTag(fc);
Data.MultiFind(fc, 2, words, lens)
ELSE EXIT END END;
END FindCloseTag;
Data.FindContext = EXTENSIBLE RECORD
rd: Data.Reader;
len, read: LONGINT;
found: BOOLEAN;
word: INTEGER
END;
Вход
FAQ
Поиск
