Заглянул в это обсуждение, потому что задал упрощённый вариант этой задачи на школьном математическом кружке. Давайте упростим, действительно, взяв ситуацию с всего двумя стульями. Также, заменим для наглядности 9/10 на 1/2 — теперь можно подкидывать монетку. Подкинем монетку два раза (О — орёл, Р — решка) и договоримся, что одинаковые исходы (ОО, РР) будут означать отсутствие бриллиантов, а при разных исходах (ОР, РО) — бриллианты в том стуле, на который выпал орёл.
Ваш ответ — «вероятность найти бриллианты во втором стуле равна 1/2» (я заменил 9/10 на 1/2 в соответствии с упрощением, из-за монетки — зачем так я упрощаю, объясню ниже). Попробуйте объяснить мне, как именно нужно поставить схему испытаний, чтобы получить такой ответ. Ниже я приведу две схемы испытаний, одна из которых подходит под формулировку задачи, другая — нет. Любопытно, что результат 1/2 не получается ни в одной из приводимых мной ниже схем.
Первая схема: в результате двух подкидываний мы составляем гарнитур из двух целых стульев, с вероятностью 1/2 (ОО, РР) получая отсутствие бриллиантов в обоих стульях, с вероятностью 1/4 получим бриллианты в первом стуле (ОР) и с вероятностью 1/4 получим бриллианты во втором стуле (РО) — после чего рассматриваем все четыре исхода. Приходим к выводу, что если у стульев есть серийные номера (№1, №2), а в задаче спрашивается «какова вероятность, что бриллианты зашиты в стуле №2?», ответ будет — 1/4. Эта схема не подходит под условие задачи, поскольку включает в общий список из четырёх равновероятных исходов один исход, явно запрещённый условием задачи, а именно тот, при котором бриллианты обнаруживаются в первом вскрытом стуле (это станет понятнее после рассмотрения второй, подходящей под условие задачи схемы испытаний).
Переходим ко второй схеме. В формулировке задачи сказано, что «к следующему переходят только в том случае, если в текущем стуле не нашлось бриллиантов». С такой формулировкой удобней номер броска монеты интерпретировать как номер выбранного для вскрытия стула. Нас спрашивают про вероятность нахождения бриллиантов в оставшемся стуле после того, как вскрытие первого стула дало ноль бриллиантов на выход. В этой постановке из мира 4-х равновероятных исходов ОО, ОР, РО, РР вычеркнут один: ОР (поскольку в первом стуле бриллианты обнаружены не были). Оставшиеся 3 исхода так же равновероятны, как до вычёркивания. Поскольку теперь (в мире «при условии, что в первом стуле бриллиантов не обнаружено») исходов осталось 3, вероятность каждого из них — одна треть. Нас интересует один исход из трёх: РО (два других означают полное отсутствие бриллиантов). Его вероятность равна 1/3. Это соответствует решению более сложного случая, приведённому автором заметки.
1/2 не получается никак. Позволю себе такую аналогию. Наличие бриллиантов в одном из стульев — научная гипотеза; обстоятельства таковы, что до экспериментирования по теоретическим расчётам вероятности того, что она верна, и того, что она неверна — равны (1/2 и 1/2). Первый эксперимент для проверки гипотезы: вскрытие первого стула — дал отрицательный результат. Можем ли мы говорить об уточнении научного знания после отрицательного результата первого эксперимента? Можем (а ведь точно, эксперименты ведь и ставятся для уточнения научного знания, не так ли?). Теперь мы в два раза более уверенны, что гипотеза неверна, чем в том, что гипотеза — верна (2/3 против 1/3) — делайте ваши ставки на результат второго эксперимента!
Серьёзно, похожие расчёты применяются при принятии важных решений, вроде того, какое лечение прописывать больному, ну или какое из опробованных на выборке пользователей изменение пользовательского интерфейса выпускать для всех пользователей.
Зачем я упростил задачу к бросанию монеток — в кружке для забавы можно устроить тотализатор. Ученики, уверенные в правильности оценки вероятности 1/2 или 1/4 (т.е. те, кто будет ставить «один к одному» или «один к трём») будут при долгой игре уверенно терять игрушечные деньги тем, кто уверен в правильности оценки вероятности 1/3 (т.е. тем, кто будет ставить «один к двум»). Наглядно.
Хотел бы добавить вот что по акторам и CSP — есть добротные книги, раскладывающие эти темы по полочкам, я их читал (не буду говорить, что эти книги — лучшие, но, по моему мнению, добротные). По акторам — книга автора QP (Miro Samek, «Practical UML Statecharts in C/C++»). По CSP — одноименная с названием подхода книга его изобретателя (Tony Hoar), она была переведена на русский году в 86-м примерно, «Взаимодействующие последовательные процессы».
Я тоже подумал об автоматизации, и вариантов в голове возникло два: 1) DSL, генерирующий и Kotlin-код, и Swift-код; 2) транспайлер из одного в другой. Я бы сам выбрал первый вариант — в знакомом мне C#-стеке могло бы выйти несложно. Кстати, не так давно проходила статья о делании DSL на Kotlin (примером был DSL для тестовых сценариев) — похоже, так тоже можно сделать довольно быстро.
Если вам любопытны элементарные доказательства (на уровне первых лет занятий школьного маткружка, без утомительной технической / механической работы с алгебраическими преобразованиями), рекомендую полистать книгу «Proofs That Really Count: The Art of Combinatorial Proof» (pdf можно найти в интернетах) — там авторы собрали / придумали довольно длинный ряд доказательств комбинаторных тождеств (уравнений с биномиальными коэффициентами в том числе) «на пальцах» — например, подсчитывая количество способов составить прямоугольник 2xN из N доминошек разными путями.
Не помню, приводят ли они рядом алгебраические доказательства (суть книги — именно в нахождении способов доказательств «на пальцах»!), но точно помню, что ближе к концу они дают сводку тождеств, к которым они доказательств «на пальцах» пока не нашли :). Перевода на русский вроде нет; я на досуге посмотрю из любопытства, не переводил ли / не пересказывал ли кто фрагментарно.
Спасибо! Понятно, что «проблему надо предотвращать в корне», я хотел разобраться, что говорит текущий стандарт (и как давно он так говорит). Если проблема не предотвращена в корне, ситуация становится вот какой (внизу в комментариях некоторые аспекты обсуждаются) — если для нового инстанса класса с дефолтным конструктором (и без ин-плейс инициализации POD-полей) не указана явно "()-инициализация" (например, написано ' new S; ', а не ' new S(); '), инстанс не инициализирован, в нём мусор. Однако, если "()-инициализация" указана (как в упомянутом ' new S(); ' или при вызове std::make_unique), текущий стандарт всё-таки диктует инициализацию нулями. Эта последняя деталь упоминается в некоторых обсуждениях на StackOverflow, например, но я не нашёл чёткую отсылку к стандарту. Полез смотреть сам (https://github.com/cplusplus/draft/blob/master/papers/n4687.pdf), нашёл вроде бы соответствующий пункт на странице 226:
if T is a (possibly cv-qualified) class type without a user-provided or deleted default constructor, then the object is zero-initialized and the semantic constraints for default-initialization are checked, and if T has a non-trivial default constructor, the object is default-initialized
Зачем мне нужно это выяснять в деталях, когда и так ясно, что проще всегда POD-поля ин-плейс инициализировать от греха подальше? Спор с коллегой, который ссылается на эту тонкость стандарта!
Проверяльщик VS 2017 какие-то случаи ловит, какие-то нет, к сожалению. Надо бы мне на досуге освоить проверяльщик Clang, наверно.
Сергей, допустим, я описал тип struct или class с полем int, и я поленился написать конструкторы, а также ин-плейс инициализацию для этого поля. Я создаю инстанс моего типа (неявно используя дефолтный конструктор без параметров). Что говорит стандарт разных годов выпуска про значение int-поля этого инстанса?
Да, ещё один момент — по-моему, в теорвере соответсвующее распределение вероятностей называется геометрическим: рассматривая его как дискретное (а не непрерывное, как в термодинамике), мы видим геометрическую прогрессию.
Попробую восполнить недостатки заметки — я читал про этот эксперимент исходную заметку на английском (плюс кое-что по ссылкам в обсуждении).
1. Распределение богатства, которое устанавливается после достаточно большого количества итераций (и независимо от начального распределения) — распределение Гиббса, и этот факт выводится тем же способом, как в термодинамике. Краткое пояснение на английском этого вывода приводится в разделе 2 вот этой статьи (ну, там пересказ термодинамического вывода, варианты которого есть в википедии и много где ещё на русском). Я идею вывода поверхностно понимаю, но не уверен, что хорошо перескажу в коротком комментарии, так что решил не пересказывать. Форма распределения — обрезанный и нормированный в соответствии с постановкой эксперимента график экспоненты.
2. Конечно, среднее количество денег у каждого участника — одно и то же, 100 долларов в исходной постановке с 100 участниками. Распределение же показывает, какую долю времени в среднем он проводит с такой-то суммой в кармане — более часто с меньшей, менее часто с большей. При этом, фиксированный шаг по абсциссе (деньги) даёт уменьшение среднего времени пребывания в этом состоянии (значение ординаты) в фиксированное количество раз — экспонента!
1. Спасибо за ссылку, посмотрел и буду иметь в виду.
2. Да, нужно будет кастить. Я покрутил в голове, и решил эту тему бросить — не стоит усилий в данный момент.
Спасибо за статью! У меня ещё два пункта для обсуждения, пользуюсь случаем:
1. Вы написали, что для генерации обвязки думали взять Roslyn — но не найдётся ли способов проще, например, основанных на атрибутах, использовании рефлексии, code rewrite? [ Я — C++ программист, c C# знаком неплохо, но не на экспертном уровне. Думаю полистать книгу «Metaprogramming in .Net» (2013). Использую в работе генерацию кода в небольшом DSL-фреймворке, созданном коллегами, там для фронтенда (построения AST) используется Antlr, для шаблонов генерации — T4; DSL-языки похожи синтаксисом на C#. Я думаю об освоении других фронтенд-технологий, и использование структуры Roslyn-а — один из вариантов (им пользуется, например, разработчик HlslTools для DSL «High Level Shading Language», он перешёл на такую структуру с Antlr-а, чтобы улучшить скорость разбора и восстановление при синтаксических ошибках). Есть ещё работоспособные альтернативы для фронтенда, но более экзотические (у меня на примете их примерно 3-4). Короче, меня эта тема довольно-таки занимает, пользуюсь случаем попробовать обменяться мнениями. ]
2. В статье и комментариях затрагивается проблема с расширяемостью системы при невозможности обновления исходной сборки библиотеки, в которой определены конкретные классы (или, скорее, специализирующие производные интерфейсы), наследующие IFigure. Мне кажется, если эту проблему предвидеть в дизайне библиотеки, она может решаться, хотя бы частично; детально я идею в этом направлении не обдумал ещё, правда. Автор библиотеки для того, чтобы допустить возможность расширения, оставляет один интерфейс-наследник IFigure (специально для этого предназначенный и названный, скажем, IOtherFugure) незапечатанным. Для пользователей библиотеки, или авторов новых версии библиотеки, исходный (v1) набор фигур не меняется, обслуживающие их визиторы стабильны и не нуждаются в изменениях при переходе на v2 с новыми фигурами — но нуждаются в подвеске дополнительных визиторов для новых фигур, представленных интерфейсами, наследующими от IOtherFugure. Для этого семейства в v2 создаётся новый интерфейс визиторов. Результирующая картина смеси v1 и v2 выглядит причудливо, но даёт возможность сохранить код, написанный для v1, без модификаций. Параллельно v2 предоставляет новый свежий «100% чистый v2» API без разделения на фигуры v1 / новые фигуры v2, чтобы при свежем старте на v2 или возможности переписать v1-зависимый код можно было бы иметь чистую картину, без кудрявостей. Мне кажется, такой подход может работать в реальных проектах, хотя он и «сложный».
Предположу, что под «отпиныванием от ООП» вы имели в виду сам факт, что описываемый паттерн предлагает альтернативу пополнению базового интерфейса IFigure функциями на все случаи жизни (что более «естественно» и, действительно, в ряде ситуаций является лучшей альтернативой).
Представим таблицу, строки которой соответствуют конкретным классам, реализующим IFigure, а столбцы — различным действиям, которые коду нужно выполнять с этими объектами.
Если столбцов мало, и они редко добавляются / меняются, а строк много, и они чаще добавляются / меняются, в линейном программном коде удобно группировать строки (реализовывать «естественный» подход, описанный выше). Полное описание строки — класса, реализующего IFigure, расположено в одном файле, где рядом сидит и рисование данной фигуры, и вывод на консоль, и вычисление площади… Немного разношёрстно, но зато — вот всё про эту фигуру, в одном месте! Правда, в случае с деревьями вложенных объектов логика обхода дерева объектов может оказаться многократно продублированной (для разных методов IFigure), но это не страшно, пока IFigure остаётся достаточно компактным и стабильным интерфейсом (т.е., повторяясь, когда в воображаемой таблице набор столбцов не слишком велик и достаточно стабилен).
Однако, если столбцов становится много, и они добавляются / меняются часто в сравнении с устоявшимся набором строк, группировка кода по столбцам становится более рациональным выбором. Визитор — хорошо известная и широко применяемая модель реализации этого выбора. Я встречаю успешное применение этой модели в работе, например, с синтаксическими деревьями или с деревьями вложенных объектов в графических диаграммах. Я встречал также неоднократно ситуации с безобразно разросшимися базовыми интерфейсами в отсутствии решения применить визитор.
То, что при первой встрече паттерн Визитор выглядит переусложнённым, неудивительно — структура классических ООП языков подталкивает к группировке по строкам, она как бы встраивается в арсенал программиста с первых шагов изучения ООП. Паттерны же вроде Визитора были изобретены и пере-изобретены для улучшения структуры кода в ситуациях, когда решения в лоб приводят к накапливающимся проблемам («разрастается в такое, что поддерживать становится невозможно»). Да, и, кстати, группировку по столбцам можно организовать и по-другому, в конкретной ситуации применение Визитора может быть, действительно, не самой удачной идеей. Тем не менее, последняя фраза вашего комментария («Отпинываться от ООП ради спорных идиологий и терять ресурсы на поддержке, это всё же пахнет глупым фанатизмом.») мне не кажется обоснованной без рассмотрения конкретных ситуаций. Повторюсь, имел дело с двумя широкими областями (синтаксический разбор, деловая графика) где использование Визитора вполне уместно и де-факто является стандартной для этих областей практикой.
Да-да, и мне физическая модель в голове помогает иногда понять математическую задачу, хотя я учился на математика (а стал программистом). С башнями из кубиков — я хотел обеспечить как можно более медленное опускание центра тяжести конструкции из самого высокого положения (для одной башенки из N кубиков) в самое низкое (для N башенок из одного кубика).
Поправки к №2 (конец дня, напутал лево / право в паре мест):
… Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на левослева направо (справа от любой башенки стоит или башенка той же, или меньшей высоты).…
Далее, кубики из руки выставляем слевасправа от этой укороченной башенки…
Для полноты описания к первому шагу следовало бы добавить условие остановки работы алгоритма (присутствующее неявно). Можно сформулировать так, например:
Рассмотреть подмассив от первого до предпоследнего элемента; если он пуст (в исходном массиве — всего один элемент), заврешить работу.
Если же он не пуст, двигаться по подмассиву справа налево по равным элементам, остановившись на последнем из них «x» (движение справа налево по равным элементам мне кажется более естественным, чем поиск «первого минимального» при движении слева направо).
Мне кажется «более естественной», опять же, генерация в обратном порядке — начиная с разложения N в одно слагаемое (равное N) — возможно, потому что именно это решение мне придумалось (я сейчас вспомнил, что когда-то решал эту задачу). Наглядно удобно представить это первое разложение как башню, составленную из поставленных в стопку N кубиков. Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево (справа от любой башенки стоит или башенка той же, или меньшей высоты).
Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).
«Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)
Ищу на Хабре, где я с кем-то разговаривал на эти темы. Короче, навсяк, ссылка:
https://habrahabr.ru/post/301104/
(типа, не спам — перевод интересного текста)
Согласен, но это один из разумных компромиссов для тех случаев, когда Lock в каждом модифицирующем методе — дорог по производительности. Бескомпромисный вариант — делать все структуры данных, разделяемые между потоками, immutable, с единственным корнем, который обновляется atomic операцией. Но это тоже дорого иногда (из-за дороговизны immutable версий сложных структур данных).
Заглянул в это обсуждение, потому что задал упрощённый вариант этой задачи на школьном математическом кружке. Давайте упростим, действительно, взяв ситуацию с всего двумя стульями. Также, заменим для наглядности 9/10 на 1/2 — теперь можно подкидывать монетку. Подкинем монетку два раза (О — орёл, Р — решка) и договоримся, что одинаковые исходы (ОО, РР) будут означать отсутствие бриллиантов, а при разных исходах (ОР, РО) — бриллианты в том стуле, на который выпал орёл.
Ваш ответ — «вероятность найти бриллианты во втором стуле равна 1/2» (я заменил 9/10 на 1/2 в соответствии с упрощением, из-за монетки — зачем так я упрощаю, объясню ниже). Попробуйте объяснить мне, как именно нужно поставить схему испытаний, чтобы получить такой ответ. Ниже я приведу две схемы испытаний, одна из которых подходит под формулировку задачи, другая — нет. Любопытно, что результат 1/2 не получается ни в одной из приводимых мной ниже схем.
Первая схема: в результате двух подкидываний мы составляем гарнитур из двух целых стульев, с вероятностью 1/2 (ОО, РР) получая отсутствие бриллиантов в обоих стульях, с вероятностью 1/4 получим бриллианты в первом стуле (ОР) и с вероятностью 1/4 получим бриллианты во втором стуле (РО) — после чего рассматриваем все четыре исхода. Приходим к выводу, что если у стульев есть серийные номера (№1, №2), а в задаче спрашивается «какова вероятность, что бриллианты зашиты в стуле №2?», ответ будет — 1/4. Эта схема не подходит под условие задачи, поскольку включает в общий список из четырёх равновероятных исходов один исход, явно запрещённый условием задачи, а именно тот, при котором бриллианты обнаруживаются в первом вскрытом стуле (это станет понятнее после рассмотрения второй, подходящей под условие задачи схемы испытаний).
Переходим ко второй схеме. В формулировке задачи сказано, что «к следующему переходят только в том случае, если в текущем стуле не нашлось бриллиантов». С такой формулировкой удобней номер броска монеты интерпретировать как номер выбранного для вскрытия стула. Нас спрашивают про вероятность нахождения бриллиантов в оставшемся стуле после того, как вскрытие первого стула дало ноль бриллиантов на выход. В этой постановке из мира 4-х равновероятных исходов ОО, ОР, РО, РР вычеркнут один: ОР (поскольку в первом стуле бриллианты обнаружены не были). Оставшиеся 3 исхода так же равновероятны, как до вычёркивания. Поскольку теперь (в мире «при условии, что в первом стуле бриллиантов не обнаружено») исходов осталось 3, вероятность каждого из них — одна треть. Нас интересует один исход из трёх: РО (два других означают полное отсутствие бриллиантов). Его вероятность равна 1/3. Это соответствует решению более сложного случая, приведённому автором заметки.
1/2 не получается никак. Позволю себе такую аналогию. Наличие бриллиантов в одном из стульев — научная гипотеза; обстоятельства таковы, что до экспериментирования по теоретическим расчётам вероятности того, что она верна, и того, что она неверна — равны (1/2 и 1/2). Первый эксперимент для проверки гипотезы: вскрытие первого стула — дал отрицательный результат. Можем ли мы говорить об уточнении научного знания после отрицательного результата первого эксперимента? Можем (а ведь точно, эксперименты ведь и ставятся для уточнения научного знания, не так ли?). Теперь мы в два раза более уверенны, что гипотеза неверна, чем в том, что гипотеза — верна (2/3 против 1/3) — делайте ваши ставки на результат второго эксперимента!
Серьёзно, похожие расчёты применяются при принятии важных решений, вроде того, какое лечение прописывать больному, ну или какое из опробованных на выборке пользователей изменение пользовательского интерфейса выпускать для всех пользователей.
Зачем я упростил задачу к бросанию монеток — в кружке для забавы можно устроить тотализатор. Ученики, уверенные в правильности оценки вероятности 1/2 или 1/4 (т.е. те, кто будет ставить «один к одному» или «один к трём») будут при долгой игре уверенно терять игрушечные деньги тем, кто уверен в правильности оценки вероятности 1/3 (т.е. тем, кто будет ставить «один к двум»). Наглядно.
Не помню, приводят ли они рядом алгебраические доказательства (суть книги — именно в нахождении способов доказательств «на пальцах»!), но точно помню, что ближе к концу они дают сводку тождеств, к которым они доказательств «на пальцах» пока не нашли :). Перевода на русский вроде нет; я на досуге посмотрю из любопытства, не переводил ли / не пересказывал ли кто фрагментарно.
Зачем мне нужно это выяснять в деталях, когда и так ясно, что проще всегда POD-поля ин-плейс инициализировать от греха подальше? Спор с коллегой, который ссылается на эту тонкость стандарта!
Проверяльщик VS 2017 какие-то случаи ловит, какие-то нет, к сожалению. Надо бы мне на досуге освоить проверяльщик Clang, наверно.
1. Распределение богатства, которое устанавливается после достаточно большого количества итераций (и независимо от начального распределения) — распределение Гиббса, и этот факт выводится тем же способом, как в термодинамике. Краткое пояснение на английском этого вывода приводится в разделе 2 вот этой статьи (ну, там пересказ термодинамического вывода, варианты которого есть в википедии и много где ещё на русском). Я идею вывода поверхностно понимаю, но не уверен, что хорошо перескажу в коротком комментарии, так что решил не пересказывать. Форма распределения — обрезанный и нормированный в соответствии с постановкой эксперимента график экспоненты.
2. Конечно, среднее количество денег у каждого участника — одно и то же, 100 долларов в исходной постановке с 100 участниками. Распределение же показывает, какую долю времени в среднем он проводит с такой-то суммой в кармане — более часто с меньшей, менее часто с большей. При этом, фиксированный шаг по абсциссе (деньги) даёт уменьшение среднего времени пребывания в этом состоянии (значение ординаты) в фиксированное количество раз — экспонента!
2. Да, нужно будет кастить. Я покрутил в голове, и решил эту тему бросить — не стоит усилий в данный момент.
Спасибо за обсуждение!
1. Вы написали, что для генерации обвязки думали взять Roslyn — но не найдётся ли способов проще, например, основанных на атрибутах, использовании рефлексии, code rewrite? [ Я — C++ программист, c C# знаком неплохо, но не на экспертном уровне. Думаю полистать книгу «Metaprogramming in .Net» (2013). Использую в работе генерацию кода в небольшом DSL-фреймворке, созданном коллегами, там для фронтенда (построения AST) используется Antlr, для шаблонов генерации — T4; DSL-языки похожи синтаксисом на C#. Я думаю об освоении других фронтенд-технологий, и использование структуры Roslyn-а — один из вариантов (им пользуется, например, разработчик HlslTools для DSL «High Level Shading Language», он перешёл на такую структуру с Antlr-а, чтобы улучшить скорость разбора и восстановление при синтаксических ошибках). Есть ещё работоспособные альтернативы для фронтенда, но более экзотические (у меня на примете их примерно 3-4). Короче, меня эта тема довольно-таки занимает, пользуюсь случаем попробовать обменяться мнениями. ]
2. В статье и комментариях затрагивается проблема с расширяемостью системы при невозможности обновления исходной сборки библиотеки, в которой определены конкретные классы (или, скорее, специализирующие производные интерфейсы), наследующие IFigure. Мне кажется, если эту проблему предвидеть в дизайне библиотеки, она может решаться, хотя бы частично; детально я идею в этом направлении не обдумал ещё, правда. Автор библиотеки для того, чтобы допустить возможность расширения, оставляет один интерфейс-наследник IFigure (специально для этого предназначенный и названный, скажем, IOtherFugure) незапечатанным. Для пользователей библиотеки, или авторов новых версии библиотеки, исходный (v1) набор фигур не меняется, обслуживающие их визиторы стабильны и не нуждаются в изменениях при переходе на v2 с новыми фигурами — но нуждаются в подвеске дополнительных визиторов для новых фигур, представленных интерфейсами, наследующими от IOtherFugure. Для этого семейства в v2 создаётся новый интерфейс визиторов. Результирующая картина смеси v1 и v2 выглядит причудливо, но даёт возможность сохранить код, написанный для v1, без модификаций. Параллельно v2 предоставляет новый свежий «100% чистый v2» API без разделения на фигуры v1 / новые фигуры v2, чтобы при свежем старте на v2 или возможности переписать v1-зависимый код можно было бы иметь чистую картину, без кудрявостей. Мне кажется, такой подход может работать в реальных проектах, хотя он и «сложный».
Представим таблицу, строки которой соответствуют конкретным классам, реализующим IFigure, а столбцы — различным действиям, которые коду нужно выполнять с этими объектами.
Если столбцов мало, и они редко добавляются / меняются, а строк много, и они чаще добавляются / меняются, в линейном программном коде удобно группировать строки (реализовывать «естественный» подход, описанный выше). Полное описание строки — класса, реализующего IFigure, расположено в одном файле, где рядом сидит и рисование данной фигуры, и вывод на консоль, и вычисление площади… Немного разношёрстно, но зато — вот всё про эту фигуру, в одном месте! Правда, в случае с деревьями вложенных объектов логика обхода дерева объектов может оказаться многократно продублированной (для разных методов IFigure), но это не страшно, пока IFigure остаётся достаточно компактным и стабильным интерфейсом (т.е., повторяясь, когда в воображаемой таблице набор столбцов не слишком велик и достаточно стабилен).
Однако, если столбцов становится много, и они добавляются / меняются часто в сравнении с устоявшимся набором строк, группировка кода по столбцам становится более рациональным выбором. Визитор — хорошо известная и широко применяемая модель реализации этого выбора. Я встречаю успешное применение этой модели в работе, например, с синтаксическими деревьями или с деревьями вложенных объектов в графических диаграммах. Я встречал также неоднократно ситуации с безобразно разросшимися базовыми интерфейсами в отсутствии решения применить визитор.
То, что при первой встрече паттерн Визитор выглядит переусложнённым, неудивительно — структура классических ООП языков подталкивает к группировке по строкам, она как бы встраивается в арсенал программиста с первых шагов изучения ООП. Паттерны же вроде Визитора были изобретены и пере-изобретены для улучшения структуры кода в ситуациях, когда решения в лоб приводят к накапливающимся проблемам («разрастается в такое, что поддерживать становится невозможно»). Да, и, кстати, группировку по столбцам можно организовать и по-другому, в конкретной ситуации применение Визитора может быть, действительно, не самой удачной идеей. Тем не менее, последняя фраза вашего комментария («Отпинываться от ООП ради спорных идиологий и терять ресурсы на поддержке, это всё же пахнет глупым фанатизмом.») мне не кажется обоснованной без рассмотрения конкретных ситуаций. Повторюсь, имел дело с двумя широкими областями (синтаксический разбор, деловая графика) где использование Визитора вполне уместно и де-факто является стандартной для этих областей практикой.
… Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию
справа на левослева направо (справа от любой башенки стоит или башенка той же, или меньшей высоты).…Далее, кубики из руки выставляем
слевасправа от этой укороченной башенки…Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).
«Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)
https://habrahabr.ru/post/301104/
(типа, не спам — перевод интересного текста)