OberonCore https://forum.oberoncore.ru/ |
|
Программирование. Начала https://forum.oberoncore.ru/viewtopic.php?f=82&t=2359 |
Страница 2 из 3 |
Автор: | Peter Almazov [ Среда, 17 Февраль, 2010 21:51 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Илья Ермаков писал(а): Бинарный поиск в тот же шаблон цикла вписывается (если потом не оптимизировать): поиск на последовательности сходящихся интервалов. Я уже не удивляюсь таким заявлениям. Но, должен констатировать, что маразм с линейным поиском превышает все мыслимые пределы.
|
Автор: | Илья Ермаков [ Среда, 17 Февраль, 2010 22:02 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Это Вы за деревьями леса не хотите видеть. К частностям целпяетесь. Математика - это не просто формалистика, суть надо видеть. Цикл по определению работает над последовательностью состояний. Ничего кроме последовательности у цикла быть не может (в отличие от рекурсии). А цель цикла либо проста (один класс состояний), либо сложна (дизъюнктивная форма). ЛП - навязывание дисциплины с выделением этих классов и оперированием с дизъюнктивной формой постусловия. Фактически, только два случая и могут быть: ЛП не нужен (нет дизъюнкции вообще), ЛП нужен (несколько классов конечных состояний). Никакой мистики. Просто явное выделение того, на что не обращалось внимания. |
Автор: | Димыч [ Среда, 17 Февраль, 2010 22:09 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): Илья Ермаков писал(а): Бинарный поиск в тот же шаблон цикла вписывается (если потом не оптимизировать): поиск на последовательности сходящихся интервалов. Я уже не удивляюсь таким заявлениям. Но, должен констатировать, что маразм с линейным поиском превышает все мыслимые пределы.Вы знаете, маразм, как и склероз - серьезные неврологические заболевания, у них нет ни мыслемых, ни немыслемых пределов. Это либо высыхание (истощение) мозга (маразм), либо загнивание мозга (склероз). Поэтому, пожалуйста, попробуйте переформулировать суть несогласия. Мне не кажется фраза Ильи какой-то странной. Тем более, что он не раз уже ее обосновывал. Как я понял эту фразу - бинарный поиск делается по той же схеме, что и линейный (в контексте разговора об атомарных операциях), разница лишь в понятии "взять следующий". Оно действительно зависит от интервала и вычисляется по сравнению с линейным поиском весьма своеобразно. |
Автор: | Peter Almazov [ Среда, 17 Февраль, 2010 22:13 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Закройте все книги, синтезируйте программу двоичного поиска и докажите, хотя бы себе, ее правильность. Время не ограничено, но разумное время на эту задачу 3-5 минут. Но с непривычки может быть значительно больше, время - не главное. |
Автор: | Димыч [ Среда, 17 Февраль, 2010 22:19 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): Закройте все книги, синтезируйте программу двоичного поиска и докажите, хотя бы себе, ее правильность. Время не ограничено, но разумное время на эту задачу 3-5 минут. Но с непривычки может быть значительно больше, время - не главное. Не понял... Предлагается по памяти записать бинарный поиск? Запишу, поскольку у меня это еще с олимпиад в печенках сидит. Да, сейчас далеко за полночь и я могу не сразу все вспомнить, но у меня действительно уйдет 3-5 мин на то, чтобы руки с головой нарисовали этот самый поиск. Или что-то другое имеется ввиду? |
Автор: | Peter Almazov [ Среда, 17 Февраль, 2010 22:25 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Не по памяти, а синтезировать программу используя маразм (зачеркнуто) "шаблон" линейный поиск. Иначе зачем базарить про него? |
Автор: | Димыч [ Среда, 17 Февраль, 2010 22:34 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): Не по памяти, а синтезировать программу используя маразм (зачеркнуто) "шаблон" линейный поиск. Иначе зачем базарить про него? Ээ-э-э... Тут я порченный пациент (это тоже термин из медицины). Синтезировать не смогу, я его просто знаю Я могу утверждать, что - в обоих поисках используется объемлющий цикл - в обоих поисках есть действие по проверке элемента (охрана цикла?) - в обоих поисках приходится производить дополнительное действие при выходе, поскольку мы могли или найти, или не найти. Различия лишь в том, как осуществляется продвижение по последовательности, в которой производится поиск (в случае с бинарным поиском последовательность заведомо сортированная и переход нелинейный). Но в общем случае мы можем обозвать это действие "взять следующий" и на уровне шаблона поиски совпадают. |
Автор: | Илья Ермаков [ Среда, 17 Февраль, 2010 23:11 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): Не по памяти, а синтезировать программу используя маразм (зачеркнуто) "шаблон" линейный поиск. Иначе зачем базарить про него? Приведено как начальный вариант в новой редакции АСД: Код: L := 0; R := N -1; m := любое значение между L и R; WHILE (L <= R) & (a[m] # x) DO IF a[m] < x THEN L := m + 1 ELSE R := m - 1 END; m := любое значение между L и R END Цитата: Подчеркнём фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R. Чтобы не потерять это подобие и тем самым надёжнее гарантировать корректность цикла, мы воздержались от соблазна мелкой оптимизации программы с целью устранения дублирование инструкции присваивания переменной m. <Дальше инвариант (A k: 0 <= k < L: a_k < x) & (A k: R < k < N: a_k > x) и обоснование корректности> Как уже упоминалось, можно заняться устранением дублирования инструкции присваивания m. Однако такая оптимизация на уровне кода является преждевременной в том смысле, что сначала лучше попытаться оптимизировать алгоритм на уровне логики задачи. Здесь это действительно возможно: ввиду сходства алгоритма с алгоритмом линейного поиска естественно искать решение с более простым условием окончания, то есть без второго операнда конъюнкции в охране цикла (И.Е.: аналогия с барьером в случае ЛП). Для этого нужно отказаться от наивного желания закончить поиск сразу после нахождения искомого значения. На первый взгляд это неразумно, но при ближайшем рассмотрении оказывается, что выигрыш в эффективности на каждом шаге больше, чем... Более быстрое решение основано на следующем инварианте: (A k: 0 <= k < L : a_k < x) & (A k: R <= k < N : a_k >= x), а поиск продолжается, пока два отрезка не будут покрывать весь массив. Код: L := 0; R := N; WHILE L < R DO m := (L + R) DIV 2; IF a[m] < x THEN L := m + l ELSE R := m END END Цитата: Можно сказать, что теперь ищется не элемент a[m] = x, а граница, отделяющая все элементы, меньшие x, от всех прочих.
... В отличие от первого решения, данный алгоритм - как и линейный поиск - находит искомое значение в позиции с наименьшим индексом. |
Автор: | Валерий Лаптев [ Среда, 17 Февраль, 2010 23:18 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Илья Ермаков писал(а): Код: L := 0; R := N; WHILE L < R DO m := (L + R) DIV 2; IF a[m] < x THEN L := m + l ELSE R := m END END не кажется ли вам, что корректнее писакть Код: m:= (L + (R-L)) DIV 2; Не может ли возникнуть в вашем случае переполнения суммы L+R ? |
Автор: | Илья Ермаков [ Среда, 17 Февраль, 2010 23:22 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Да ну, нереальная ситуация. Даже если Вы возьмёте массив размером со всё адресное пространство, то поделите это на размер элемента - получитё ёмкость индексов, в неск. раз меньшую MAX(INTEGER). А случай не мой; а полностью из книги процитированный. |
Автор: | Geniepro [ Четверг, 18 Февраль, 2010 07:36 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Однако ява-программисты таки столкнулись однажды с этим глюком в стандартной функции бинарного поиска... |
Автор: | Peter Almazov [ Четверг, 18 Февраль, 2010 08:17 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Илья Ермаков писал(а): Приведено как начальный вариант в новой редакции АСД: ... Смиялсо.Вы читать-то умеете? Peter Almazov писал(а): Закройте все книги ... --------Цитата: Подчеркнём фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R.... Пример характернейший. В приведенной цитате вся галиматья про линейный поиск - целиком на совести info21, тут даже оригинал можно не перечитывать. Но я все же проверил. У Вирта, к его чести, ничего этого нет.
|
Автор: | Валерий Лаптев [ Четверг, 18 Февраль, 2010 08:28 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): Илья Ермаков писал(а): Приведено как начальный вариант в новой редакции АСД: ... Смиялсо.Вы читать-то умеете? Peter Almazov писал(а): Закройте все книги ... --------Цитата: Подчеркнём фундаментальное структурное подобие этого алгоритма и алгоритма линейного поиска в предыдущем разделе: роль i теперь играет тройка L, m, R.... Пример характернейший. В приведенной цитате вся галиматья про линейный поиск - целиком на совести info21, тут даже оригинал можно не перечитывать. Но я все же проверил. У Вирта, к его чести, ничего этого нет.Это вы, батенька, ахинею несете! Затем именно и нужны справочники, о которых Димыч говорил в первом посте. Грамотный инженер из башки не будет придумывать, он в справочник полезет. А в справочнике как раз паттерны-то и прописаны! И в каких условиях их применять лучше! |
Автор: | Peter Almazov [ Четверг, 18 Февраль, 2010 09:05 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Валерий Лаптев писал(а): А в справочнике как раз паттерны-то и прописаны! Я говорю об инструменте для "прописывателей паттернов".
|
Автор: | Валерий Лаптев [ Четверг, 18 Февраль, 2010 11:33 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): Валерий Лаптев писал(а): А в справочнике как раз паттерны-то и прописаны! Я говорю об инструменте для "прописывателей паттернов".Прошу прощения - не понял. Если вы о том, что в справочнике прописывать, а что считать творческим алгоритмом, то я тоже такой вопрос задавал. ИМХО паттерн двоичного поиска должен быть прописан. Как и паттерны линейного поиска, поиска максимума или минимума... И т.п. Или вы о том, что не получится прописать ПРАВИЛЬНЫЙ паттерн? |
Автор: | Димыч [ Четверг, 18 Февраль, 2010 11:38 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): Валерий Лаптев писал(а): А в справочнике как раз паттерны-то и прописаны! Я говорю об инструменте для "прописывателей паттернов".Честно говоря, так и не понял вашу позицию. Ну да ладно... Утро вечера мудренее: вынужден с вами согласиться. Из головы у большинства программеров поиск выйдет с ошибкой. Но ведь тем важнее создание справочника, в котором будет прописано что да как делать - бери и списывай. Понятно, что на такие вещи надо натаскиваться во время обучения, что такие вещи должны просто от зубов отскакивать. Но мы имеем то, что имеем - разночтения даже в основных алгоритмах, не говоря уже о том, как реализовывать "хаки" и "трюки". |
Автор: | Info21 [ Четверг, 18 Февраль, 2010 11:42 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Geniepro писал(а): Однако ява-программисты таки столкнулись однажды с этим глюком в стандартной функции бинарного поиска... Примеры в этой книге -- вовсе не код для библиотек. Это учебные примеры -- базовые алгоритмы "общего назначения". Библиотечная программа обычно нашпигована всякими проверками по самое не могу. В учебнике нельзя объять необъятное. Вирт и в предисловии о чем-то таком пишет, мол, хотел не просто слова, а довести до работающих примеров. Но не до качества универсальных библиотек. |
Автор: | Димыч [ Четверг, 18 Февраль, 2010 11:49 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Наблюдаю за обсуждением (в этой и соседней ветках) и понимаю, что справочник нужен. Понимаю также, что это работа не на один год, если подходить к этому серьезно. Что считаю обязательным:
Ну вот как-то так... |
Автор: | Info21 [ Четверг, 18 Февраль, 2010 12:05 ] |
Заголовок сообщения: | Re: Программирование. Начала |
Peter Almazov писал(а): галиматья про линейный поиск Если я отвечу "око за око", то какой-нибудь очередной обиженный когда-нибудь это мне припомнит. А поскольку модераторы и так политику, наконец, ужесточают, то и мне нужды давать вам в глаз особой нет.Данная версия алгоритма была написана упростить объясняющую логику в тексте и упростить верификацию -- как и в случае всех других исправлений в новой версии книги (см. предисловие переводчика http://www.inr.ac.ru/~info21/wirth/ADru ... versii.htm). Все исправления -- начиная с их цели -- были одобрены Виртом. Он просил внести их в английский текст, но мне трудно найти связный блок времени, потому что нужно будет делать и изменения по тексту. Если у кого-то есть время -- займитесь, я просмотрю изменения на предмет английского, и новый вариант будет выложен на страничке Вирта в ETH с указанием имени героя. У вас по существу есть возражения? |
Страница 2 из 3 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |