Для улучшения возможностей научных вычислений в C# я реализовал evaluator, способный вычислить любое математическое строковое выражение с исключительной производительностью. Он также поддерживает пользовательские переменные и функции. Библиотека .NET под названием MathEvaluator и её документация доступны на GitHub.
Для достижения высокой производительности при вычислении математических выражений используется сочетание современных возможностей .NET и эффективных алгоритмов. Ключевые стратегии включают минимизацию выделения памяти, избегание регулярных выражений и сокращение накладных расходов от сложных структур данных.
Минимизация выделения памяти
Для минимизации выделения памяти при разборе математических выражений evaluator использует ReadOnlySpan<char>. Эта структура позволяет эффективно манипулировать подстроками без необходимости в дополнительных выделениях памяти, что обеспечивает значительный прирост производительности. Именно поэтому эта библиотека нацелена на .NET Standard 2.1 или выше.
Избегание регулярных выражений
Хотя регулярные выражения мощны, они могут вносить значительные накладные расходы. Вместо использования регулярных выражений для разбора строки, evaluator применяет рекурсивные вызовы методов для вычисления математических операций на основе приоритета операторов и других математических правил. Этот рекурсивный подход упрощает логику парсера и устраняет накладные расходы, связанные с использованием стеков или очередей, обычно применяемых при вычислении математических выражений.
Статические методы
Используя статические методы, evaluator получает выгоду от оптимизаций при компиляции. Статические методы обычно быстрее, так как для их вызова не требуется экземпляр класса, что уменьшает накладные расходы, связанные с вызовами методов экземпляра.
Эффективный поиск
Для эффективного поиска и управления переменными и функциями evaluator использует префиксное дерево, также известное как trie. Trie позволяет быстро искать по ключам (именам) и весьма эффективно при работе с большим количеством переменных и функций. Эта структура обеспечивает быстрый поиск и добавление, что делает её идеальной для расширения математических контекстов пользовательскими переменными и функциями.
Сравнение производительности
Давайте сравним, например, производительность вычисления математического выражения:
22888.32 * 30 / 323.34 / .5 - -1 / (2 + 22888.32) * 4 - 6Ниже приведено сравнение производительности с библиотекой NCalc:
Поддерживаемые математические функции, операторы и константы
Библиотека MathEvaluator уже включает поддержку контекстов для вычисления научных, программных и математических выражений на C#. Чтобы просмотреть полный список поддерживаемых функций, операторов и констант, обратитесь к документации. Эти контексты можно расширить, унаследовав их и добавив другие операторы, константы или функции. На основе отзывов разработчиков я могу расширить эти контексты для удовлетворения специфических потребностей, но надеюсь на высокую заинтересованность самого сообщества в развитии этого проекта.
Пример использования пользовательского математического контекста:
var context = new MathContext();
context.BindVariable(0.5, "x1");
context.BindVariable(-0.5, "x2");
context.BindFunction(Math.Sqrt);
context.BindFunction(Math.Log, "ln");
"ln(1/-x1 + Math.Sqrt(1/(x2*x2) + 1))"
.SetContext(context)
.Evaluate();Для вычисления математического выражения на C# используйте DotNetStandardMathContext. Этот программный математический контекст .NET Standard 2.1 поддерживает все константы и функции, предоставляемые классом System.Math.
Пример:
"-2 * Math.Log(1/0.5f + Math.Sqrt(1/Math.Pow(0.5d, 2) + 1L)"
.Evaluate(new DotNetStandartMathContext());Дополнительные примеры и подробная информация в документации.
Заключение
MathEvaluator обеспечивает высокую скорость за счёт минимизации выделения памяти, избегания сложности регулярных выражений и сокращения накладных расходов, связанных со структурами данных типа стек или очередь. Он использует префиксное дерево для эффективного поиска пользовательских переменных и функций, что делает его мощным инструментом для научных вычислений в .NET. Библиотека следует правилам математических вычислений и может вычислять сложные выражения с поразительной скоростью и эффективностью, что подтверждается прохождением более 1000 тестов и benchmarks, включая сложные математические выражения, такие как sin-3/cos1 или -3^4sin(-π/2).
Для развития проекта можно добавить поддержку вычисления выражений на Python, формул Excel или добавить контекст для поддержки спецификации LaTeX, зависит от потребностей и поддержки сообщества. Если вы считаете этот проект ценным, пожалуйста, рассмотрите возможность спонсирования его на GitHub.
Спасибо! Если у вас есть идеи или предложения, пожалуйста, оставляйте их в комментариях.
Комментарии (23)
troepolik
01.08.2024 09:21+1Вижу есть примеры с параметризацией выражений
var value1 = "ln(1/-x1 + sqrt(1/(x2*x2) + 1))".Bind(new { x1, x2, sqrt, ln }).Evaluate();в этом случае скомпилированное выражение закэшируется или будет парситься каждый раз?
AntonAntonov88 Автор
01.08.2024 09:21Если одно и тоже выражение вычисляется многократно, советую контекст создавать отдельно и переиспользовать его, он потокобезопасен. Так как логика парсинга простая и производительность благодаря этому высокая, а "компиляция" потребует значительного выделения памяти и кеширование легко реализовать отдельно то решил это не добавлять, если библиотека будет пользоваться спросом можно рассмотреть добавление этой функциональности.
belch84
01.08.2024 09:21+1В таком случае ваши тесты измеряют не скорость вычисления, а суммарную скорость компиляции (парсинга) и вычисления. А теперь представьте себе, что какая-нибудь другая библиотека компилирует выражения в десять раз медленнее, чем ваша, зато после компиляции вычисляет их на 10 % быстрее. Какая библиотека, по-вашему, будет более полезной? Компиляция (перевод во внутреннее представление) и вычисление по внутреннему представлению должны быть отделены друг от друга обязательно. Практически во всех содержательных приложениях на одну компиляцию приходится множество вычислений, иногда соотношение может достигать сотен тысяч или миллионов. Просто вообразите себе, что вашу библиотеку кто-то захочет использовать для построения графика функции (сотни или тысячи вычислений на одну компиляцию) или для решения диффуравнений (десятки тысяч вычислений на одну компиляцию)
AntonAntonov88 Автор
01.08.2024 09:211000 вычислений займут 0.5 секунды без компиляции, важнее сама простота концепции, поддержка сложных математических выражений и расширяемость, существующие решения предлагают ограниченный набор функций, либо закрыты либо требуют значительных усилий для расширения их возможностей, я не исключаю добавление компиляции и кеширование, это вторично, может быть добавлено позже, вы также можете поучаствовать в этом.
AntonAntonov88 Автор
01.08.2024 09:211000 вычислений это 0.5 ms, соответственно 1 млн это полсекунды
Colt045
01.08.2024 09:21+1Когда-то давно делал подобную задачу. Еще для Трубо-Паскаля.
И таки полностью с вами согласен, что парсинг должен быть отдельно от котлет. В первую очередь, конечно, как раз для массовых вычислений по одной формуле (см. построение графиков).
Но что еще интересно, то получив дерево разбора, можно потом с ним делать всякое (а не только банальное вычисление). Например, я тогда прикрутил в свою либу возможность получения производной функции.
belch84
01.08.2024 09:21Но что еще интересно, то получив дерево разбора, можно потом с ним делать всякое (а не только банальное вычисление). Например, я тогда прикрутил в свою либу возможность получения производной функции
Совершенно верно, я тоже дифференцирование реализовал. Еще написал крайне полезную функцию, которая показывает, зависит ли данное выражение в виде дерева от заданной пременной
И еще один аспект - вычисление следует выполнять с помощью выражения, заведомо не содержащего синтаксических ошибок, иначе каждый раз при вычислении придется выполнять кучу проверок
Alexandroppolus
01.08.2024 09:21Совершенно верно, я тоже дифференцирование реализовал.
Наверно, дифференцирование добавляли почти все, кто делал парсер ) Я не стал исключением. Но собственно взять производную по формулам, имея на руках AST - пустяковая задача на рекурсию. Намного сложнее потом сократить результат (недостаточно отбросить "шелуху" вроде добавления нуля или умножения на 1, могут понадобиться всякие дополнительные преобразования, раскрытия скобок, тригонометрические приколы и т.д.)
Хотя нет, даже производную не всегда легко взять. Например, y = x^x, тут сначала надо привести к e^(x * ln(x))
Еще написал крайне полезную функцию, которая показывает, зависит ли данное выражение в виде дерева от заданной пременной
Формально зависит, или фактически?
Например, f(x) = sin(x)^2 + cos(x)^2 не зависит от х. Это опять же к вопросу упрощений.
belch84
01.08.2024 09:21Намного сложнее потом сократить результат (недостаточно отбросить "шелуху" вроде добавления нуля или умножения на 1, могут понадобиться всякие дополнительные преобразования, раскрытия скобок, тригонометрические приколы и т.д.)
Это зависит от того, что вы собираетесь с этой производной делать дальше. Мне она нужна была для получения якобиана системы диффуравнений, который далее должен был использоваться в вычислениях. Для этого вполне достаточно было иметь элементы якобиана в виде деревьев, очищенных от вырожденных случаев (x*0=0 и т.п.). Если же подразумевается иное использование (например, студент на экзамене должен доказать, что умеет брать производные) - тогда действительно могут понадобиться дополнительные упрощения
Refridgerator
01.08.2024 09:21Если нужна производная функции, то её проще через дуальные числа получить. А также через те же дуальные числа можно разрешать неопределённости вида 0/0.
andrejjm78
01.08.2024 09:21+4Подобных проектов много. На базе идеи AngouriMath делался калькулятор фишка которого была в том, что расчеты из текстового поля (по типу рабочего листа MatLab) преобразовывались в отчет в ворде с оформленными формулами и, даже, графиками и векторными диаграммами. MathML не стоит использовать, лучше LATEX, из под него проще сделать вычисления выражений. Набрал в текстовом виде задачу, нажал кнопочку и, если расчетами доволен, через несколько секунд готов красивенький вордовский отчет. Поменял исходные данные и следующий вариант готов. Не надо в ворде перебивать формулы и циферки из маткада или вольфрама.
Выражения в подобных проектах не компилируются. Если нужны графики с мелким шагом или 100000 значений, то жми на кнопку и иди пей чай.
Какая разница за 0,1 мкс или 10 мкс вычислится выражение, если его надо 1 минуту набирать?
Refridgerator
01.08.2024 09:21Скорость парсинга вообще не имеет значения, потому что оно один раз делается. Имеет значение скорость выполнения выражения в виде синтаксического дерева или списка в виде польской записи, а также дополнительная функциональность по преобразованию его в код, latex и т.д. А в таком виде это уровень студенческой работы, так вы донатов не соберёте, уж извините.
AntonAntonov88 Автор
01.08.2024 09:21Я был студентом и даже лучшим на курсе, студент такое не сделает, попридержите при себе оскорбления чтобы потом не приходилось извиняться. По поводу донатов, у меня не было цели сделать замену всех существующих решений, я предлагаю публике решение основанное на простых математических правилах вычислений, расширяемое за счёт создания своих контекстов и быстрое независимо от сложности контекста, о чем и написано в статье, у меня нет времени заниматься тем что не пользуется спросом, донаты это показатель того что сообщество это поддерживает и есть смысл дальше это развивать, на данном этапе я смотрю на заинтересованность сообщества в развитии этого решения. Например создать контекст для поддержки Latex, компиляцию выделить в отдельную структуру.
Refridgerator
01.08.2024 09:21Это не оскорбление. Я делал подобное именно студентом 2-го курса в качестве курсовой работы, только там сверху ещё скелетная 3D-анимация была.
swingaroo
01.08.2024 09:21Жаль, что булевских операций нет. Поигрался бы с альтернативой NCalc на проекте. Нужно массово вычислять булевские выражения с десятком параметров, попадаются весьма громоздкие.
zhek_pot
01.08.2024 09:21О, да!! Мне тоже очень нужны просчеты булевских выражений, делаю свой ЧПУ постпроцессор))
Colt045
01.08.2024 09:21А что имеется ввиду под "булевскими операциями"?
Простые, чисто булевские, выражения типа "x and y", или микс с математическими, типа "(x>0) and (sin(y)=1)"?
Хотите иметь классическую булеву логику (true/false) или тренарную (true/false/unknown)?
Просто интересно.
belch84
А как будет выглядеть вычисление 10000 значений по одной и той же формуле с различными значениями переменной (скажем, изменяющимися в каком-то диапазоне), можете привести пример?
AntonAntonov88 Автор
Здесь примеры выражений и benchmarks.
Все крутится около 500 ns или 0.5 ms даже примеры с использованием переменных в научном контексте за счет применения структуры префексное дерево в контекте. Зависит от сложности выражений, есть примеры и 300-400 ns.
belch84
Все равно не понимаю. Там все примеры - это вычисление одного выражения. Хотел бы понять, как это выглядит в цикле - одно и то же выражение, вычисляемое 10000 раз для различных значений переменной
petuhov_k
Судя по коду, нет ни синтаксического дерева ни дерева выражений, т. е. парсинг и вычисление делаются вместе. Выражение не компилируется.
sami777
Так 500 ns или 0.5 ms??? Что, 3 порядка разница?
AntonAntonov88 Автор
500 ns т.е. 0.0005 ms, сам себе в ногу выстрелил, да вы правы 1ms это 10^6 ns