В этой статье я продемонстрирую, как динамически вычислять логические математические выражения из строк в C#, с высокой производительностью. Решение, реализованное с использованием библиотеки .NET MathEvaluator, поддерживает логические операции в различных математических контекстах, включая программирование, научные вычисления и C#. Кроме того, библиотека позволяет расширять эти контексты, а также добавлять пользовательские переменные и функции.
Библиотека MathEvaluator и ее документация доступны на GitHub.
В предыдущей статье я уже подробно описал реализацию и методы быстрого вычисления математических выражений в C#. Здесь я сосредоточусь на конкретном случае вычисления логических выражений и сравню возможности и производительность MathEvaluator с известной библиотекой NCalc.
Поддерживаемые математические функции, операторы и константы
Библиотека MathEvaluator включает встроенные контексты для оценки сложных научных, программных и C# математических выражений. Она предлагает набор функций, операторов и констант, адаптированных к этим специфическим контекстам. Для получения полного списка поддерживаемых функций и возможностей, обратитесь к документации. При оценке логического выражения, если функция возвращает значение 0.0, оно интерпретируется как false, а любое другое значение считается true, также ведет себя функция Convert.ToBoolean предоставляемая .NET.
Сравнение с NCalc
Мы будем использовать BenchmarkDotNet для сравнения производительности. Подробности окружения:
BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.4037/23H2/2023Update/SunValley3)
11th Gen Intel Core i7-11800H 2.30GHz, 1 CPU, 16 logical and 8 physical cores
.NET SDK 8.0.300
[Host] : .NET 6.0.30 (6.0.3024.21525), X64 RyuJIT AVX2
.NET 6.0 : .NET 6.0.30 (6.0.3024.21525), X64 RyuJIT AVX2
.NET 8.0 : .NET 8.0.5 (8.0.524.21615), X64 RyuJIT AVX-512F+CD+BW+DQ+VL+VBMIПример 1: Вычисление логического программного выражения.
Сравним производительность вычисления логического выражения A or not B and (C or B):
BenchmarkRunner.Run<Benchmarks>();
[SimpleJob(RuntimeMoniker.Net80)]
[SimpleJob(RuntimeMoniker.Net60)]
[MemoryDiagnoser]
public class Benchmarks
{
private readonly ProgrammingMathContext _context = new();
private int _count;
[Benchmark(Description = "MathEvaluator")]
public bool MathEvaluator_EvaluateBoolean_ProgrammingExpression()
{
_count++;
bool a = _count % 2 == 0; //randomizing values
return "A or not B and (C or B)"
.SetContext(_context)
.BindVariable(a, "A")
.BindVariable(!a, "B")
.BindVariable(a, "C")
.EvaluateBoolean();
}
[Benchmark(Description = "NCalc")]
public bool NCalc_Evaluate_ProgrammingExpression()
{
_count++;
bool a = _count % 2 == 0; //randomizing values
var expression = new Expression("A or not B and (C or B)");
expression.Parameters["A"] = a;
expression.Parameters["B"] = !a;
expression.Parameters["C"] = a;
return (bool)expression.Evaluate();
}
}Ниже приведены результаты сравнения производительности:
Пример 2: Вычисление логического алгебраического выражения.
NCalc не поддерживает логические алгебраические выражения, такие как A∨¬B∧(C∨B). В отличие от неё, MathEvaluator может вычислить такие выражения и может быть расширен с помощью пользовательских математических контекстов, так как MathEvaluator следует простым математическим правилам основанным на приоритете операторов добавление других контекстов не вызывает сложности.
Рассмотрим пример создания контекста, поддерживающего логические алгебраические выражения:
using MathEvaluation.Context;
public class BooleanAlgebraMathContext : MathContext
{
public BooleanAlgebraMathContext()
{
static double andFn(double leftOperand, double rigntOperand)
=> leftOperand != default && rigntOperand != default ? 1.0 : default;
BindOperator(andFn, '∧', (int)EvalPrecedence.LogicalAnd);
static double orFn(double leftOperand, double rigntOperand)
=> leftOperand != default || rigntOperand != default ? 1.0 : default;
BindOperator(orFn, '∨', (int)EvalPrecedence.LogicalOr);
static double xorFn(double leftOperand, double rigntOperand)
=> leftOperand != default ^ rigntOperand != default ? 1.0 : default;
BindOperator(xorFn, '⊕', (int)EvalPrecedence.LogicalXor);
static double logicalNegationFn(double rigntOperand)
=> rigntOperand == default ? 1.0 : default;
BindConverter(logicalNegationFn, '¬');
}
}Измерим производительность вычисления выражения A∨¬B∧(C∨B) с использованием вновь созданного класса BooleanAlgebraMathContext:
BenchmarkRunner.Run<Benchmarks>();
[SimpleJob(RuntimeMoniker.Net80)]
[SimpleJob(RuntimeMoniker.Net60)]
[MemoryDiagnoser]
public class Benchmarks
{
private readonly BooleanAlgebraMathContext _context = new();
private int _count;
[Benchmark(Description = "MathEvaluator")]
public bool MathEvaluator_EvaluateBoolean_ProgrammingExpression()
{
_count++;
bool a = _count % 2 == 0; //randomizing values
return "A∨¬B∧(C∨B)"
.SetContext(_context)
.BindVariable(a, "A")
.BindVariable(!a, "B")
.BindVariable(a, "C")
.EvaluateBoolean();
}
}Ниже приведены результаты измерения производительности:
Пример 3: Вычисление математического выражения на C#.
Сравним производительность вычисления сложного логического выражения A!= !B || A == C && false ^ -2.9 >= -12.9 + 0.1 / 0.01:
BenchmarkRunner.Run<Benchmarks>();
[SimpleJob(RuntimeMoniker.Net80)]
[SimpleJob(RuntimeMoniker.Net60)]
[MemoryDiagnoser]
public class Benchmarks
{
private readonly DotNetStandartMathContext _context = new();
private int _count;
[Benchmark(Description = "MathEvaluator")]
public bool MathEvaluator_EvaluateBoolean_ProgrammingExpression()
{
_count++;
bool a = _count % 2 == 0; //randomizing values
return "A != !B || A == C && false ^ -2.9 >= -12.9 + 0.1 / 0.01"
.SetContext(_context)
.BindVariable(a, "A")
.BindVariable(!a, "B")
.BindVariable(a, "C")
.EvaluateBoolean();
}
[Benchmark(Description = "NCalc")]
public bool NCalc_Evaluate_ProgrammingExpression()
{
_count++;
bool a = _count % 2 == 0; //randomizing values
var str = "A != !B || A == C && false ^ -2.9 >= -12.9 + 0.1 / 0.01";
var expression = new Expression(str);
expression.Parameters["A"] = a;
expression.Parameters["B"] = !a;
expression.Parameters["C"] = a;
return Convert.ToBoolean(expression.Evaluate());
}
}Ниже приведены результаты сравнения производительности:
Пример 4: Вычисление пользовательской логической функции.
Рассмотрим, как расширить программный контекст для поддержки дополнительных логических функций. Например, создадим функцию if, которая принимает три аргумента: первый — это условие, второй указывает, что возвращать, если условие истинно, и третий определяет, что возвращать, если оно ложно:
var context = new ProgrammingMathContext();
context.BindFunction((c, v1, v2) => c != 0.0 ? v1 : v2, "if");
var a = 2.0;
var result = "if(3 % a = 1, true, false)"
.SetContext(context)
.BindVariable(a)
.EvaluateBoolean();Заключение
Библиотека MathEvaluator — это мощный и гибкий инструмент для вычиления логических математических выражений в различных контекстах. Независимо от того, нужно ли вам обрабатывать логические операции в программировании, научные вычисления или выражения на C#, MathEvaluator обеспечивает превосходную производительность и расширяемость по сравнению с альтернативными решениями.
Если вы считаете этот проект ценным, рассмотрите возможность спонсирования меня на GitHub.
Спасибо! Если у вас есть идеи или предложения, пожалуйста, оставьте их в комментариях.
Комментарии (24)
dyadyaSerezha
20.08.2024 21:09+1Тест из реальной жизни. В реальной жизни, когда требуется производительность, все выражения создают заранее, заранее привязывают параметры, транслируют всё так или иначе средствами библиотеки, и только потом многократно вызывают собственно вычисление выражения.
Тут же все создаётся с нуля каждый раз, а так делают при разовых нечастых вычислениях, где производительность вообще не критична.
Proscrito
20.08.2024 21:09+1Если выражения известны заранее, скорее всего ничего парсить не надо вовсе, все можно в коде написать. Но выражения могут строиться динамически, могут собираться из разных источников, могут приходить откуда-то извне.
Бенчмарк полностью валидный. Фреймворки созданы для парсинга и вычисления, их скорость и измеряется. Можно добавить еще бенчмарков для более частных случаев, описали бы сценарии для автора, если есть идеи.
dyadyaSerezha
20.08.2024 21:09+1Известны заранее - это известны в ран-тайме непосредственно перед первым и дальнейшими тысячами/миллионами вычислений. Могут иногда меняться и опять вычисляться очень много раз. Ну или приведите реальный пример, когда нужно читать откуда-то и вычислять тысячи/миллионы выражений, причём раждый раз разные. Причём так, чтобы это влияло на производительность приложения. Я не знаю, такого примера. А вот мой пример очень часто встречается.
Proscrito
20.08.2024 21:09Пошаговая игра, пропускаем ход - все объекты/эффекты/юниты и тд обходятся по графу и по каким-то там правилам собирается коллекция выражений, которая потом обрабатывается чтобы изменять состояние объектов. Строки собираются потому что в игре используются скрипты для кастомизации поведения и пользовательских настроек. Производительность важна, потому что игра динамичная: таймеры, интерфейс и придирчивая аудитория. Собираются и парсятся строки каждый ход, их не будут тысячи и миллионы, но десятки запросто, а в отдельных случаях может и сотни и они могут быть довольно сложными. Ну и если со стороны серверной части зайти, то игр может быть и 100к одновременно.
Или нам таблицы загружают с формулами в реальном времени, что там в них будет одному пользователю известно, а мы должны обсчитать и выдать результат какой-то там.
Сценарии из головы можно выдумывать сколько фантазии хватит, вопрос в другом. Вы вот делаете какой-то фреймворк, наверняка печетесь о производительности. Сидите алгоритмы изобретаете, оптимизируете, чтобы ваш парсинг быстрее работал. А тут кто-то приходит и говорит что в реальной жизни скорость парсинга не имеет значения, потому что в реальной жизни таких сценариев не бывает. Ну не знаю. Даже если б я лично не мог придумать реальных сценариев где нужна эта скорость, бенчмарки от этого бесполезными не становятся. Выигрыш по скорости и аллокации в 15-20 раз, это очень круто. Кто-то старался, работу со строками заменил на спаны, я склонен поприветствовать разрабов, кто бы они ни были, хотя мне на данный момент оно триста лет не надо.
mayorovp
20.08.2024 21:09Строки собираются потому что в игре используются скрипты для кастомизации поведения и пользовательских настроек.
Эти скрипты компилируются в момент загрузки и больше не меняются. Зачем тут каждый ход формировать какую-то там строку, а потом разбирать её?
dyadyaSerezha
20.08.2024 21:09Абсолютно. Это как раз мой случай. Вариант с таблицей не понял. Сколько там выражений? Как часто она загружается? Так критично - потратить 1 тысячную или 1 сотую секунды на вычисления?
Proscrito
20.08.2024 21:09Да все, в принципе, не критично в мире разработки. По сравнению с тем, что иногда встречается в коде такие пустяки действительно никого не волнуют. И зачем кому-то что-то может понадобиться тоже не всегда понятно. Вот я не могу придумать как бы я мог использовать IronPython. Загадочная штука для меня.
dyadyaSerezha
20.08.2024 21:09Ну хотя бы для того, чтобы научиться правильно произносить слово iron :) (нет, это не айрон)
Proscrito
20.08.2024 21:09На объекте есть N активных эффектов. У каждого эффекта может быть какая-то обработка события: при получении урона, при пропуске хода, при розыгрыше карты, при движении и тд и тп. Эта обработка представляет из себя логику генерации куска (или кусков) выражения. Мы не можем обрабатывать эффекты по одному, потому что одни эффекты могут влиять на другие по каким-то правилам. Нам надо собрать результирующее выражение, чтобы просчитать все изменения, которые должны произойти с объектом по событию. Мы проходим по всем эффектам, у каждого берем релевантный обработчик (на этом этапе уже могут быть ветвления), соединяем все вместе и получаем промежуточный результат: некоторое выражение. Это выражение можно парсить и уже непосредственно вычислять результат, применив его к данным объекта. Учитывая количество возможных комбинаций и ветвлений логики, скорее всего два одинаковых выражения встречаться практически не будут и прекомпилировать ничего не выйдет. Кроме этого, у пользователя могут быть индивидуальные особенности, от какой-нибудь специализации, до именного подарочного нфт дающего уникальный эффект.
Всегда можно сделать одно и то же кучей разных способов, просили пример, пример довольно очевидный: там где выражение генерируется, а не берется из заранее известного хранилища, его очевидно нельзя прекомпилировать. Но всегда конечно можно придумать, как обойтись без выражений и без парсинга в принципе.mayorovp
20.08.2024 21:09Мы проходим по всем эффектам, у каждого берем релевантный обработчик...
...который ничего не мешает подготовить (скомпилировать) заранее.
соединяем все вместе и получаем промежуточный результат: некоторое выражение
Зачем формировать одноразовое выражение вместо того, чтобы сразу получить результат? В этом нет никакого смысла.
shai_hulud
20.08.2024 21:09+1Человек хочет комбинировать выражения вместо комбинации функций. Зачем? Хз. На FPS это влияет отрицательно, на сложность отладки и разработки тоже, из положительного только "крутость" решения.
Deosis
20.08.2024 21:09Не хватает теста NCalc с заранее созданным выражением
AntonAntonov88 Автор
20.08.2024 21:09В заранее скомпилированном выражении нельзя менять значения переменных, понятное дело что скомпилированное будет выполняться быстрее после компиляции, но компиляция требует времени. Если вам динамическое выражение необходимо выполнить всего один раз то без компиляции будет быстрее, если вам необходимо выполнить его 1 млн раз меняя значения переменных, например, строим график, то скомпилированное выражение вам не подойдёт. При производительности которой я добился выполнение 1 млн операций займёт 0.5 секунды, это более чем достаточно для подобных задач.
mayorovp
20.08.2024 21:09В смысле - нельзя менять значения переменных? А что мешает?
AntonAntonov88 Автор
20.08.2024 21:09Вы прочитайте внимательно, речь идёт про компиляцию в NCalc. Я также могу добавить компиляцию во внутреннюю структуру но с возможностью изменять переменные, но пока это не в приоритете, в приоритете простота и расширяемость, в Ncalc такой возможности нет.
mayorovp
20.08.2024 21:09Зачем вообще компилировать выражение, если нет возможности потом запускать его несколько раз с разными параметрами? Это абсурд. Где компиляция, там и параметры.
В частности, пример передачи параметров в компилированное выражение есть в документации NCalc: https://ncalc.github.io/ncalc/articles/lambda_compilation.html
shai_hulud
20.08.2024 21:09Вы человеку так все бенчмарки поломает :) после компиляции выражений у всех либ разница будет только в скорости паркинга и биндинга, что скорее всего большинство пользователей не интересует.
Btw у меня есть аналогичная либа с полным c# 3.5 синтаксисом и поддержкой AOT для unity
AntonAntonov88 Автор
20.08.2024 21:09+1Я могу также попытаться обесценить вашу работу, особо не вдаваясь в подробности закинуть вопрос. Если время парсинга и компиляции не важны почему вы не использовали Roslyn или CodeDom для компиляции c# кода? Я уже не говорю про то что парснинг c# выражения ещё более узкий кейс чем то что поддерживает моя библиотека.
shai_hulud
20.08.2024 21:09+1Если время парсинга и компиляции не важны почему вы не использовали Roslyn или CodeDom для компиляции c# кода?
По тому что они не работают везде, где может запускается Unity. Моим пользователям не важно время пасинга и биндинга т.к у них все практические кейсы в том что бы запарсить выражение из строки а потом вызывать миллионы раз. Например взять из конфига формулу
(damage, entity) => damage * (1 / entity.damageResistance) * (entity.immunity ? 0 : 1)скомпилировать в рантайме и потом много раз использовать.
Соотвественно проверять перфоманс на бенчмарке холодного старта не совсем корректно.
Стоило разбить на парсинг + биндинг и вычисление. Ну и мерить один запуск это мелко, стоит сделать 100.000 итераций + замерить сколько мусора будет создано в памяти.
belch84
20.08.2024 21:09Путь, на котором сейчас находится автор (упорно не желая при этом двигаться дальше), я прошёл уже очень давно, несколько десятилетий назад. Когда тебе удаётся написать парсер арифметических выражений, начинаешь чувствовать себя чуть ли не повелителем Вселенной. Мой первый
парсервычислитель действительно был устроен примерно так же, то есть каждое вычисление выражение должно было предваряться синтаксическим разбором, на входе была строка выражения и значение переменной, на выходе - значение выражения. Назначение того вычислителя было совершенно конкретным - построение графиков функций, заданных формулами. Однако, поскольку дело было давно, довольно быстро стало понятно, что все это работает слишком медленно (хотя для того конкретного применения и тех компьютеров этого и было достаточно, однако на ум приходили и более сложные задачи). Поэтому, повторюсь, уже очень давно мой набор процедур для вычислений стал состоять из отдельного парсера, преобразующего строку во внутреннее представление (дерево), и отдельной процедуры вычисления значения выражения по заданным дереву и значениям переменных.Бенчмарки однократного вычисления значения выражения, конечно же, абсолютно бессмысленны
AntonAntonov88 Автор
20.08.2024 21:09Спасибо, желание двигаться дальше есть, но я двигаюсь в соответствии с приоритетом и наличием времени. Но люди хотят все и сразу и бесплатно, вместо того чтобы поддержать аргументированным советом я получаю комментарии в духе "я бы сделал или сделал лучше", на что и получают соответстветствующий ответ, поэтому у вас возможно сложилось впечатление что я не желаю двигаться дальше. К слову я делюсь этой информацией также на ресурсе medium.com и там я такого не наблюдаю, к слову, наблюдение толкающее сделать определённые выводы. Хотя должен отметить, впринципе комментариев здесь я получаю больше и иногда очень ценные, за что таким комментариям я благодарен. На это решение я потратил пока приемлемое количество времени и добавить компиляцию возможно, но пока не вижу поддержки и заинтересованности сообщества в этом чтобы потратить на эвалюатор ещё времени, так как есть и другие идеи требующие моего внимания. Но повторюсь, интерес есть, вопрос на сколько он приобладает над интересом к другим идеям пока не решил.
belch84
20.08.2024 21:09пока не вижу поддержки и заинтересованности сообщества в этом чтобы потратить на эвалюатор ещё времени
Чтобы получить поддержку и заинтересованность, вам бы не помешало создать какой-нибудь содержательный пример применения вашей библиотеки. Какой именно - я не знаю, но практически уверен, что попытка построения такого примера в виде программы почти наверняка привела бы к осознанию того, что компиляция и вычисление должны быть разделены
OBIEESupport
За статью и код - спасибо большое! Решаете важную проблему!