OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 15:44

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




Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9  След.
Автор Сообщение
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 22 Январь, 2009 16:30 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Для тех, кто "тык-мыкает", будет постоянный соблазн вкрутить лишний EXIT вместо думания над совокупностью условий.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Пятница, 23 Январь, 2009 08:15 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1053
Откуда: Россия, Чебоксары
Вот чего не понимаю... Тот же exit в виде Драконовской ветки никого вроде не напрягает и возражений не вызывает...

Получается "думание над совокупностью условий" vs. "нормальное визуальное представление"?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Пятница, 23 Январь, 2009 09:37 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Эээ, в том-то и штука, что на плоскости получается не exit, а исход, по которому дальше идёт выполнение. А break-и в линейном тексте все ведут в одну точку. Если мы не можем сформулировать чётко условие на один исход - значит, плохо понимаем его смысл )
Если же ситуация такая, что действительно не хватает двумерности, многих исходов - то break не поможет, как мёртвому припарка. Вот и остаётся он для тыкальщиков ))

(Дракон же обладает таким свойством, что на любую выходящую стрелку постусловие сразу видно (провёл взглядом вверх, сконьюнктил условия из развилок по пути - и увидел)).

Лично я считаю вопрос этот предельно ясным - ситуации, про которые говорят "без досрочных выходов трудно", бывают - в управляющей логике особенно. Но break эти ситуации НЕ РЕШАЕТ. И вообще в рамках операторного языка их ничего не решит. А в большинстве случаев россказни про то, как "я не мог написать цикл без выхода, там такой цикл..." связаны просто с неумением циклы строить - если человек пишет что-то типовое, а не некий системный код автоматообразный.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 13 Июль, 2009 20:39 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
В каких мало-мальски реалистичных языках (кроме О-07) есть цикл Дейкстры?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Суббота, 05 Декабрь, 2009 19:18 

Зарегистрирован: Среда, 04 Июль, 2007 16:43
Сообщения: 247
Info21 писал(а):

Вон, известный Eric Raymond ("Искусство программирования на Юниксе") активно пропагандирует питон + Ц(для кусков, где нужна оптимизация) вместо Ц++. При том, что питон сильно тормозной, судя по вот этому: http://shootout.alioth.debian.org/u32/b ... l&lang=all


Имеется ввиду Why Python??

Есть ещё интересная цитата в его блоге C++ Considered Harmful:
Цитата:
C++ is an overcomplexity generator. It was designed to solve what
turned out to be the wrong problems; as a result, it lives in an
unhappy valley between two utility peaks in language-design space,
with neither the austere elegance of C nor the expressiveness and
capability of modern interpreted languages. The layers, patches, and
added features designed to lift it out of that valley have failed to
do so, resulting in a language that is bloated, obfuscated, unwieldy,
rigid, and brittle. Programs written in C++ tend to inherit all
these qualities.

In the remainder of this paper we will develop this charge into
a detailed critique of C++ and the style it encourages. While we
do not intend to insult the designers of C++, we will not make
excuses for them either. They repeatedly made design choices that
were well-intentioned, understandable in context, and wrong. We
think it is long past time for the rest of us to stop suffering
for those mistakes.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 11:11 
Модератор
Аватара пользователя

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

Пишем через простой линейный поиск:

