OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Воскресенье, 24 Февраль, 2019 03:48

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




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

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Илья Ермаков писал(а):
Представьте себе вместо примера с двумерным массивом поиск в страничной структуре вида
Page = POINTER TO RECORD data: ARRAY 2048 OF Elem; next: Page END.


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


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9088
Откуда: Россия, Орёл
AVC писал(а):
Код:
struct def *search(const char *name)
{
    struct def *p;

    for (p = root; p != NULL; p = p->next)
        if (strcmp(name, p->name) == 0)
            return p;
    return NULL;
}
И тут, конечно, Вы меня начинаете критиковать за "нестрогость" и несоответствие образцу линейного поиска.

Ну хорошо, а если не отдельный поиск, а конкретный поиск с выполнением в случае, если найден, конкретного действия?
Будем писать
Цитата:
for (p = root; p != NULL; p = p->next)
if (strcmp(name, p->name) == 0)
{
делаем что-то с p;
break;
}

А я - безо всякого даже знания о "грамотных циклах", просто исходя из житейской логики - спрошу: позвольте, в цикле пишутся те действия, которые повторяются много раз. Почему же у нас львиную долю тела цикла занимают действия, которые выполняются один раз, ПОСЛЕ цикла?

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

Вот на Драконе линейный поиск:
Вложение:
linsearchdrakon.jpg
linsearchdrakon.jpg [ 20.09 КБ | Просмотров: 7551 ]

- тут в двумерном представлении вообще все противоречия исчезают и между структурированностью, и между возможностью иметь несколько выходов.
Если я начну на Драконе записывать обычный линейный поиск - я получу как раз эту же схему!! Потому что конъюнкция условий будет выражена графически как раз этой "ступенькой развилок". А потом я увижу, что после схлопывания выходов я опять анализирую то же самое и "сокращу" проверку, навесив две ситуации прямо на линии выходов.


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

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

Два вложенных цикла не отражают того, что поиск единый, последовательный. Насчёт одного цикла WHILE и вложенного IF - вполне нормально и так. Насчёт Вашего варианта отдельной функции: да, иногда сам применял такое решение, катит :-) Но в более сложных случаях.


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1022
Откуда: Россия, Чебоксары
Vlad писал(а):
Представил. Два цикла - все равно нагляднее. Еще лучше - отдельная функция анализа страницы применямая к каждой странице.
А вот и вовсе даже не нагляднее! ;)
Я вообще не обязан знать о страницах, я работаю с информационной моделью, которую мне даёт хороший интерфейс. И этот интерфейс инкапсулирует детали реализации, которые для меня в данной задаче не важны (а там пусть хоть из инета грузится очередная страница).


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

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Илья Ермаков писал(а):
Два вложенных цикла не отражают того, что поиск единый, последовательный.


Хм. А больше одной процедуры не отражают, что модуль один? Не, правда, очень странный аргумент...

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


Это зависит от того, насколько сложно завести отдельную функцию ;)


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1343
Илья Ермаков писал(а):
Ну хорошо, а если не отдельный поиск, а конкретный поиск с выполнением в случае, если найден, конкретного действия?
Будем писать
Код:
    for (p = root; p != NULL; p = p->next)
        if (strcmp(name, p->name) == 0)
        {
           делаем что-то с p;
           break;
         }
А я - безо всякого даже знания о "грамотных циклах", просто исходя из житейской логики - спрошу: позвольте, в цикле пишутся те действия, которые повторяются много раз. Почему же у нас львиную долю тела цикла занимают действия, которые выполняются один раз, ПОСЛЕ цикла?


"Львиную долю цикла" в смысле объёма записанного кода?
Ну так её и так переписать можно (по логике?...):
Код:
for (p = root; p != NULL; p = p->next)
        if (strcmp(name, p->name) == 0)
        {
           break;
         }
 делаем что-то с p;

Только теперь не совсем ясно с каким именно указателем мы что-то делаем... Нужно ещё одно условие вводить...

А "львиная доля" как раз очень даже в нужном месте стоит. Логично. Итеративно проходя по всем элементам, мы выполняем некое действие только с тем элементом, что подпадает под условие. И - заметьте, как раз break ЯВНО указывает, что наша логика - я нашёл, что нужно, что-то с найденным сделал и поиск других таких же не надо дальше производить! Если бы нужно было - break-а бы не стояло...
... А перенеси вы "львиную долю после цикла", вам ещё и доп проверку надо производить на найденный элемент или проход по всему массиву (без нахождения нужного элемента)...


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

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Alexey_Donskoy писал(а):
А вот и вовсе даже не нагляднее! ;)
Я вообще не обязан знать о страницах, я работаю с информационной моделью, которую мне даёт хороший интерфейс. И этот интерфейс инкапсулирует детали реализации, которые для меня в данной задаче не важны (а там пусть хоть из инета грузится очередная страница).


Не понял. Какое это имеет отношение к выносу внутреннего цикла в функцию?


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

Зарегистрирован: Понедельник, 05 Июнь, 2006 09:49
Сообщения: 327
Откуда: Ленинград, Емельянов Алексей Николаевич
Я как-то своей коллеге (под влиянием Ермакова :) ) помог переделать цикл с "брэйками" в "While" без "брейков". Суть там была в том, что основные действия как раз производились для найденного элемента, которые она пыталось делать с помощью "брэйков". Когда объем процедуры уменьшился раз в ... , ну в общем на много, я почувствовал удовлетворение :D
По моим наблюдениям, народ предпочитает "брэйки" из-за того, что не привык к длинным цепочкам логических условий, хочет на каждый логический "чих" какое-то отдельное выражение.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7972
Откуда: Троицк, Москва
Vlad писал(а):
Info21 писал(а):
Vlad писал(а):
Покажите реальный пример, где цикл Д. нагляднее.

