Comments 41
За статью и код - спасибо большое! Решаете важную проблему!
Тест из реальной жизни. В реальной жизни, когда требуется производительность, все выражения создают заранее, заранее привязывают параметры, транслируют всё так или иначе средствами библиотеки, и только потом многократно вызывают собственно вычисление выражения.
Тут же все создаётся с нуля каждый раз, а так делают при разовых нечастых вычислениях, где производительность вообще не критична.
Тест Не из реальной жизни*
Если выражения известны заранее, скорее всего ничего парсить не надо вовсе, все можно в коде написать. Но выражения могут строиться динамически, могут собираться из разных источников, могут приходить откуда-то извне.
Бенчмарк полностью валидный. Фреймворки созданы для парсинга и вычисления, их скорость и измеряется. Можно добавить еще бенчмарков для более частных случаев, описали бы сценарии для автора, если есть идеи.
Известны заранее - это известны в ран-тайме непосредственно перед первым и дальнейшими тысячами/миллионами вычислений. Могут иногда меняться и опять вычисляться очень много раз. Ну или приведите реальный пример, когда нужно читать откуда-то и вычислять тысячи/миллионы выражений, причём раждый раз разные. Причём так, чтобы это влияло на производительность приложения. Я не знаю, такого примера. А вот мой пример очень часто встречается.
Пошаговая игра, пропускаем ход - все объекты/эффекты/юниты и тд обходятся по графу и по каким-то там правилам собирается коллекция выражений, которая потом обрабатывается чтобы изменять состояние объектов. Строки собираются потому что в игре используются скрипты для кастомизации поведения и пользовательских настроек. Производительность важна, потому что игра динамичная: таймеры, интерфейс и придирчивая аудитория. Собираются и парсятся строки каждый ход, их не будут тысячи и миллионы, но десятки запросто, а в отдельных случаях может и сотни и они могут быть довольно сложными. Ну и если со стороны серверной части зайти, то игр может быть и 100к одновременно.
Или нам таблицы загружают с формулами в реальном времени, что там в них будет одному пользователю известно, а мы должны обсчитать и выдать результат какой-то там.
Сценарии из головы можно выдумывать сколько фантазии хватит, вопрос в другом. Вы вот делаете какой-то фреймворк, наверняка печетесь о производительности. Сидите алгоритмы изобретаете, оптимизируете, чтобы ваш парсинг быстрее работал. А тут кто-то приходит и говорит что в реальной жизни скорость парсинга не имеет значения, потому что в реальной жизни таких сценариев не бывает. Ну не знаю. Даже если б я лично не мог придумать реальных сценариев где нужна эта скорость, бенчмарки от этого бесполезными не становятся. Выигрыш по скорости и аллокации в 15-20 раз, это очень круто. Кто-то старался, работу со строками заменил на спаны, я склонен поприветствовать разрабов, кто бы они ни были, хотя мне на данный момент оно триста лет не надо.
Строки собираются потому что в игре используются скрипты для кастомизации поведения и пользовательских настроек.
Эти скрипты компилируются в момент загрузки и больше не меняются. Зачем тут каждый ход формировать какую-то там строку, а потом разбирать её?
Абсолютно. Это как раз мой случай. Вариант с таблицей не понял. Сколько там выражений? Как часто она загружается? Так критично - потратить 1 тысячную или 1 сотую секунды на вычисления?
Да все, в принципе, не критично в мире разработки. По сравнению с тем, что иногда встречается в коде такие пустяки действительно никого не волнуют. И зачем кому-то что-то может понадобиться тоже не всегда понятно. Вот я не могу придумать как бы я мог использовать IronPython. Загадочная штука для меня.
На объекте есть N активных эффектов. У каждого эффекта может быть какая-то обработка события: при получении урона, при пропуске хода, при розыгрыше карты, при движении и тд и тп. Эта обработка представляет из себя логику генерации куска (или кусков) выражения. Мы не можем обрабатывать эффекты по одному, потому что одни эффекты могут влиять на другие по каким-то правилам. Нам надо собрать результирующее выражение, чтобы просчитать все изменения, которые должны произойти с объектом по событию. Мы проходим по всем эффектам, у каждого берем релевантный обработчик (на этом этапе уже могут быть ветвления), соединяем все вместе и получаем промежуточный результат: некоторое выражение. Это выражение можно парсить и уже непосредственно вычислять результат, применив его к данным объекта. Учитывая количество возможных комбинаций и ветвлений логики, скорее всего два одинаковых выражения встречаться практически не будут и прекомпилировать ничего не выйдет. Кроме этого, у пользователя могут быть индивидуальные особенности, от какой-нибудь специализации, до именного подарочного нфт дающего уникальный эффект.
Всегда можно сделать одно и то же кучей разных способов, просили пример, пример довольно очевидный: там где выражение генерируется, а не берется из заранее известного хранилища, его очевидно нельзя прекомпилировать. Но всегда конечно можно придумать, как обойтись без выражений и без парсинга в принципе.
Мы проходим по всем эффектам, у каждого берем релевантный обработчик...
...который ничего не мешает подготовить (скомпилировать) заранее.
соединяем все вместе и получаем промежуточный результат: некоторое выражение
Зачем формировать одноразовое выражение вместо того, чтобы сразу получить результат? В этом нет никакого смысла.
А теперь вам сказали написать аналог Matlab. И сразу скорость интерпретации стала важной. Или business analytics какой.
Возможность компиляции математических выражений из строк была добавлена в MathEvaluator 2.0
Не хватает теста NCalc с заранее созданным выражением
В заранее скомпилированном выражении нельзя менять значения переменных, понятное дело что скомпилированное будет выполняться быстрее после компиляции, но компиляция требует времени. Если вам динамическое выражение необходимо выполнить всего один раз то без компиляции будет быстрее, если вам необходимо выполнить его 1 млн раз меняя значения переменных, например, строим график, то скомпилированное выражение вам не подойдёт. При производительности которой я добился выполнение 1 млн операций займёт 0.5 секунды, это более чем достаточно для подобных задач.
В смысле - нельзя менять значения переменных? А что мешает?
Вы прочитайте внимательно, речь идёт про компиляцию в NCalc. Я также могу добавить компиляцию во внутреннюю структуру но с возможностью изменять переменные, но пока это не в приоритете, в приоритете простота и расширяемость, в Ncalc такой возможности нет.
Зачем вообще компилировать выражение, если нет возможности потом запускать его несколько раз с разными параметрами? Это абсурд. Где компиляция, там и параметры.
В частности, пример передачи параметров в компилированное выражение есть в документации NCalc: https://ncalc.github.io/ncalc/articles/lambda_compilation.html
Вы человеку так все бенчмарки поломает :) после компиляции выражений у всех либ разница будет только в скорости паркинга и биндинга, что скорее всего большинство пользователей не интересует.
Btw у меня есть аналогичная либа с полным c# 3.5 синтаксисом и поддержкой AOT для unity
Я могу также попытаться обесценить вашу работу, особо не вдаваясь в подробности закинуть вопрос. Если время парсинга и компиляции не важны почему вы не использовали Roslyn или CodeDom для компиляции c# кода? Я уже не говорю про то что парснинг c# выражения ещё более узкий кейс чем то что поддерживает моя библиотека.
Если время парсинга и компиляции не важны почему вы не использовали Roslyn или CodeDom для компиляции c# кода?
По тому что они не работают везде, где может запускается Unity. Моим пользователям не важно время пасинга и биндинга т.к у них все практические кейсы в том что бы запарсить выражение из строки а потом вызывать миллионы раз. Например взять из конфига формулу
(damage, entity) => damage * (1 / entity.damageResistance) * (entity.immunity ? 0 : 1)скомпилировать в рантайме и потом много раз использовать.
Соотвественно проверять перфоманс на бенчмарке холодного старта не совсем корректно.
Стоило разбить на парсинг + биндинг и вычисление. Ну и мерить один запуск это мелко, стоит сделать 100.000 итераций + замерить сколько мусора будет создано в памяти.
Я могу также попытаться обесценить вашу работу,
Так что может быть проще? Добавьте его либу в свои бенчмарки!
Только, пожалуйста, вот этот сценарий, когда одно выражение вычисляется 100-1000-10000 раз с разными входными данными.
Как человеку, который уже 10+ лет участвует в разработке продукта, где вычисление выражений является краеугольным камнем, очень бы интересно было посмотреть, что у вас обоих получилось.
На вас все напали потому-что математические выражения должны компилироваться в бинарные деревья. А деревья можно выполнять сколь угодно много раз меняя значения переменных и даже операторы можно менять. И добавлять новые действия. Алгоритмы на деревьях позволяют делать очень многое и очень универсально и быстро.
А еще бинарные деревья выполняются за максимально возможное быстрое время. На данный момент даже в теории не существует наиболее быстрых алгоритмов вычислений математических выражений.
По этому все тут и возмущены почему компилированное выражение не может менять переменные итп.
Поизучайте алгоритмы и структуры данных. Они не такие страшные как про них говорят.
Путь, на котором сейчас находится автор (упорно не желая при этом двигаться дальше), я прошёл уже очень давно, несколько десятилетий назад. Когда тебе удаётся написать парсер арифметических выражений, начинаешь чувствовать себя чуть ли не повелителем Вселенной. Мой первый парсер вычислитель действительно был устроен примерно так же, то есть каждое вычисление выражение должно было предваряться синтаксическим разбором, на входе была строка выражения и значение переменной, на выходе - значение выражения. Назначение того вычислителя было совершенно конкретным - построение графиков функций, заданных формулами. Однако, поскольку дело было давно, довольно быстро стало понятно, что все это работает слишком медленно (хотя для того конкретного применения и тех компьютеров этого и было достаточно, однако на ум приходили и более сложные задачи). Поэтому, повторюсь, уже очень давно мой набор процедур для вычислений стал состоять из отдельного парсера, преобразующего строку во внутреннее представление (дерево), и отдельной процедуры вычисления значения выражения по заданным дереву и значениям переменных.
Бенчмарки однократного вычисления значения выражения, конечно же, абсолютно бессмысленны
Спасибо, желание двигаться дальше есть, но я двигаюсь в соответствии с приоритетом и наличием времени. Но люди хотят все и сразу и бесплатно, вместо того чтобы поддержать аргументированным советом я получаю комментарии в духе "я бы сделал или сделал лучше", на что и получают соответстветствующий ответ, поэтому у вас возможно сложилось впечатление что я не желаю двигаться дальше. К слову я делюсь этой информацией также на ресурсе medium.com и там я такого не наблюдаю, к слову, наблюдение толкающее сделать определённые выводы. Хотя должен отметить, впринципе комментариев здесь я получаю больше и иногда очень ценные, за что таким комментариям я благодарен. На это решение я потратил пока приемлемое количество времени и добавить компиляцию возможно, но пока не вижу поддержки и заинтересованности сообщества в этом чтобы потратить на эвалюатор ещё времени, так как есть и другие идеи требующие моего внимания. Но повторюсь, интерес есть, вопрос на сколько он приобладает над интересом к другим идеям пока не решил.
пока не вижу поддержки и заинтересованности сообщества в этом чтобы потратить на эвалюатор ещё времени
Чтобы получить поддержку и заинтересованность, вам бы не помешало создать какой-нибудь содержательный пример применения вашей библиотеки. Какой именно - я не знаю, но практически уверен, что попытка построения такого примера в виде программы почти наверняка привела бы к осознанию того, что компиляция и вычисление должны быть разделены
Кому интересно здесь есть описание алгоритма как быстро и просто скомпилировать бинарное дерево любого математического выражения. https://gitverse.ru/MaksMN/EvaluateString
Бинарное дерево позволяет делать абсолютно всё. Любые операторы, функции, переменные. Можно даже свой скриптовый язык сделать.
Ваш "быстрый" алгоритм работает за O(N²), в то время как алгоритм сортировочной станции справляется за O(N).
бинарное дерево вычисляется за O(n) так как при вычислении каждый узел посещается только 1 раз.
А вот преобразование строки в дерево может иметь ряд накладных расходов, потому-что надо сортировать операторы, а там уже всё зависит от алгоритмов сортировки в которых в худшем случае сложность может быть квадратичной.
Сборка дерева делается всего 1 раз после чего вы можете менять в нем значения операндов и вычислять его бесконечное количество раз за O(n).
Самая лучшая сортировка даст вам Ω(N log N), что всё ещё медленнее алгоритма сортировочной станции.
Я вообще не понимаю что вы придрались к этой сортировке? Она здесь не главное.
Главное тут дерево. Именно оно будет работать на продолжении всего жизненного цикла приложения. И только из него мы будем получать важные данные. И только оно будет влиять на скорость выполнения.
А способы получения дерева принципиально не важны. Оно собирается только 1 раз и процесс сборки перестанет нас волновать когда дерево полностью вырастет.
Конечно если у вас десятки сотни миллионов операторов, то вам надо позаботиться и об эффективной сортировке.
Я не являюсь автором дерева математических выражений. Его придумали за долго до моего рождения. Я вам показал пошаговые операции создания дерева, а как вы их будете реализовывать это уже ваши проблемы.
Это ваши слова?
Кому интересно здесь есть описание алгоритма как быстро и просто скомпилировать бинарное дерево любого математического выражения. https://gitverse.ru/MaksMN/EvaluateString
Если бы вы с самого начала писали про дерево - я бы с вами согласился, отделить разбор выражения от его вычисления и правда автору не помешает. Но вы написали более конкретный комментарий - про свой алгоритм построения дерева, назвав его быстрым. А он быстрым не является, все общепринятые алгоритмы разбора быстрее него.
Расскажите где можно почитать о разборе математической строки в дерево?
А то везде рассказывается только про само дерево и его структуре и нигде нет информации о том в какой последовательности его собирать.
Я немного прикинул и у меня вышло правило крайнего правого оператора с самым низким приоритетом.
Подскажите про другие способы разбора строки.
Я вам уже несколько раз написал: алгоритм сортировочной станции, статей про него в интернете полным-полно. Обычно его описывают как алгоритм преобразования из инфиксной формы в суффиксную (она же обратная польская нотация), но тривиальная доработка позволяет получить на выходе дерево.
Также можно использовать метод рекурсивного спуска, он муторнее, но в некотором смысле проще.
Наконец, в реальных задачах часто используют генераторы парсеров, вроде ANTLR, сгенерированный парсер на выходе даёт сразу дерево (хотя его настройка - то ещё приключение). Правда, это синтаксическое дерево, а не дерево выражений, но одно дерево в другое превращается тривиально.
По сути у меня и получилась сортировочная станция. Единственно отличие в том что я предлагаю все операторы кидать сначала в сортированный стек. А потом строить дерево когда все операнды и операторы раскиданы по стекам.
Я всегда считал что от этой сортировки можно уйти, но всё руки не доходили.
Ладно будем смотреть что там нам товарищ Дейкстра посоветует.
Подскажите пожалуйста является ли хорошей практикой строительство дерева от листьев к корню?
Я сейчас разобрался как во время обхода строки создать стек из которого можно построить дерево от корня к листьям. Но тогда получается что-то похожее на O(2n)
Проход по строке создаст стек
Создание дерева из полученного стека
А если дерево строить прямо в процессе обхода строки то получится O(n) но дерево строить придется от листов к корню.
Хотя с другой стороны получается в самом обходе будет больше операций. Дерево будет строится параллельно. Проход по строке будет включать одновременно и создание стека и дерева сразу. Какие-то временные данные все равно придется кидать в стек.
Вот теперь в раздумьях.
Подскажите пожалуйста является ли хорошей практикой строительство дерева от листьев к корню?
Это единственный нормальный способ строить деревья выражений.
Но тогда получается что-то похожее на O(2n)
O(2n) и O(n) - это одно и то же
Какие-то временные данные все равно придется кидать в стек.
Разумеется. Без стека можно парсить только регулярные языки (т.е. языки, которые полностью описываются регулярными выражениями).
Вычисление логического выражения из строки в C# (.NET)