OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 20 Февраль, 2019 08:29

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




Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8, 9  След.
Автор Сообщение
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Вторник, 18 Ноябрь, 2008 10:48 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9084
Откуда: Россия, Орёл
Geniepro писал(а):
Какой смысл лепить два простых цикла в один громоздкий и малопонятный?

Евгений, там нет двух циклов. Там есть один. Структура задачи линейна. Ввести два - а потом пытаться каким-то образом бороться с этим несоответствием задаче, т.е. искать, где стоп-кран рвануть...


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

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Alexey_Donskoy писал(а):
Инкапсуляция. Управление сложностью.
И не надо один громоздкий. Вот механизм доступа целесообразно вынести в процедуру...
Вы о чём? Об инкапсуляции тут не было ни слова. Вопрос именно о механизме доступа к страничной структуре данных при поиске в ней: с помощью одного цикла Дейкстры (Илья Ермаков) или двух вложенных циклов с break (Vlad). С тем что этот поиск нужно оформить в виде процедуры никто и не спорит.


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1022
Откуда: Россия, Чебоксары
Ну вот Илья же ответил выше - структура задачи линейна. По сути нужен ОДИН цикл.

Два цикла есть уход от задачи и решение совсем другой задачи - иди потом, ищи, где эти задачи пересекаются и как...

Про то, чтобы поиск оформить в виде процедуры, говорил не я ;) Я говорил, что в процедуру надо упихать ДОСТУП К ДАННЫМ, где и будут учтены все страницы и т.п. Т.е. это совсем другая задача!


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

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Вы какой вариант выберете?
Код:
PROCEDURE Search1 (root: Page; item: INTEGER): INTEGER;
VAR i, pos: INTEGER; page: Page;
BEGIN
  page := root;
  pos := 0;
  WHILE page # NIL DO
    i := 0;
    WHILE i # N DO
      IF page.data[i] = item THEN RETURN pos END;
      pos := pos + 1;
      i := i + 1
    END;
    page := page.next
  END;
  RETURN -1
END Search1;

Код:
PROCEDURE Search2 (root: Page; item: INTEGER): INTEGER;
VAR i, pos: INTEGER; page: Page;
BEGIN
  page := root;
  i := 0;
  pos := 0;
  WHILE (i # N) & (page # NIL) & (page.data[i] # item) DO
    i := i + 1;
    pos := pos + 1
  ELSIF (i = N) & (page # NIL) DO
    page := page.next;
    i := 0
  END;
  IF (i # N) & (page # NIL) THEN RETURN pos ELSE RETURN -1 END
END Search2;


Последний раз редактировалось PGR Вторник, 18 Ноябрь, 2008 12:28, всего редактировалось 3 раз(а).

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

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
PGR писал(а):
Вы какой вариант выберете?
Лично я выбрал бы первый, если бы понимал, что делать потом с индексом без указания страницы.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9084
Откуда: Россия, Орёл
Не забывайте про третий вариант с обычным WHILE. За отсутствием цикла Дейкстры используется именно он (если, конечно, не изворачиваться с упаковкой поиска в процедуру с RETURN).

Насчёт его и цикла Дейкстры я не уверен, что выразительнее - одинаково...
Код:
page := first; i := 0;
WHILE (i # LEN(page.data)) & ~SearchCond(page.data[i]) DO
  INC(i);
  IF i = LEN(page.data) & (page.next # NIL) THEN
    page := page.next;
    i := 0
  END
END

(Для справки: LEN вычисляется компилятором статически)


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

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Страницу вернуть не проблема, но цикл(ы) поиска от этого не поменяются ;)


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

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
AVC писал(а):
PGR писал(а):
Вы какой вариант выберете?
Лично я выбрал бы первый, если бы понимал, что делать потом с индексом без указания страницы.
А-а, до меня дошло: потом можно вызвать функцию "Получить элемент по номеру позиции".
А в принципе, первый вариант понятнее (или, по крайней мере, привычнее).


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

Зарегистрирован: Четверг, 17 Ноябрь, 2005 11:51
Сообщения: 2930
Откуда: г. Ярославль
Владимир Лось писал(а):
Код:
foreach( ItemType item in items )
Код:
for( int i = 0; i<items.count; ++i )

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


Последний раз редактировалось Иван Кузьмицкий Вторник, 18 Ноябрь, 2008 11:43, всего редактировалось 1 раз.

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

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4488
Откуда: Россия, Орёл
PGR писал(а):
Вы какой вариант выберете?

А мне второй эстетически больше нравится/кажется проще; даже не вчитываясь в код... Может потому, что в первом случае в одном структурном операторе сидит другой, а во втором - нет.


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1022
Откуда: Россия, Чебоксары
Ну что ж вы так... Вот как надо: ;)
Код:
for i:=0 to Count-1 do if Condition(GetData(i)) then return(i);
return(-1);
И вот теперь доступ к данным отделён от алгоритма задачи. И может выглядеть по-всякому, например:
Код:
function GetData(i:integer):somedatatype;
begin
  return(Pages[i div PageSize].data[i mod PageSize]);
end;
То есть, повторяю, есть задача, а есть (вспомогательные) подзадачи. И задачу от подзадач целесообразно отделять явно. Поэтому мне одинаково не нравятся два предложенных варианта, и даже вариант Ильи тоже не нравится, поскольку он таки смешивает все слои в общую кучу... Отчего понятность кода существенно проигрывает...


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7969
Откуда: Троицк, Москва
Позорная дискуссия. Всех уволить.

Упражнение. Возьмите первый нетривиальный алгоритм в "Алгоритмах и структурах данных" Вирта (поиск Кнута-Морриса-Пратта, раздел 1.12.5 в старом издании) и перепишите двойной цикл по Дейкстре, т.е. в виде однократного с двумя ветвями.

Увидите две вещи:

1) Рассуждения по Дейкстре позволяют привести нестандартный цикл к стандартному виду ("циклу Дейкстры"), который по-стандартному объясняется, что, естественно, несравненно облегчает понимание-конструирование-объяснение-верификацию.

2) Сам Вирт, хотя и использует инвариант цикла, возится с двойным циклом (скорее всего, он просто "причесал" с помощью WHILE оригинальный код КМП; надо думать, он эти алгоритмы изучал в связи с компиляторами). Отсюда, видимо, объяснение, почему цикл Дейкстры появился в Обероне только в версии 07 не без внешних влиянияний.

Но то, что простительно Вирту, научившемуся уже прилично программировать до 1970 г., непростительно программерам, родившимся после 1970.
(Товарисчи постарше are exempted :-)
---------------------
---------------------
Еще видно, какая там лабуда в пояснениях, причем русский перевод-без-понятия только запутывает дело. И это не одно такое место в книжке, где перевод-по-словам-к-сроку лажает.
А советская теория перевода гласит, что перевод технического текста может и должен быть лучше оригинала 8)


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

