dynamic_cast вреден — почему?

это у него фетиш, надеюсь, скоро пройдет

Ладно, ты не хочешь понять, что «тип» сущности в предметной области отличен от типа представления сущности в языке программирования, что приведение типов следует применять если только а предметной области оно имеет смысл и применять его следует тогда явно, а не через приведение типов представлений, что профит от наследования можно получить только при общности поведения, что паттерны служат не для того чтоб они были, что у каждого паттерна есть область применимости, что паттерн визитор описан у банды четырех не так, как ты его понимаешь и применяешь. Хорошо. Но если хочешь, чтоб например я написал точно как надо было делать, набросай на джаве (можешь вместо реализаций написать словами что метод делает, но интерфейсы все изобрази точно), а то я в твоих юник птр-ах запутался.

Ты же в mipt учишься

Посмотрел на его аватарку и почему-то так и подумал...

У add_child()'ов и children() сигнатуры разные, т. к. в зависимости от типа узла к каждому потомку прилагаются свои «метаданные».

Тут ЯННП. Если создается нода, то кто то (типа порождающей ф-ии) знает как ее делать и возвращает какой нить пойнтер (умный пойнтер) базового типа. Откуда разные сигнатуры, откуда доп метаданные? Это решается на уровне порождения дерева.

Методы, определённые в Node::Value, специфичны именно для чисел — неужели нужно вытащить их в Node::Base и заставить возвращать boost::optional? И так везде.

Тут я понял;-) Допустим есть метод упростить (сложить/умножить чиселки если это возможно), и в зависимости от, метод возвращает либо Value, либо Base, но узлу (скажем узел +) нужно понять что у него за исходящие ветки (обе Value или хотя бы одна Base).

К сожалению, на плюсах тут все решения ИМНО условно кривые. Либо действительно cast, либо заводить метод проверки типа (что тот же каст). Но плюсы ИМНО не совсем для таких задач, на питоне это смотриться куда лаконичней.

На питоне в таких случаях идет проверка типа через isinstance, что по факту тот же RTTI - просто в итоге получается меньше букв. Ну и порождение дерева можно спихнуть на интерпретатор.

Так что все у Вас так, не слушайте местных аналитегов (и меня в т.ч.), на самом деле довольно трудно дать адекватный ответ не разобравшись в специфике конкретной задачи. Главное быть последовательным в своих заблуждениях!;-)

ЗЫ Вы уже распределились на кафедру? А то айда к нам!;-)

Конечно, есть. Проблема в том, что получается многословно и запутанно (когда, скажем, нужно принять решение на основе совокупности dynamic_cast'ов, говоря в терминах текущего кода).

Я повыкидывал лишние std::move(), остались только действительно необходимые ввиду семантики unique_ptr<> (и ввиду того ограничения, что copy elision работает только с объектами того же типа).

А кто сказал, что я успеваю и не ботаю сутками? :]

Тут ЯННП. <...> Откуда разные сигнатуры, откуда доп метаданные?

Так получилось, что у меня дерево не бинарное, а n-арное. Например, вместо узлов «плюс» и «минус», из которых строятся гирлянды произвольного уровня вложенности, существует понятие узла «плюс-минус», который описывает алгебраическую сумму. Соответственно, к каждому потомку приделан флаг отрицания. То же самое с произведением и делением, только там флаг «обратного числа».

Отсюда сигнатуры (примерно) add_child (Node::Base*, bool) и list<pair<Node::Base*, bool>>& children().

Наверное, можно ввести отдельный узел унарного отрицания (и унарного «приведения к обратному»). И потом заиметь те же самые касты при кодогенерации (в моём случае — при латехогенерации). Понятия не имею, как правильно.

ЗЫ Вы уже распределились на кафедру? А то айда к нам!;-)

Ну, до распределения ещё дожить надо (оно на третьем курсе)... Тем не менее, я вроде бы к параллельцам собрался. А что у вас за кафедра?

