OberonCore https://forum.oberoncore.ru/ |
|
Цикл Дейкстры https://forum.oberoncore.ru/viewtopic.php?f=30&t=1225 |
Страница 4 из 9 |
Автор: | Vlad [ Понедельник, 17 Ноябрь, 2008 21:18 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Илья Ермаков писал(а): Представьте себе вместо примера с двумерным массивом поиск в страничной структуре вида Page = POINTER TO RECORD data: ARRAY 2048 OF Elem; next: Page END. Представил. Два цикла - все равно нагляднее. Еще лучше - отдельная функция анализа страницы применямая к каждой странице. |
Автор: | Илья Ермаков [ Понедельник, 17 Ноябрь, 2008 21:25 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
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-и схлопываются в конце в одной точке. А путаницы уйма - пропадает ясность свойств кода (для меня ясность - это возможность тыкнуть пальцем в любую точку-срез, определить утверждения и видеть все возможные маршруты входа-выхода). Потому что в линейном операторном программировании мы пытаемся прорваться во второе измерение - и не прорываемся, и ясность рушим. Вот на Драконе линейный поиск: Вложение: - тут в двумерном представлении вообще все противоречия исчезают и между структурированностью, и между возможностью иметь несколько выходов. Если я начну на Драконе записывать обычный линейный поиск - я получу как раз эту же схему!! Потому что конъюнкция условий будет выражена графически как раз этой "ступенькой развилок". А потом я увижу, что после схлопывания выходов я опять анализирую то же самое и "сокращу" проверку, навесив две ситуации прямо на линии выходов. |
Автор: | Илья Ермаков [ Понедельник, 17 Ноябрь, 2008 21:28 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Vlad писал(а): Представил. Два цикла - все равно нагляднее. Еще лучше - отдельная функция анализа страницы применямая к каждой странице. Два вложенных цикла не отражают того, что поиск единый, последовательный. Насчёт одного цикла WHILE и вложенного IF - вполне нормально и так. Насчёт Вашего варианта отдельной функции: да, иногда сам применял такое решение, катит Но в более сложных случаях. |
Автор: | Alexey_Donskoy [ Понедельник, 17 Ноябрь, 2008 21:44 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Vlad писал(а): Представил. Два цикла - все равно нагляднее. Еще лучше - отдельная функция анализа страницы применямая к каждой странице. А вот и вовсе даже не нагляднее! Я вообще не обязан знать о страницах, я работаю с информационной моделью, которую мне даёт хороший интерфейс. И этот интерфейс инкапсулирует детали реализации, которые для меня в данной задаче не важны (а там пусть хоть из инета грузится очередная страница). |
Автор: | Vlad [ Понедельник, 17 Ноябрь, 2008 22:14 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Илья Ермаков писал(а): Два вложенных цикла не отражают того, что поиск единый, последовательный. Хм. А больше одной процедуры не отражают, что модуль один? Не, правда, очень странный аргумент... Илья Ермаков писал(а): Насчёт Вашего варианта отдельной функции: да, иногда сам применял такое решение, катит Но в более сложных случаях. Это зависит от того, насколько сложно завести отдельную функцию |
Автор: | Wlad [ Понедельник, 17 Ноябрь, 2008 22:14 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Илья Ермаков писал(а): Ну хорошо, а если не отдельный поиск, а конкретный поиск с выполнением в случае, если найден, конкретного действия? Будем писать Код: 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-а бы не стояло... ... А перенеси вы "львиную долю после цикла", вам ещё и доп проверку надо производить на найденный элемент или проход по всему массиву (без нахождения нужного элемента)... |
Автор: | Vlad [ Понедельник, 17 Ноябрь, 2008 22:18 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Alexey_Donskoy писал(а): А вот и вовсе даже не нагляднее! Я вообще не обязан знать о страницах, я работаю с информационной моделью, которую мне даёт хороший интерфейс. И этот интерфейс инкапсулирует детали реализации, которые для меня в данной задаче не важны (а там пусть хоть из инета грузится очередная страница). Не понял. Какое это имеет отношение к выносу внутреннего цикла в функцию? |
Автор: | Axcel [ Понедельник, 17 Ноябрь, 2008 22:30 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Я как-то своей коллеге (под влиянием Ермакова ) помог переделать цикл с "брэйками" в "While" без "брейков". Суть там была в том, что основные действия как раз производились для найденного элемента, которые она пыталось делать с помощью "брэйков". Когда объем процедуры уменьшился раз в ... , ну в общем на много, я почувствовал удовлетворение По моим наблюдениям, народ предпочитает "брэйки" из-за того, что не привык к длинным цепочкам логических условий, хочет на каждый логический "чих" какое-то отдельное выражение. |
Автор: | Info21 [ Понедельник, 17 Ноябрь, 2008 22:33 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Vlad писал(а): Info21 писал(а): Vlad писал(а): Покажите реальный пример, где цикл Д. нагляднее. Докажите, что вы прочли книжки Дейкстры и Гриса. Как? Подписаться под тем, что цикл Д. имеет смысл в современном ЯВУ? |
Автор: | Wlad [ Понедельник, 17 Ноябрь, 2008 22:55 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
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 ] ); к тому же, в первом случае "чистота" описания условий/действий явно поприличнее, чем во втором, где вводится "логический шум"... |
Автор: | Илья Ермаков [ Понедельник, 17 Ноябрь, 2008 22:56 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Тут ещё вопрос, прочувствована ли программистом природа цикла как описания некоего процесса (изменения состояний), протекающего от начала до конца по некоторому закону. Если ощущается - то "душа просит делать по Дейкстре". Если не ощущается - то безразличие либо "в штыки". |
Автор: | Илья Ермаков [ Понедельник, 17 Ноябрь, 2008 22:59 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Владимир Лось писал(а): 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(); } |
Автор: | Wlad [ Понедельник, 17 Ноябрь, 2008 23:02 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Илья Ермаков писал(а): Владимир, что за КОШМАР??? ...а ведь условия и последовательности цепочек могут быть НАМНОГО длиннее и объёмнее... |
Автор: | Илья Ермаков [ Понедельник, 17 Ноябрь, 2008 23:03 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Владимир Лось писал(а): И - заметьте, как раз break ЯВНО указывает, что наша логика - я нашёл, что нужно, что-то с найденным сделал и поиск других таких же не надо дальше производить! Если бы нужно было - break-а бы не стояло... Две совершенно разные схемы - линейный поиск (квантор существования - "показать, что существует такой-то") и полный проход с фильтрацией (квантор всеобщности - "для любого, такого, что..., сделать то-то") |
Автор: | Илья Ермаков [ Понедельник, 17 Ноябрь, 2008 23:05 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
И что? Если сама запись короче выходит? condition вычисляемый? Можно в функцию, можно (если такты не позволяют или ещё что) в теле цикла расчитывать перед очередной итерацией (немного поменяв порядок проверки условий - или вообще лучше уйдя к while). |
Автор: | Alexey_Donskoy [ Понедельник, 17 Ноябрь, 2008 23:54 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Vlad писал(а): Alexey_Donskoy писал(а): А вот и вовсе даже не нагляднее! Не понял. Какое это имеет отношение к выносу внутреннего цикла в функцию?Я вообще не обязан знать о страницах, я работаю с информационной моделью, которую мне даёт хороший интерфейс. И этот интерфейс инкапсулирует детали реализации, которые для меня в данной задаче не важны (а там пусть хоть из инета грузится очередная страница). Грубо говоря, я хочу решать СВОЮ задачу, используя системный драйвер для доступа к данным, в то время как Вы предлагаете попутно с решением задачи ещё и сам драйвер писать |
Автор: | Geniepro [ Вторник, 18 Ноябрь, 2008 09:20 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Alexey_Donskoy писал(а): Vlad писал(а): ]Не понял. Какое это имеет отношение к выносу внутреннего цикла в функцию? Так ведь речь шла про линейный поиск, и нам не важно, что сама структура данных разбита на страницы. Делая два цикла, Вы лезете внутрь структуры данных... А она вообще не нужна в данной задаче (или может быть переменной, полиморфной ну и т.п.).Грубо говоря, я хочу решать СВОЮ задачу, используя системный драйвер для доступа к данным, в то время как Вы предлагаете попутно с решением задачи ещё и сам драйвер писать Так он и предложил -- один цикл, в котором к каждой странице применяется отдельная функция поиска в этой странице... |
Автор: | Alexey_Donskoy [ Вторник, 18 Ноябрь, 2008 09:29 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Geniepro писал(а): Так он и предложил -- один цикл, в котором к каждой странице применяется отдельная функция поиска в этой странице... А разница-то какая? В пределах страницы тоже куча данных, подлежащих поиску. Всё равно отдельный цикл нужен, хоть выноси его в функцию, хоть не выноси...А Илья предлагал отделить задачу от механизма доступа к данным. В задаче - цикл один, единственный. По смыслу её. Потому что сквозной индекс (порядковый номер) нас интересует, и просмотр всех данных по этому индексу. А доступ к данным может быть сколь угодно сложным, включая мапирование сквозного индекса на страницы и т.п. |
Автор: | Geniepro [ Вторник, 18 Ноябрь, 2008 09:52 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Alexey_Donskoy писал(а): А Илья предлагал отделить задачу от механизма доступа к данным. В задаче - цикл один, единственный. По смыслу её. Потому что сквозной индекс (порядковый номер) нас интересует, и просмотр всех данных по этому индексу. Какой смысл лепить два простых цикла в один громоздкий и малопонятный? |
Автор: | Alexey_Donskoy [ Вторник, 18 Ноябрь, 2008 10:13 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Инкапсуляция. Управление сложностью. И не надо один громоздкий. Вот механизм доступа целесообразно вынести в процедуру... |
Страница 4 из 9 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |