OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 21 Сентябрь, 2017 20:57

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 75 ]  На страницу Пред.  1, 2, 3, 4
Автор Сообщение
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Четверг, 21 Апрель, 2011 09:53 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2284
Откуда: Россия, Санкт-Петербург
Разбирал очередной LOOP, увидел вот что. Не только выход из LOOP с помощью RETURN, но и выход из FOR c помощью EXIT.
Код:
   d := 0; i := 0;
   LOOP
      IF d = LEN (array, 1) THEN
         RETURN FALSE
      END;
      FOR i := 0 TO LEN (array, 0) - 1 DO
         PrepareForCheck1 (array [d, i]);
         IF Check1 (array [d, i]) THEN
            EXIT
         END;
         PrepareForCheck2 (array [d, i]);
         IF Check2 (array [d, i]) THEN
            EXIT
         END;
      END; (* for i *)
      INC (d);
   END; (* loop *)
   HandleSuccess ();
   RETURN TRUE

Первым делом объединил процедуры PrepareForCheckN с CheckN, чтобы можно было целиком поставить в IF (побочных эффектов у них не было).
Код:
   d := 0; i := 0;
   LOOP
      IF d = LEN (array, 1) THEN
         RETURN FALSE
      END;
      FOR i := 0 TO LEN (array, 0) - 1 DO
         IF PrepareAndCheck1 (array [d, i]) THEN
            EXIT
         END;
         IF PrepareAndCheck2 (array [d, i]) THEN
            EXIT
         END;
      END; (* for i *)
      INC (d);
   END; (* loop *)
   HandleSuccess ();
   RETURN TRUE

Уже видно, что внутри FOR условия можно объединить с помощью OR, а сам FOR при этом легко превращается в обычный поисковый WHILE. По сути EXIT из FOR - это успешное завершение поиска, которое надо сигнализировать за пределы LOOP. Заводим для этого переменную res: BOOLEAN:
Код:
   res := FALSE; d := 0;
   WHILE (d < LEN (array, 1)) & ~res DO
      i := 0;
      WHILE (i < LEN (array, 0)) & ~res DO
         res := PrepareAndCheck1 (array [d, i]) OR PrepareAndCheck2 (array [d, i]);
         INC (i);
      END; (* while i *)
      INC (d);
   END; (* while d *)
   IF res THEN
      HandleSuccess ();
   END;
   RETURN res

Значения i и d не используются в HandleSuccess. Если бы использовались, то надо было бы их уменьшить на 1 при успешном завершении поиска.
Итого, устранены три преждевременных выхода из циклов, добавлена одна локальная переменная, исходник уложился в понятный шаблон и стал короче на 6 строк (правда, пришлось написать вспомогательную процедуру, но она пригодилась ещё раз для усмирения аналогичного LOOP'а в том же модуле).

Кстати, сравните приведённый выше код вот с этим:
Код:
   res := FALSE; d := 0;
   WHILE (d < LEN (array, 1)) & ~res DO
      i := 0;
      WHILE (i < LEN (array, 0)) & ~(PrepareAndCheck1 (array [d, i]) OR PrepareAndCheck2 (array [d, i])) DO
         INC (i);
      END; (* while i *)
      res := ~(i < LEN (array, 0));
      INC (d);
   END; (* while d *)
   IF res THEN
      HandleSuccess ();
   END;
   RETURN res

В последнем варианте присвоение res вынесено за цикл, а искомое условие записано в условии цикла. Хотя этот вариант более каноничен, мне всё же препоследний кажется более читабельным из-за явного присвоения res и явного визуального сходства двух WHILE.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Четверг, 21 Апрель, 2011 13:17 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 524
Откуда: Москва
Если я правильно понял, то эти переработки не эквивалентны оригиналу. В нем HandleSuccess () вызывается всегда, там сплошной Success :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Четверг, 21 Апрель, 2011 13:53 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4392
Откуда: Россия, Орёл
Peter Almazov писал(а):
Если я правильно понял, то эти переработки не эквивалентны оригиналу. В нем HandleSuccess () вызывается всегда, там сплошной Success :)
Не всегда --- в теле цикла RETURN


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Четверг, 21 Апрель, 2011 13:56 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8781
Откуда: Россия, Орёл
Вот ещё прекрасный пример, за что "прыгунов" "убивать" надо - потом нормальный человек видит в конце процедуры какое-то действие и резонно предполагает, что оно выполняется всегда.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Пятница, 22 Апрель, 2011 12:16 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 524
Откуда: Москва
Вообще, если обе проверки слить в одну, то будет наглядно видно, что это классический поиск в двумерном массиве.
Странно, что Info21 не предложил использовать цикл Дейкстры :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Понедельник, 25 Апрель, 2011 16:45 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2284
Откуда: Россия, Санкт-Петербург
Ужас, летящий на крыльях ночи.
Код:
PROCEDURE CheckAll (flag: BOOLEAN);
VAR
   done: BOOLEAN;
   fc: SHORTINT;
BEGIN
   IF SomeCondition () THEN
      fc := 0;
   ELSE
      fc := 2;
   END;
   done := FALSE;
   LOOP
      IF FirstObject () THEN
         REPEAT
            IF fc = 2 THEN
               IF SomeCheck () THEN DEC (fc) END;
            ELSIF (fc = 1) & SomeCheck () THEN
               EXIT
            ELSIF AccessCheck () THEN
               done := DoSomething (flag);
            END;
         UNTIL done OR ~NextObject ();
         DEC (fc);
      ELSE
         EXIT
      END; (* if FirstObject *)
      IF fc < 0 THEN
         EXIT
      END;
   END; (* loop *)
