Да-да, и мне физическая модель в голове помогает иногда понять математическую задачу, хотя я учился на математика (а стал программистом). С башнями из кубиков — я хотел обеспечить как можно более медленное опускание центра тяжести конструкции из самого высокого положения (для одной башенки из N кубиков) в самое низкое (для N башенок из одного кубика).
Поправки к №2 (конец дня, напутал лево / право в паре мест):
… Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на левослева направо (справа от любой башенки стоит или башенка той же, или меньшей высоты).…
Далее, кубики из руки выставляем слевасправа от этой укороченной башенки…
Для полноты описания к первому шагу следовало бы добавить условие остановки работы алгоритма (присутствующее неявно). Можно сформулировать так, например:
Рассмотреть подмассив от первого до предпоследнего элемента; если он пуст (в исходном массиве — всего один элемент), заврешить работу.
Если же он не пуст, двигаться по подмассиву справа налево по равным элементам, остановившись на последнем из них «x» (движение справа налево по равным элементам мне кажется более естественным, чем поиск «первого минимального» при движении слева направо).
Мне кажется «более естественной», опять же, генерация в обратном порядке — начиная с разложения N в одно слагаемое (равное N) — возможно, потому что именно это решение мне придумалось (я сейчас вспомнил, что когда-то решал эту задачу). Наглядно удобно представить это первое разложение как башню, составленную из поставленных в стопку N кубиков. Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию справа на лево (справа от любой башенки стоит или башенка той же, или меньшей высоты).
Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).
«Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)
Ищу на Хабре, где я с кем-то разговаривал на эти темы. Короче, навсяк, ссылка:
https://habrahabr.ru/post/301104/
(типа, не спам — перевод интересного текста)
Согласен, но это один из разумных компромиссов для тех случаев, когда Lock в каждом модифицирующем методе — дорог по производительности. Бескомпромисный вариант — делать все структуры данных, разделяемые между потоками, immutable, с единственным корнем, который обновляется atomic операцией. Но это тоже дорого иногда (из-за дороговизны immutable версий сложных структур данных).
Вариант: каждый тип — struct (чтобы успокоить себя насчёт производительности) со всеми полями readonly и удобным набором конструкторов. Все методы — чистые (можно для единообразия делать их все extension-методами, пополняя набор методов без вмешательства в определение struct-«ядра» библиотеки; дополнительный плюс такого правила — обязательное именование this параметра в реализации каждого такого extension-метода, как хочет автор этого поста); те из них, которые «мутаторы», возвращают новую («преобразованную») копию struct this-параметра (первого параметра в реализации extension-метода). Бонус: при такой дисциплине цепочечный синтаксис обеспечен для каждого типа «из коробки»: myS = myS.Transform1().Transform2().Transform3();. Лишнее копирование полей this-параметра в локальные переменные не требуется, дисциплина обеспечивает иммьютабельность автоматически. Правила для поддержания этой дисциплины при статической проверке вроде бы должны быть несложными.
В C++ есть идиома с вызовом Swap в конце метода, хорошо сочетается с идиомой pImpl (данные объекта хранятся в отдельном блоке — «реализации», а сам объект — «фасад» — обёртка над смартпойнером на этот блок). Дополнительные бонусы — простая дисциплина потоковой безопасности (надо позаботиться только о безопасности Swap) и сильная безопасность по исключениями (объект никогда не остаётся в некорректном «смешанном» состоянии, если посреди метода происходит исключение, при этом требование noexcept необходимо только для Swap). Эта идиома полуофициально поддерживается в STL (см. реализацию stl::swap для классов библиотеки плюс для POD типов).
При использовании этой идиомы дисциплину можно организовать такую. Объекты-реализации никогда не имеют методов, меняющих состояние, но, зато, имеют достаточно богатые наборы конструкторов. Основное тело метода объекта public API (фасада соответствующего объекта-реализации) состоит в построении новой версии объекта-реализации (при этом копировать поля текущего объекта в локальные переменные, как у автора поста, смысла нет — компилятор в помощь, поскольку pImpl-смартпойнтер фасада указывает на константный объект, да и все методы объекта-реализации помечены const). Эта часть метода завершается вызовом конструктора нового объекта-реализации, с сохранением указателя на него в локальную переменную — такой же смартпойнтер, как pImpl. Заключительный оператор метода — swap (std::swap, для единообразия) этой переменной и единственного поля фасада — pImpl.
Кстати, роль явного this (как у автора поста) здесь играет необходимость обращаться к реализации через единственное поле фасада — pImpl.
Дополнительная стоимость такого подхода, применяемого строго, понятна — но в каких-то применениях она оправдана, а узкие по производительности места можно и подрихтовать, если надо.
Упоминание auto_ptr («в грядущем переиздании») не рулит. Если вы можете повлиять на редактуру, сделайте, пожалуйста, сноску о том, что этот смарпойнтер is getting deprecated (replaced by unique_ptr) — или, ещё лучше, просто молча замените на unique_ptr. Автор одобрит, я уверен.
Приведу пример про ошибки с непарностью new / delete с [] и без: «неопределённое поведение» в стандарте объявлено всегда, а на практике компиляторы (я даже подозреваю, _все_ компиляторы) оптимизируют код для типов без деструкторов так, что разницы нет. Т.е. в данном случае мы имеем ситуацию «неопределённое поведение в реальном мире: всё работает без проблем», не знаю уж, к счастью или к несчастью. Нехорошая ошибка в коде есть. Теоретически (и практически, если удастся найти компилятор, который не делает вышеобозначенную оптимизацию) всё плохо. Всё становится действительно плохо, когда кому-то захочется отмодифицировать код, заменив тип элемента без деструктора на тип с деструктором. В этот момент этот программист и наступит на заботливо разложенные грабли (и, вероятно, разберётся и пофиксает). Но, пока этого не произошло, «все работает ЗАМЕЧАТЕЛЬНО!» :(.
"прочитаю — доложусь" — давай! Я буду тебе напоминать.
"Очень странная разметка у тебя :)" — у них тут какой-то агрессивный markdown. Я всего лишь поставил то ли два, то ли три пробела в начале двух параграфов "попроще: ..." и "посложнее: ..." и, видимо, эти пробелы послужили сигналами, что я цитирую код или что-то такое. Потом, почему английский подхватился жирным, а после // пошло сереньким синтезированным италиком, ну, я не хочу даже разбираться (посты здесь не пишу, нет смысла инвестировать внимание в это).
Спасибо Семён! Я статью из Nature распечатал ещё тогда и просмотрел по диагонали, но не изучил. Ты пишешь очень доходчиво.
По делу — с точки зрения отличия от "настоящего" AI у меня к AlphaGo две претензии / предложения, попроще и посложнее:
попроще: было бы интересно узнать, во сколько раз больше вычислительных ресурсов потребовалось бы, чтобы натренировать сети до такого же отличного уровня игры чисто через игры с самой собой, без обучения на большой базе игр экспертов (ты про этот аспект написал, кстати? вроде не вижу...);
посложнее: параметры системы (картинки-таблицы в твоей статье: топология сетей и параметры MCTS) тоже люди же подбирали, не само выросло... Вот эти дела чтобы самовыводились, это интересная (и гораздо более ресурсоёмкая) задача. Ты читал / слышал про General Game World Championships? http://www.general-game-playing.de/ (почему-то с 2011 года соревнования не проводились... Но сайт обновляется!)
про последний вопрос на тему robo advisory — абсолютно согласен с Дмитрием — на собственном опыте, кстати. Условно говоря, надираловка от конкретной фирмы (в моём случае — Швабс) в красивой обёртке. Подробности письмом.
Капитан Очевидность (TL;DR): матричный вариант всех ест с хрустом на завтрак. Господа, матрицы не причём, вопрос в том, используется возможность человеческого мозга абстрагировть, или нет.
«Это означает, что некоторые проблемы ES5, на которые разработчики жаловались годами так же никуда не денутся.» — странно, этот вопрос можно было бы решить расширением режима strict, типа strict6.
«В ES6 добавили очень нужные JavaScript-разработчикам шутки...» — абсолютно за, без чувства юмора определённого сорта программировать на JavaScript невозможно! Очень хорошо, что юмор теперь стандартизован!
… Как и в вашем решении, слагаемые всегда будут отсортированы по невозрастанию
справа на левослева направо (справа от любой башенки стоит или башенка той же, или меньшей высоты).…Далее, кубики из руки выставляем
слевасправа от этой укороченной башенки…Далее, работая над новым разложением, делаем следующее: двигаясь справа налево, собираем в руку все башенки единичной высоты, пока не наткнёмся на башенку неединичной высоты (если таковой нет — конец работы). У этой башенки снимем в руку верхний кубик. Далее, кубики из руки выставляем слева от этой укороченной башенки рядом башенок той же, как укороченная, высоты, плюс ноль или одна высотой меньше (если такая есть, её высота — остаток от деления количества кубиков в руке на высоту укороченной башенки).
«Физический смысл» — разложения на слагаемые генерируются в обратном лексикографическом порядке (у вас же — в прямом). В системе башенок — слове из неувеличивающихся по номеру букв (чисел-слагаемых) — находим самую правую букву, которую можно заменить на предыдущую (число на один меньшее), сохраняя сортировку букв в слове. Хвост нового слова после замены этой буквы должен состоять из букв не старше уменьшенной, при этом быть как можно дальше в словаре, поэтому мы и повторяем эту уменьшенную букву как можно дольше, а потом выкладывает букву-остаток. Процесс выстроен так, чтобы при лексикографической сортировке мы не пропускаем ни одного слова, сохраняя два инварианта (сумму букв и отсортированность букв)
https://habrahabr.ru/post/301104/
(типа, не спам — перевод интересного текста)
При использовании этой идиомы дисциплину можно организовать такую. Объекты-реализации никогда не имеют методов, меняющих состояние, но, зато, имеют достаточно богатые наборы конструкторов. Основное тело метода объекта public API (фасада соответствующего объекта-реализации) состоит в построении новой версии объекта-реализации (при этом копировать поля текущего объекта в локальные переменные, как у автора поста, смысла нет — компилятор в помощь, поскольку pImpl-смартпойнтер фасада указывает на константный объект, да и все методы объекта-реализации помечены const). Эта часть метода завершается вызовом конструктора нового объекта-реализации, с сохранением указателя на него в локальную переменную — такой же смартпойнтер, как pImpl. Заключительный оператор метода — swap (std::swap, для единообразия) этой переменной и единственного поля фасада — pImpl.
Кстати, роль явного this (как у автора поста) здесь играет необходимость обращаться к реализации через единственное поле фасада — pImpl.
Дополнительная стоимость такого подхода, применяемого строго, понятна — но в каких-то применениях она оправдана, а узкие по производительности места можно и подрихтовать, если надо.
"Очень странная разметка у тебя :)" — у них тут какой-то агрессивный markdown. Я всего лишь поставил то ли два, то ли три пробела в начале двух параграфов "попроще: ..." и "посложнее: ..." и, видимо, эти пробелы послужили сигналами, что я цитирую код или что-то такое. Потом, почему английский подхватился жирным, а после // пошло сереньким синтезированным италиком, ну, я не хочу даже разбираться (посты здесь не пишу, нет смысла инвестировать внимание в это).
По делу — с точки зрения отличия от "настоящего" AI у меня к AlphaGo две претензии / предложения, попроще и посложнее:
«В ES6 добавили очень нужные JavaScript-разработчикам шутки...» — абсолютно за, без чувства юмора определённого сорта программировать на JavaScript невозможно! Очень хорошо, что юмор теперь стандартизован!