Код:
   PROCEDURE (c: StdCache) Lookup (IN name: ARRAY OF CHAR; num: INTEGER; OUT it: CacheItem);
      VAR i: CacheItem;
   BEGIN
      i := c.items;
      WHILE (i # NIL) & ~( (i.name = name) & (num = 0) ) THEN
         IF i.name = name THEN
            DEC(num)
         END;
         i := i.next
      END;
      it := i
   END Lookup;


Ради любопытства переписываем с циклом Дейкстры:
Код:
   PROCEDURE (c: StdCache) Lookup (IN name: ARRAY OF CHAR; num: INTEGER; OUT it: CacheItem);
      VAR i: CacheItem;
   BEGIN
      i := c.items;
      LOOP
         IF (i # NIL) & (i.name # name) THEN
            i := i.next
         ELSIF (i # NIL) & (num > 0) THEN (* ASSERT(i.name = name) *)
            DEC(num);
            i := i.next
         ELSE
            EXIT
         END
      END
      (* ASSERT( (i = NIL) OR (i.name = name) & (num = 0) ) - прямо вытекает из конъюнкции отрицаний условий всех веток ЦД *)
      it := i
   END Lookup;


Сходимость тоже очевидна из наличия убывающих параметров.

А теперь внимание: сама собой случилась оптимизация, и условие i.name = name вычисляется только один раз. Классификация ситуаций идёт за счёт проверки на порядок более дешёвой i # NIL.
Т.е. ЦД даёт отличную свободу для манёвра :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 11:37 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Там и без цикла Дейкстры присутствует свобода для манёвра.
Код:
   PROCEDURE (c: StdCache) Lookup (IN name: ARRAY OF CHAR; num: INTEGER; OUT it: CacheItem);
      VAR i: CacheItem;
   BEGIN
      i := c.items;
      WHILE (i # NIL) & (num # 0) DO
         IF i.name = name THEN
            DEC(num)
         END;
         i := i.next
      END;
      IF i # NIL THEN it := i ELSE it := NIL END
   END Lookup;


Кстати, предполагается, что после цикла нужен IF?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 13:11 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Код:
   PROCEDURE (c: StdCache) Lookup (IN name: ARRAY OF CHAR; num: INTEGER; OUT it: CacheItem);
      VAR i: CacheItem;

      PROCEDURE NumOk (): BOOLEAN;
      BEGIN DEC(num); RETURN (num = -1)
      END NumOk;

   BEGIN ASSERT(num >= 0, 20);
      i := c.items;
      WHILE (i # NIL) & ~((i.name = name) & NumOk()) DO i := i.next END;
      it := i
   END Lookup;


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 13:24 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Valery Solovey писал(а):
Код:
IF i # NIL THEN it := i ELSE it := NIL END
Кстати, предполагается, что после цикла нужен IF?
Я инвертирую условие, и вы увидите, что ваш IF эквивалентен простому присваиванию:
Код:
IF i = NIL THEN it := NIL ELSE it := i END

Вместо переменной i можно сразу использовать it, тогда присваивание вообще можно удалить.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 13:44 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Если сразу использовать it, то да. Иначе, не эквивалентно: если num # 0, то нужного значения мы не нашли. Значит it не должен возвращать никакого объекта (если по условию задачи требуется строго num-ный указанный объект списка).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 14:11 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Ошибка: к моменту, когда num=0, i уже будет указывать на следующий элемент.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 15:46 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Peter Almazov писал(а):
Ошибка: к моменту, когда num=0, i уже будет указывать на следующий элемент.
Контрпример: (c.items.name = name), (num = 0) -> (i = c.items).

Если при входе в процедуру num - это число элементов (i.name = name), которые нужно пропустить (т.е. num - это индекс, начинающийся с 0), тогда ошибки нет. Если num - это натуральный номер элемента, начинающийся с 1, то ошибка есть.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 16:04 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Ну, пусть Илья напишет, с чего начинается num - с 1 или 0.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 16:22 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Valery Solovey писал(а):
Если сразу использовать it, то да. Иначе, не эквивалентно: если num # 0, то нужного значения мы не нашли. Значит it не должен возвращать никакого объекта (если по условию задачи требуется строго num-ный указанный объект списка).

Ах да, я забыл, что указатели при создании = NIL. То есть, достаточно просто присваивания.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 17:14 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Цитата:
Вместо переменной i можно сразу использовать it, тогда присваивание вообще можно удалить.


Не, итерировать внешние переменную, по ссылке - нехорошо. Надо ж тоже понимать, что косвенность. Локальный параметр цикла может быть в регистре.
Для прогулки по списку, конечно, пофиг - там так и так разыменования, но зачем привыкать?
(Это как дельфисты попривыкали к return и многократному вызову IF Fun(..) ... THEN используем Fun(...) END)

C нуля num начинается...

А в цикле Валерия, даже при переделке, упрыгаем на следующий элемент. Т.е. нужно prev помнить... Или добавлять IF num > ... THEN it := it.next END. Так что не идёт. Плюс семантика разымыта как-то... Влияние внутреннего условия на остановку цикла через не очень осмысленную в этом случае переменную num.

Про локальную процедуру, как Сергей написал, - конечно, так и делается часто :) (Хотя функция с поб. эффектом - как-то неприятно...)

Но ЦД, по-моему, рулит :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 18:19 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Илья Ермаков писал(а):
Но ЦД, по-моему, рулит :)
Да при чём тут вообще ЦД??? Была бы в КП операция "--", так этот поиск записывался бы в одну строчку:

while ((i # null) && ~((i.name == name) && (num-- == 0))) { i := i.next; }

В который раз убеждаюсь, что слухи о "рульности" ЦД сильно преувеличены: А был ли мальчик?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 18:22 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Илья Ермаков писал(а):
Не, итерировать внешние переменную, по ссылке - нехорошо. Надо ж тоже понимать, что косвенность. Локальный параметр цикла может быть в регистре.
Просто хотел, чтобы это было упомянуто как техника оптимизации.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 19:38 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Илья Ермаков писал(а):
Ради любопытства переписываем на ЦД:

Код:
   PROCEDURE (c: StdCache) Lookup (IN name: ARRAY OF CHAR; num: INTEGER; OUT it: CacheItem);
      VAR i: CacheItem;
   BEGIN
      i := c.items;
      LOOP
         IF (i # NIL) & (i.name # name) THEN
            i := i.next
      ELSIF (i # NIL) & (num > 0) THEN (* ASSERT(i.name = name) *)
              (* Тут одно из двух: либо это не ЦД, либо это^ условие не всегда  выполняется   *)
...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 19:53 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Это почему? Детерминированный вариант ЦД.

~ ( (i # NIL) & (i.name # name) ) <=> (i = NIL) OR (i.name = name)

Во второй ветке:

(i # NIL) & ( (i = NIL) OR (i.name = name) ) <=> FALSE OR (i # NIL) & (i.name = name) <=> (i # NIL) & (i.name = name)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 19:56 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Сергей Губанов писал(а):

Да при чём тут вообще ЦД??? Была бы в КП операция "--", так этот поиск записывался бы в одну строчку:

while ((i # null) && ~((i.name == name) && (num-- == 0))) { i := i.next; }

В который раз убеждаюсь, что слухи о "рульности" ЦД сильно преувеличены: А был ли мальчик?


Но этой операции нет. И в условиях её отсутствия проверки, влияющие на продолжение цикла, начинают уходить вглубь. Иногда вообще во вложенный цикл (линейный поиск в матрице и т.п.).

ЦД позволяет вытащить все проверки, связанные с продолжением цикла, на один уровень.


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

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


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

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


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

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