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 писал(а):
Не по памяти, а синтезировать программу используя маразм (зачеркнуто) "шаблон" линейный поиск. Иначе зачем базарить про него?

Ээ-э-э... Тут я порченный пациент (это тоже термин из медицины). Синтезировать не смогу, я его просто знаю :)

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

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

Автор:  Peter Almazov [ Среда, 17 Февраль, 2010 22:56 ]
Заголовок сообщения:  Re: Программирование. Начала

У вас есть инструмент - шаблон линейны поиск. Точнее, скажем так: лекция № 8 Ткачева. Я предлагаю с его помощью решить задачу, которую дает Бентли в книге "Жемчужины творчества программистов".

Вложения:
bin.png
bin.png [ 168.03 КБ | Просмотров: 10576 ]

Автор:  Илья Ермаков [ Среда, 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: Программирование. Начала

Наблюдаю за обсуждением (в этой и соседней ветках) и понимаю, что справочник нужен.

Понимаю также, что это работа не на один год, если подходить к этому серьезно.
Что считаю обязательным:
  • примеры на нескольких языках: Oberon-2, CP, Object Pascal, C. Вероятнее всего С++ и Java.
  • наличие ссылок на литературу с обсуждениями достоинств/недостатков/истории вопроса.
  • классификация. Понимаю, что это необходимо, но, не с этого начинать :)

Ну вот как-то так...

Автор:  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/