Так получилось, что у меня дерево не бинарное, а n-арное.

Ну... наверное это зависит от задач которые ставятся перед тулзой. Все таки классическое дерево, которое унарно/бинарное проще парсить (это можно отдать компилятору или интерпретатору), но с другой стороны м.б. проще какие то виды обработки с такими гирляндами.

Но есть же еще степень, и есть функции.

Ну, до распределения ещё дожить надо (оно на третьем курсе)... Тем не менее, я вроде бы к параллельцам собрался. А что у вас за кафедра?

https://sites.google.com/site/kiam81k/ www.linux.org.ru/wiki/en/User:AIv/LRnLA

Параллелизма у нас по самое небалуйся, для ряда задач у нас самые быстрые коды в мире;-)

В общем числодробилки. Смесь физики, прикладной математики и довольно специфического программирования/метапрограммирования.

А еще мы талончики на питание даем;-)

м.б. проще какие то виды обработки с такими гирляндами.

Вот упрощать выражение как раз легче получается с таким деревом.

В общем числодробилки.

Не-не-не, математику я ненавижу... Параллельцы — это Parallels, там виртуализация и прочий low-level.

Возможно.

Вы путаете математику и прикладную математику. В ПМ сплошь и рядом алгоритмы. Ну и в программировании тоже много математики, Вы просто видимо этого не осознаете:-)

алгоритмы

Их туда же. В программировании, безусловно, много математики, но передо мной стоит задача по оптимизации: выбрать такую область программирования, где её меньше всего. И computer science в решение этой задачи не входит :]

много математики, но передо мной стоит задача по оптимизации: выбрать такую область программирования, где её меньше всего

Любая байтосодомия. Например, embedded.

Пчелы против меда!:-)

Ну успехов Вам.

А вот мы на ПМ занимаемся одной М. Пока что. Диффуры там всякие, функан и ничего про алгоритмы... пока что

ну еще есть очень базовый курс с++

Ну это как бы фундамент... куды без него.

И конечно пока НИР-ом не займетесь алгоритмы будут только на каких то специальных курсах.

Хотя даже решение СЛАУ каким нить Гауссом это уже алгоритм:-)

Слегка оффтоп, просто стало интересно: а почему такие деревья не принято обрабатывать в «реляционном» стиле? Делаем из дерева «таблицу» (массив), добавляем немного избыточности (вот для примера из ОП пригодился бы level):

id  | parent | level | func | sign | param | ...
------------------------------------------------
 1  |    0   |   1   |   +  | false|       |
 2  |    1   |   2   | load | true |   a   |
 3  |    1   |   2   |   +  | true |       |
 4  |    3   |   3   | load | true |   b   |
 5  |    3   |   3   | load | true |   c   |

и уже по этой таблице переписываем (т.е. делаем rewriting). Таблицу можно удобно сортировать и группировать по нужным полям

Так же проще чем на каждое переписывающее правило придумывать свой алгоритм обхода и обработки, не?

Потому что статистика по дереву малоинтересна (и тривиально делается через тот же визитор). А вот со структурой дерева ковыряться... я хз как это в реляционном стиле сделать. Те понятно что сделать можно, но ИМНО будет ужасно выглядеть.

Подход плох хотя бы тем, что ты две операции с разными математическими свойствами объединяешь в одну. Еще удивляешься, что так рано к успеху пришел.

Семантика операций, образующих выражение, на данном этапе вообще скорее всего не важна. Только их математические свойства. Ах да, ты же ненавидишь математику.

Вот и не факт. Один из контрольных примеров для оптимизатора - сможет ли он полином привести к схеме горнера при вычислении?

А должен?

Мой не может, но нет никакой проблемы в том, чтобы это реализовать.

Сложение и вычитание — операции с разными свойствами? Сильно сомневаюсь.

Да и с приходом к успеху тоже всё в порядке — этот тред о гипотетических проблемах.