Докажите, что вы прочли книжки Дейкстры и Гриса.

Как? Подписаться под тем, что цикл Д. имеет смысл в современном ЯВУ? :)
Я не спрашивал, поняли ли вы там что-то. Докажите, что добросовестно прочли.


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1343
Axcel писал(а):
По моим наблюдениям, народ предпочитает "брэйки" из-за того, что не привык к длинным цепочкам логических условий, хочет на каждый логический "чих" какое-то отдельное выражение.
блин,! Да причём тут "привык-не привык"???
что нагляднее?
Код:
foreach( ItemType item in items )
{
    if( condition( item ) )
    {
         do_something( item );
         break;
    }
}
или
Код:
bool foundIndex = -1;
for( int i = 0; i<items.count; ++i )
{
    if( condition( items[ i ] && foundIndex == -1)
        foundIndex = i;
}
if( foundIndex != -1 ) do_something( items[ foundIndex ] );
а ведь условия и последовательности цепочек могут быть НАМНОГО длиннее и объёмнее...
к тому же, в первом случае "чистота" описания условий/действий явно поприличнее, чем во втором, где вводится "логический шум"...


Последний раз редактировалось Wlad Понедельник, 17 Ноябрь, 2008 23:01, всего редактировалось 3 раз(а).

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

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


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9088
Откуда: Россия, Орёл
Владимир Лось писал(а):
bool foundIndex = -1;
for( int i = 0; i<count; ++i )
{
if( condition && foundIndex == -1) foundIndex = i;
}
if( foundIndex != -1 ) do_something();


Владимир, что за КОШМАР???

Это ж записывается так:
Цитата:
for( int i = 0; (i<count) && !condition; ++i );
<-- вообще с пустым телом цикл... && в Си ведь гарантирует сокращённое вычисление??
if ( i < count ) {
do_something();
}


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

Зарегистрирован: Воскресенье, 28 Май, 2006 22:12
Сообщения: 1343
Илья Ермаков писал(а):
Владимир, что за КОШМАР???

...а ведь условия и последовательности цепочек могут быть НАМНОГО длиннее и объёмнее...


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9088
Откуда: Россия, Орёл
Владимир Лось писал(а):
И - заметьте, как раз break ЯВНО указывает, что наша логика - я нашёл, что нужно, что-то с найденным сделал и поиск других таких же не надо дальше производить! Если бы нужно было - break-а бы не стояло...

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


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

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9088
Откуда: Россия, Орёл
И что? Если сама запись короче выходит?

condition вычисляемый? Можно в функцию, можно (если такты не позволяют или ещё что) в теле цикла расчитывать перед очередной итерацией (немного поменяв порядок проверки условий - или вообще лучше уйдя к while).


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1022
Откуда: Россия, Чебоксары
Vlad писал(а):
Alexey_Donskoy писал(а):
А вот и вовсе даже не нагляднее! ;)
Я вообще не обязан знать о страницах, я работаю с информационной моделью, которую мне даёт хороший интерфейс. И этот интерфейс инкапсулирует детали реализации, которые для меня в данной задаче не важны (а там пусть хоть из инета грузится очередная страница).
Не понял. Какое это имеет отношение к выносу внутреннего цикла в функцию?
Так ведь речь шла про линейный поиск, и нам не важно, что сама структура данных разбита на страницы. Делая два цикла, Вы лезете внутрь структуры данных... А она вообще не нужна в данной задаче (или может быть переменной, полиморфной ну и т.п.).
Грубо говоря, я хочу решать СВОЮ задачу, используя системный драйвер для доступа к данным, в то время как Вы предлагаете попутно с решением задачи ещё и сам драйвер писать ;)


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

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey_Donskoy писал(а):
Vlad писал(а):
]Не понял. Какое это имеет отношение к выносу внутреннего цикла в функцию?
Так ведь речь шла про линейный поиск, и нам не важно, что сама структура данных разбита на страницы. Делая два цикла, Вы лезете внутрь структуры данных... А она вообще не нужна в данной задаче (или может быть переменной, полиморфной ну и т.п.).
Грубо говоря, я хочу решать СВОЮ задачу, используя системный драйвер для доступа к данным, в то время как Вы предлагаете попутно с решением задачи ещё и сам драйвер писать ;)

Так он и предложил -- один цикл, в котором к каждой странице применяется отдельная функция поиска в этой странице...


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

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

А Илья предлагал отделить задачу от механизма доступа к данным. В задаче - цикл один, единственный. По смыслу её. Потому что сквозной индекс (порядковый номер) нас интересует, и просмотр всех данных по этому индексу.

А доступ к данным может быть сколь угодно сложным, включая мапирование сквозного индекса на страницы и т.п.


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

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

Какой смысл лепить два простых цикла в один громоздкий и малопонятный?


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

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 1022
Откуда: Россия, Чебоксары
Инкапсуляция. Управление сложностью.
И не надо один громоздкий. Вот механизм доступа целесообразно вынести в процедуру...


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

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


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

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


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

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