Зарегистрирован: Суббота, 19 Ноябрь, 2005 15:59
Сообщения: 803
Откуда: Зеленоград
Info21 писал(а):
Упражнение. Возьмите первый нетривиальный алгоритм в "Алгоритмах и структурах данных" Вирта (поиск Кнута-Морриса-Пратта, раздел 1.12.5 в старом издании) и перепишите двойной цикл по Дейкстре, т.е. в виде однократного с двумя ветвями.
У кого только электронный обероновский вариант (pdf), то там это раздел 1.9.5.


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

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Alexey_Donskoy писал(а):
Ну что ж вы так... Вот как надо: ;)
Код:
for i:=0 to Count-1 do if Condition(GetData(i)) then return(i);
return(-1);
И вот теперь доступ к данным отделён от алгоритма задачи.
А то, что для рассматриваемой страничной структуры алгоритм поиска станет не линейным, а квадратичным волновать не должно?


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Info21 писал(а):
Позорная дискуссия. Всех уволить.

Не уволить, а забанить. Начать с меня, как обычно... :o


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1022
Откуда: Россия, Чебоксары
PGR писал(а):
А то, что для рассматриваемой страничной структуры алгоритм поиска станет не линейным, а квадратичным волновать не должно?
А с чего бы ему становиться квадратичным?
Вот я написал пример с прямым доступом к страницам - так он и останется линейным (за вычетом накладных расходов на вызов процедуры и пары команд целочисленной арифметики...

Разумеется, на случай жёсткой оптимизации лучше ничего не придумаешь, чем два цикла ;) Но, согласитесь, это уже совсем другая постановка задачи...

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

Пример, конечно, утрированный, абстрактный и тривиальный... Но тем не менее... ;)


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey_Donskoy писал(а):
PGR писал(а):
А то, что для рассматриваемой страничной структуры алгоритм поиска станет не линейным, а квадратичным волновать не должно?
А с чего бы ему становиться квадратичным?

Там вроде главная структура -- список (содержащий страницы). А доступ к n-му элементу списка обычно имеет сложность O(n), а не O(1) как у массива. Получается, что сложность перебора в цикле 0(n) умножается на сложность доступа к элементам массива и получается O(n^2)...


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1022
Откуда: Россия, Чебоксары
Ну я же подчеркнул - пример с прямым доступам к страницам...

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

Если однонаправленный список страниц И требование масштабируемости, тогда:

а) учёт "аппаратных" ограничений => направление просмотра, совпадающее со списком;
б) кеширование:

Код:
function GetData(i:integer):somedatatype;
begin
  if i div PageSize>BegPageIndex then begin Page:=Next; inc(BegPageIndex,PageSize); end;
  return(Page.data[i mod PageSize]);
end;
Заметим, что это тот же алгоритм Ильи, но с разнесёнными слоями задачи и подзадачи...

Для универсальности и произвольного доступа кэширование, конечно, будет чуть сложнее... Но всё равно для сонаправленного со списком просмотра затратность всё равно будет О(1), а для противоположного, самого неприятного случая, значительно хуже 1, но всё-таки никак не в квадрате ;)


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

Зарегистрирован: Вторник, 18 Сентябрь, 2007 08:48
Сообщения: 108
2 замечания
1. Насколько быстродействущим является цикл Дейкстры? IMHO, стандартный цикл с двумя (тремя) for-ами (примеры выше) все таки будет пошустрее.
2. Некоторые компиляторы могут из вложенных циклов сделать один суперцикл.

PS. Не понимаю, о чем спор? Вирт и Дейкстра - все таки не божки, их мнения не являются абсолютизмом. Вам решать, как строить циклы на свой вкус и стиль.


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9084
Откуда: Россия, Орёл
Речь не о вкусах, а о понимании/не понимании смысла, лежащего под составлением алгоритмов.
viewtopic.php?p=21375#p21375
Цитата:
Вообще меня всегда поражали эти споры касательно метода Дейкстры.
Вот в третьем классе детям на математике начинают объяснять, что такое уравнения (по крайней мере по занковской системе мы их тогда уже активно изучали). И с их помощью начинают решать задачки. Те же самые, которые раньше решались по действиям с задействованием "общей соображалки". И ведь точно так же было непонятно "а на хрена ж эти уравнения сдались, мы вот и под действиям сообразим"... Только задачи бывают и на порядок сложнее, а при владении единым методом щёлкаются как семечки. Есть общий мат. метод составления уравнений. А есть "партизанские вилы".


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

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


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

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


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

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