реализовать упрощение дерева по принципу a - (b + c) = a - b - c

в каком месте тут «упрощение»?

А должен?

должен. Потому что в схеме Горнера операций меньше.

Мой не может, но нет никакой проблемы в том, чтобы это реализовать.

ну значит у тебя ещё нет оптимизатора.

Мне нужно упрощать для человекочитаемости, а не для вычисления. Поэтому конкретно твой тухлый помидор совершенно не к месту.

Мне нужно упрощать для человекочитаемости, а не для вычисления.

тогда мне интересен критерий этой твоей «человкекочитаемости». А то для меня не очевидно, что a-(b+c) менее «читаемо», чем a-b-c. ИМХО всё зависит от природы этих a, b и c.

Поэтому конкретно твой тухлый помидор совершенно не к месту.

ну меня их много, т.ч. не переживай.

Критерий совершенно не важен. Вопросы, поднятые в этом треде, не зависят от конкретного набора преобразований, применяемых к дереву.

А вообще — конкретно это преобразование лишь упрощает реализацию других (например, «x - (x + y)» не особо соптимизируешь, а вот «x - x - y» уже сильно легче привести к "-y").

не особо соптимизируешь, а вот «x - x - y» уже сильно легче привести к "-y"

а если x-(y-y)? Вообще непонятно, как ты хранишь a-b-c? Наверное как (a-b)-c, да? Или у тебя есть тернанрная сумма(т.е. узел «+» с тремя потомками)?

Вопросы, поднятые в этом треде, не зависят от конкретного набора преобразований, применяемых к дереву.

если ты про динамик каст, то почему нет? Вполне себе ДА. Только есть одно но: не забудь проверить результат каста на NULL, а то каст возможен не всегда, и если каст зафейлился, то получится NULL. А если ты ссылки кастуешь, то нужно ловить исключение.

В твоём случае действительно можно попробовать найти все «суммы» и сложить их. Но я не понимаю, почему же «не для вычислений», а для чего? Как раз это нужно для вычислений, но вычисления ведь в два этапа проводятся,

1. время компиляции

2. рантайм.

Например на первом этапе можно константы посчитать: 2*x+3*x->5*x. Здесь есть две константы 2 и 3, и их нужно сложить. Предполагается, что x будет известен только на втором этапе.

А оптимизация «для красоты» ИМХО не нужна.

а если x-(y-y)

Здесь «y - y» можно легко обработать, и не раскрывая скобок. Но это простой случай.

Вообще непонятно, как ты хранишь a-b-c?

Выше по треду писал — у меня есть n-арные узлы суммы и произведения.

Только есть одно но: не забудь проверить результат каста на NULL

Да это-то понятно. Там и по смыслу каст возможен далеко не всегда.

Но я не понимаю, почему же «не для вычислений», а для чего?

Ну... вообще-то, для того, чтобы символьно посчитать по этому дереву кучу частных производных, возвести в квадрат-сложить-извлечь корень, отрендерить в латех, переписать в тетрадку и сдать грёбаную лабу. :]

Так что мне как раз нужна оптимизация «для красоты».

Выше по треду писал — у меня есть n-арные узлы суммы и произведения.

это плохой подход. Лучше выкинуть n-арные операции, оставить только бинарные.

Ну... вообще-то, для того, чтобы символьно посчитать по этому дереву кучу частных производных, возвести в квадрат-сложить-извлечь корень, отрендерить в латех, переписать в тетрадку и сдать грёбаную лабу. :]

производные и умножение — это всё вычисления. Просто далеко не всегда тебе известны все переменные, т.е. в качестве ответа ты не всегда можешь получить число. Часто ответ тоже имеет вид выражения.

Так что мне как раз нужна оптимизация «для красоты».