END CheckAll;
Задача - выяснить, в каких отношениях состоят проверки SomeCondition, SomeCheck и переменная fc, после чего упростить код.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Понедельник, 25 Апрель, 2011 17:02 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4392
Откуда: Россия, Орёл
Александр Ильин писал(а):
Код:
   IF SomeCondition () THEN
      fc := 0;
   ELSE
      fc := 2;
   END;
Задача - выяснить, в каких отношениях состоят проверки SomeCondition, SomeCheck и переменная fc, после чего упростить код.
Предлагаю для начала выписать две версии процедуры --- для fc = 0 и fc = 2.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Понедельник, 25 Апрель, 2011 18:17 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1508
Откуда: Беларусь, Минск
Тут сложно что-то онветить. Непонятно, какие процедуры используют элементы из последовательности (NextObject).

fc - это состояние конечного автомата.
SomeCondition - это переход с состояния, находящегося на более высоком уровне.
SomeCheck - это переход между состояниями на этом уровне.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Понедельник, 25 Апрель, 2011 18:27 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2284
Откуда: Россия, Санкт-Петербург
Valery Solovey писал(а):
Тут сложно что-то онветить. Непонятно, какие процедуры используют элементы из последовательности (NextObject).
FirstObject-NextObject - результаты их работы используются всеми процедурами, кроме SomeCondition. Т.е. SomeCheck, AccessCheck и DoSomething - все, кто находится внутри REPEAT..UNTIL, работают с очередным объектом.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Понедельник, 25 Апрель, 2011 18:40 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1508
Откуда: Беларусь, Минск
а FirstObject возвращает к началу последовательности или выдаёт FALSE при повторном обращении?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Понедельник, 25 Апрель, 2011 18:54 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2284
Откуда: Россия, Санкт-Петербург
Valery Solovey писал(а):
а FirstObject возвращает к началу последовательности или выдаёт FALSE при повторном обращении?
Возвращает к началу. FALSE возвращает только если вообще нету объектов для обработки (пустой список).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Понедельник, 25 Апрель, 2011 20:58 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1508
Откуда: Беларусь, Минск
Стало больше, чем было.

Код:
PROCEDURE CheckAll (flag: BOOLEAN);
VAR
   done: BOOLEAN;
   objNotNil, twinsFound : BOOLEAN;
BEGIN
   objNotNil := FirstObject();
   IF objNotNil THEN
      IF SomeCondition() THEN (* fc = 0 *)
         (*done := AccessCheck() & DoSomething(flag); (* DoSomething не добавляет элементы в последовательность? *)
         WHILE ~done & NextObject() DO done := AccessCheck() & DoSomething(flag) END*)
         WHILE ~(AccessCheck() & DoSomething(flag)) & NextObject() DO END
      ELSE (* fc = 2 *)
         WHILE objNotNil & ~SomeCheck() DO objNotNil := NextObject() END;
         IF ~objNotNil THEN (* SomeCheck не нашёл ничего с первого раза - не найдёт и со второго. Поэтому сразу копируем сюда то же, что выполняется для fc = 0 *)
            objNotNil := FirstObject();
            WHILE ~(AccessCheck() & DoSomething(flag)) & NextObject() DO END
         ELSE (* SomeCheck пытается повторить удачу *)
            twinsFound := FALSE;
            done := FALSE;
            (* цикл ниже не будет работать как исходный пример, если хвост очереди < 2. В исходном примере при хвосте = 1 последовательность завернётся на начало, и SomeCheck снова найдёт тот же объект, что и на предыдущем проходе по последовательности. Так и надо? *)
            WHILE ~twinsFound & ~done & NextObject() DO
               twinsFound := SomeCheck();
               (*IF ~twinsFound & AccessCheck() THEN done := DoSomething(flag) END;*)
               done := ~twinsFound & AccessCheck() & DoSomething(flag)
            END
         END
      END
   END
END CheckAll;


P.S. Не проверял.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Воскресенье, 01 Май, 2011 06:40 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2284
Откуда: Россия, Санкт-Петербург
Valery Solovey писал(а):
Стало больше, чем было.
Понятно, что станет больше. Это нормально. Здесь проблема как раз в чрезмерной оптимизации. По-хорошему, к такому коду надо комментарий на полстраницы, а тут ни строчки не было.

DoSomething ничего в последовательность не добавляет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Четверг, 05 Май, 2011 09:48 
Аватара пользователя

Зарегистрирован: Пятница, 25 Сентябрь, 2009 13:10
Сообщения: 1155
Откуда: Tel-Aviv
Полезно было бы привести теорию оптимальности циклов на графах переходов состояний и показывать на них что излишне и почему.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Убираю LOOP'ы
СообщениеДобавлено: Четверг, 05 Май, 2011 12:47 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1508
Откуда: Беларусь, Минск
Думаю, здесь цикл завёрнут не на состояния. Там, где цикл можно привязать к состояниям, обычно по-другому делать будет менее рационально.

Здесь цикл завёрнут на вызов NextObject: вместо трёх идущих друг за другом действий, каждое из которых обращается к последовательности (выполняет независимый вызов следующего объекта), было объявлено только одно место вызова NextObject, а всё остальное построили вокруг этой операции. То ли решили таким образом соптимизировать что-то, то ли боялись, что при написании кода забудут своевременно добавить вызов процедуры.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 75 ]  На страницу Пред.  1, 2, 3, 4

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2017, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB