OberonCore
https://forum.oberoncore.ru/

Пара примеров на цикл Дейкстры
https://forum.oberoncore.ru/viewtopic.php?f=82&t=3770
Страница 1 из 3

Автор:  Илья Ермаков [ Четверг, 19 Январь, 2012 08:42 ]
Заголовок сообщения:  Пара примеров на цикл Дейкстры

У меня молодой коллега, мой студент, основательно поучился сам по Потопахину и по "красной книжечке" и сразу как-то привык "любить ЦД".
Недавно вместе составляли кое-какие алгоритмы - и я по инерции начинал с вложенных циклов, а он сразу шёл от ЦД. И в итоге мы сравнили и оставили, за явным преимуществом, его варианты.

Привожу как примеры, где ЦД хорошо сработал.

Алгоритм 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;

Автор:  Валерий Лаптев [ Четверг, 19 Январь, 2012 10:06 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Спасибо. Замечание насчет repeat - весьма ценно. Учтем в нашем языке.

Автор:  Info21 [ Четверг, 19 Январь, 2012 13:02 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Елы-палы. Оформляйте по-человечески. Чтобы сразу было ясно, о чем речь.

LOOP IF
...
END EXIT END END

Автор:  Сергей Губанов [ Четверг, 19 Январь, 2012 17:25 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Илья Ермаков писал(а):
Алгоритм 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;
Это же просто три вложенных линейных поиска совершенно не запутанных друг с другом. Вот смотрите:
Код:
PROCEDURE MultiFind* (IN source: ARRAY OF BYTE; begin, end, wordCount: INTEGER; IN words: ARRAY OF ARRAY OF BYTE; IN lens: ARRAY OF INTEGER; OUT word, pos: INTEGER);
  VAR w, j: INTEGER;
BEGIN word := -1; pos := -1;
  WHILE begin < end DO
    w := 0;
    WHILE w < wordCount DO
      IF (begin + lens[w] <= end) & (source[begin] = words[w][0]) THEN
        j := 1; (* это оптимизация: первую букву j=0 уже проверили в IF без организации тяжёлого WHILE *)
        WHILE (j < lens[w]) & (source[begin + j] = words[w][j]) DO INC(j) END;
        IF j = lens[w] THEN
          word := w; pos := begin; (* запоминаем ответ *)
          w := wordCount; begin := end (* симулируем EXIT *)
        END
      END;
      INC(w)
    END;
    INC(begin)
  END
END MultiFind;
Раз нет запутанности, то никакой "дейкстра" тут не нужен.

(модератор) Обсуждение оптимизации выделено в отдельную тему: viewtopic.php?f=86&t=3776

Автор:  Евгений Темиргалеев [ Четверг, 19 Январь, 2012 20:41 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Сергей Губанов писал(а):
Это же просто три вложенных линейных поиска совершенно не запутанных друг с другом....
ЦД, на мой взгляд, выглядит гораздо яснее.

Автор:  Илья Ермаков [ Пятница, 20 Январь, 2012 08:55 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

2 Сергей Губанов:

Я тоже составлял ваш вариант, когда мы сравнивали с коллегой. ЦД писал он.
Для меня наличие двух лишних IF стало весомым агрументом выкинуть мой вариант и оставить ЦД.
Вместо трёх рядом стоящих условий мы имеем пять, раскиданных по разным уровням.
Если вложенные циклы неоднородны (не какой-нибудь многомерный цикл), я вообще всегда стараюсь их выкидывать в отдельные процедуры, чтобы нормально понималось. Представьте, насколько упадёт быстродействие в Вашем-моём варианте, если я его структурирую по процедурам, как "душа просит" (модератор, см. viewtopic.php?f=86&t=3776).

Автор:  Сергей Губанов [ Пятница, 20 Январь, 2012 11:51 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Евгений Темиргалеев писал(а):
ЦД, на мой взгляд, выглядит гораздо яснее.
Здесь три вложенных линейных поиска совершенно не запутанных друг с другом. Цикл Дейкстры предназначен для описания запутанных циклов. Поскольку он сам запутанный, то запутанные циклы в него ложатся как 1:1, это хорошо. Однако не запутанные циклы будучи переписанными через формализм ЦД становятся тоже как бы запутанными. Это причиняет вред, вносит запутанность туда где её на самом деле нет.

Автор:  Валерий Лаптев [ Пятница, 20 Январь, 2012 12:03 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Евгений Темиргалеев писал(а):
Сергей Губанов писал(а):
Это же просто три вложенных линейных поиска совершенно не запутанных друг с другом....
ЦД, на мой взгляд, выглядит гораздо яснее.

+ 100
Я тоже подумал, что ЦД в некоторых задачах гораздо яснее выглядит.
Классика - алгоритм Евклдида.
Хотя, может быть, и не столь эффективен.

Автор:  Евгений Темиргалеев [ Пятница, 20 Январь, 2012 12:20 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Сергей Губанов писал(а):
Евгений Темиргалеев писал(а):
ЦД, на мой взгляд, выглядит гораздо яснее.
Здесь три вложенных линейных поиска совершенно не запутанных друг с другом. ... Однако не запутанные циклы будучи переписанными через формализм ЦД становятся тоже как бы запутанными. Это причиняет вред, вносит запутанность туда где её на самом деле нет.
Сергей, "на мой взгляд" значит, что для меня вложенные линейные поиски выглядят более запутаными. Как говорится, "На вкус и цвет, товарища нет". :)

А в общем, чего спорить?

ЦД --- более универсальная "конструкция", которая позволяет формально строить алгоритмы. Поэтому учить строить алгоритмы надо с её использованием. Это самое главное.

Оптимизации (в данном случае "распутывание") --- тоже нужно учить, но после, отдельным спец. курсом.

Автор:  Сергей Губанов [ Пятница, 20 Январь, 2012 12:47 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Евгений Темиргалеев писал(а):
ЦД --- более универсальная "конструкция", которая позволяет формально строить алгоритмы. Поэтому учить строить алгоритмы надо с её использованием. Это самое главное.
Категорически нет. Цикл Дейкстры запутывает то, что запутанным не является. В этом он вреден. Цикл Дейстры полезен для описания того, что и так само по себе запутано, то есть для экзотики, в обычной программистской практике это 1% случаев или меньше, как раз чтобы закрыть вопрос "в исключительных случаях нужном" goto. Запутанную задачу goto решает запутанно, то есть 1:1, но незапутанную задачу goto тоже решает запутанно, в этом его вред как и ЦД.

Автор:  Info21 [ Пятница, 20 Январь, 2012 13:32 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Сообщение сюда даже больше относится, чем туда, поэтому ставлю ссылочку:

viewtopic.php?f=80&t=1710&p=69722#p69722

Автор:  Евгений Темиргалеев [ Суббота, 21 Январь, 2012 07:01 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Сергей Губанов писал(а):
Евгений Темиргалеев писал(а):
ЦД --- более универсальная "конструкция", которая позволяет формально строить алгоритмы. Поэтому учить строить алгоритмы надо с её использованием. Это самое главное.
Категорически нет. Цикл Дейкстры запутывает то, что запутанным не является... Запутанную задачу goto решает запутанно, то есть 1:1, но незапутанную задачу goto тоже решает запутанно, в этом его вред как и ЦД.
Суть в контексте этого форума: решение с ЦД формально проверяемо, с goto --- нет, поэтому Ваше обоснование "запутывает" т. о. некорректно. (viewtopic.php?p=69722#p69722)

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

Автор:  Евгений Темиргалеев [ Суббота, 21 Январь, 2012 07:51 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Тема разделена, оптимизация решения с ЦД см: viewtopic.php?f=86&t=3776

Автор:  Peter Almazov [ Суббота, 21 Январь, 2012 09:20 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Илья Ермаков писал(а):
Привожу как примеры, где ЦД хорошо сработал.
После осмысленного синтеза и оптимизации алгоритма 1 получилось два варианта на выбор. Лишних сравнений нет, ЦД тоже нет. Мне больше нравится второй, хотя он и подлиннее. Не тестировал.
Код:
WHILE (i + j < end) & (j < wlen) DO
  IF (s[i + j] = words[w][j]) THEN
    INC(j)
  ELSIF (w = wordCount - 1) THEN
    (* дальше нельзя увеличивать w *)
    INC(i); w := 0; wlen := lens[0]; j := 0
  ELSE
     INC(w); wlen := lens[w]; j := 0
  END;
END;
---------------------------------------------
WHILE (i + j < end) & (j < wlen) DO
  IF (s[i + j] = words[w][j]) THEN
    INC(j)
  ELSE
    INC(w);
    IF (w = wordCount) THEN
      INC(i); w := 0; wlen := lens[0]; j := 0
    ELSE
       INC(w); wlen := lens[w]; j := 0
    END;
  END;
END;
Теоретически эти варианты можно было сразу вывести из первоначального, но это стало ясно (мне) только в конце.

Автор:  Илья Ермаков [ Суббота, 21 Январь, 2012 13:08 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Да, отличный "вынос за скобки", я что-то просмотрел такую возможность. Решение Ваше всё равно той же структуры, что и чистый ЦД, со всеми его плюсами. Без вложенных циклов. В общем-то, тот же принцип избавления от вложенности, что и при обходе многомерного массива одним циклом :)

Автор:  Valery Solovey [ Воскресенье, 22 Январь, 2012 18:45 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Сергей Губанов писал(а):
Евгений Темиргалеев писал(а):
ЦД, на мой взгляд, выглядит гораздо яснее.
Здесь три вложенных линейных поиска совершенно не запутанных друг с другом. Цикл Дейкстры предназначен для описания запутанных циклов. Поскольку он сам запутанный, то запутанные циклы в него ложатся как 1:1, это хорошо. Однако не запутанные циклы будучи переписанными через формализм ЦД становятся тоже как бы запутанными. Это причиняет вред, вносит запутанность туда где её на самом деле нет.

На самом деле, обычные циклы - это и есть ЦД. Частный случай : ). Но с другой стороны, говоря "запутанный", Вы имеете в виду "сильно связанный". Если призадуматься, то циклы и ветвления введены в языки программирования по причине наличия соответствующих неделимых сущностей.

Если попытаться разделить многоветочный ЦД, то будут нарушены и потеряны некоторые связи. И полученный результат в лучшем случае будет решать частный случай исходной задачи.

А при чтении искусственно привнесённого ЦД читающему могут привидиться лишние связи, которых там нет.

Автор:  Info21 [ Понедельник, 04 Июнь, 2012 20:00 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Некто vlad задал задачку: найти первую пару идущих подряд нулей.
Сказав, что цикл нестандартный.

Позор нашему тут коллеге, не сумевшему сразу, на инстинкте написать простенький цикл Дейкстры.

Нестандартный цикл >> цикл Дейкстры.

Приводимый код написан для поиска в массиве.
Легко меняется на поиск в последовательности.

Код пишется автоматом по постусловию (i >= LEN(a)) OR oneZero & (a[i] = 0)

Код:
      i := 0;
      oneZero := FALSE;
      LOOP IF (i < LEN(a)) & ~oneZero THEN
         oneZero := a[i] = 0;
         INC(i);
      ELSIF (i < LEN(a)) & (a[i] # 0) THEN
         oneZero := FALSE;
         INC(i);
      ELSE EXIT END END;
      
      IF i < LEN(a) THEN (*эквивалентное упрощение: albobin*)
         Log.String("нашли: ");  Log.Int( i-1 );  Log.Ln;
      ELSE
         Log.String("не нашли");  Log.Ln;
      END;

Раздел 1.9 новых Алгоритмов ... прочесть в любом случае невредно.

Автор:  Александр Шостак [ Понедельник, 04 Июнь, 2012 21:28 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Код:
NumZeroes := 0;
Success   := FALSE;
i         := 0;

WHILE (i < LEN(a)) & ~Success DO
  IF a[i] = 0 THEN
    INC(NumZeroes);
    Success := NumZeroes = 2;
  ELSE
    NumZeroes := 0;
  END;

 INC(i);
END;

Автор:  Info21 [ Понедельник, 04 Июнь, 2012 21:35 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Александр Шостак писал(а):
Код:
NumZeroes := 0;
Success   := FALSE;
Теперь осталось устранить переменную Success :)

Считаю Ваше решение практически эквивалентным моему:
цикл и вложенный IF + (у Вас) небольшая оптимизация.

Автор:  Info21 [ Понедельник, 04 Июнь, 2012 21:41 ]
Заголовок сообщения:  Re: Пара примеров на цикл Дейкстры

Чтобы не казалось, что мой вариант сложнее, перепишу на Обероне-07, где ЦД есть явно:
Код:
      i := 0;
      oneZero := FALSE;
      WHILE (i < LEN(a)) & ~oneZero DO
         oneZero := a[i] = 0;
         INC(i);
      ELSIF (i < LEN(a)) & (a[i] # 0) DO
         oneZero := FALSE;
         INC(i);
      END;

Строк в цикле, между прочим, здесь 7 против 9 :)

Ваш, правда, общее. Как раз на две строчки :)

Страница 1 из 3 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/