не получится. Понятие «красоты» не формализуется. Лучше будет заменить «красоту» на что-то конкретное, например на цену операции. Тогда ты можешь эту цену уменьшать. Но с n-арными операциями это сложно будет, если все операции бинарные, то рассчитать их общую цену несложно. Тогда выражение x+y-y будет иметь цену 2, а выражение x будет иметь цену 0. Оптимизируется это всё очень просто, а именно подобными членами, т.е. делишь любую сумму произведений на части: (1*x)+(1*y+(-1)y), выносишь неизвестные за скобки и _считаешь_ известные. При этом важно вовремя остановиться, например sqrt(3) считать не нужно, препод не оценит. Т.е. sqrt(const) это _другой_ _тип_ констант. Т.е. правильный ответ sqrt(3)*y+4*y==(sqrt(3)+4)*y, а вовсе не 5.73205080756887729352*y. Отрицательные степени тоже не нужно считать тем же типом, что и обычные числа: 1/7≠.14285714285714285714, так «не красиво».

это плохой подход.

Why? Не представляю, как можно внятно написать всё это на бинарных деревьях. Как определить понятие цены для n-арных операций — вполне себе очевидно: количество потомков минус один (можно ещё умножить на коэффициент).

Просто далеко не всегда тебе известны все переменные, т.е. в качестве ответа ты не всегда можешь получить число. Часто ответ тоже имеет вид выражения.

Естественно. Более того, мне в виде выражения ответ и нужен. Потому и говорю, что считаю символьно.

не получится. Понятие «красоты» не формализуется. Лучше будет заменить «красоту» на что-то конкретное

Да, это верно... Уже думал об этом. Но пока что все эвристики прокатывают, если их тупо применять одну за другой к целому дереву.

Оптимизируется это всё очень просто, а именно подобными членами

Уже (хотя пока что умею приводить только константы, т. е. x*y + x*z -> x*(y+z) сработает только если y и z — числа).

При этом важно вовремя остановиться, например sqrt(3) считать не нужно

Отрицательные степени тоже не нужно считать тем же типом, что и обычные числа

Действительно, надо это захэндлить, спасибо.

Отрицательные степени не надо считать тем же типом, что и константы... Надо захэндлить... Так постепенно придет понимание того, что дерево, являющееся представлением выражения, не есть само выражение. Понимание этого, а также понимание того, какие на самом деле типы выражений нужны избавит от проблем с кастом и от многих других.

Типы выражений. Слово кажется магической пустой болтовней. Но так ли это? Предположим, что ты можешь взять выражение, найти все правила оптимизации, которым оно удовлетворяет и построить итератор по всем выражениям, являющимся результатом применения одного из правил. Это только условно, на самом деле оптимизировать в конце концов будем не так, но пока логически можно считать, что так.

Схема оптимизации полностью определяет интерфейс каждого из типов выражений. Только по счастливому стечению обстоятельств в выражении могут оказаться функции доступа к операндам и оператору. Но они не ключевые. Интерфейс выражения наследуется от того, какова его роль в процессе оптимизации. Оно должно что-то уметь делать с собой? Оно должно представлять кому-то какую-то информацию о себе?

Покумекав и так и сяк ты обнаружишь, что некоторые операции должны вести себя почти одинаково в процессе оптимизации. Может конечно статься, что это плюс и минус, но опыт подсказывает, что это не так. И тогда в дело вступит наследование и все остальные полезные фишки ООП.

Некоторые шаблоны действительно понятно на интуитивно уровне когда применять, как применять, и можно это делать независимо друг от друга. И да, можно по счастливой случайности получить от их применения профита больше чем вреда. Но в большинстве случаев правило «потому что шаблон и потому что все так делают и потому что бест практис» не прокатывает. Нужно тщательно оценить получаемый профит и вред. Поначалу лучше вообще от шаблона отказаться, и только когда он явно вылезет, подрихтовать конструкцию под него. Хорошими книгами по теме являются книги Кириевски и (внезапно) книга Голуба - Holub on patterns😊