Блог

Примером может служить что-то вроде Desmos (но как настольное приложение). Функция задается пользователем в виде текста, поэтому она не может быть записана во время компиляции. Кроме того, функция может быть повторно использована тысячи раз, прежде чем она изменится. Однако истинным примером может быть то, где функция может меняться чаще, чем desmos, и ее значения также могут использоваться чаще.

Я вижу четыре метода для написания этого кода:

1. Разбирайте определяемую пользователем функцию с грамматикой при каждом вызове функции. (Медленно из-за большого количества вызовов функций)
2. Создайте синтаксическое дерево математического выражения так, чтобы узлы содержали функциональные указатели на соответствующие математические операции, что позволяет программе пропускать синтаксический анализ текста при каждом вызове функции. Это должно быть быстрее, чем # 1 для многих вызовов функций, но оно по-прежнему включает указатели на функции и дерево, что добавляет косвенность и не так быстро, как если бы функции были предварительно скомпилированы (и оптимизированы).
3. Используйте что-то вроде компилятора Tiny C в качестве серверной части для динамической генерации кода с помощью libtcc, чтобы быстро скомпилировать пользовательскую функцию после перевода ее в код C, а затем использовать ее в основной программе. Поскольку этот компилятор может компилировать что-то вроде 10 000 очень простых программ на моей машине в секунду, задержек при разборе новых функций почти не должно быть. Кроме того, этот компилятор генерирует машинный код для функции, поэтому не используются указатели или деревья, а оптимизация выполняется TinyCC. Этот метод более сложен для программиста среднего уровня, такого как я.
4. Написать свой собственный крошечный компилятор (не на C, но специально адаптированный к моей проблеме), чтобы генерировать машинный код почти мгновенно. Это, вероятно, в 20 раз больше работы, чем # 3, и не сильно влияет на будущие улучшения (добавление генератора операций суммирования потребовало бы от меня написания большего количества ассемблерного кода для этого).

Есть ли какой-либо более простой, но не менее эффективный метод, чем # 3, оставаясь при этом в области C ? Я недостаточно разбираюсь в лямбдах, шаблонах и стандартной библиотеке, чтобы точно сказать, нет ли какого-нибудь абстрактного способа написать этот код легко и эффективно.

Даже метод, который быстрее, чем # 2, но медленнее, чем # 3, и не требует динамической генерации кода, был бы улучшением.

Это скорее интеллектуальное любопытство, чем реальная проблема, вот почему меня так беспокоит производительность, и вот почему я бы не стал использовать чужую библиотеку математического анализа. Именно поэтому я бы не стал рассматривать использование интерпретатора javascript или Python, который может интерпретировать подобные вещи «на лету».

Я думаю, что что-то вроде вашего варианта 2 было бы неплохо. За исключением, может быть, немного проще было бы иметь Expr класс с float Expr::eval(std::unordered_map<string,float> vars) методом. Затем реализуйте подклассы, такие как Var с name , Add с left и right , Sub , Mult Div и т. Д. Все функции, которые вы хотите. При оценке вы просто передаете карту с помощью like {{"x",3},{"y",4}} или чего угодно, и каждый Expr объект передаст это любым подвыражениям, а затем выполнит свою операцию.

Я бы подумал, что это будет достаточно быстро. Как вы думаете, насколько сложными будут выражения, которые будут вводить ваши пользователи? Для большинства выражений, вероятно, не потребуется более 10-20 вызовов функций.

Это также может быть намного быстрее

Если вы пытаетесь создать что-то, что отображает функции (или подобное), вы могли бы значительно ускорить это, если бы вы сделали свои операции способными работать с векторами значений, а не с отдельными скалярными значениями.

Предполагая, что вы хотите построить график чего-то вроде x^3 - 6x^2 11x - 6 с 10 000 точками, если бы ваши Expr объекты одновременно работали только с отдельными значениями, да, это было бы похоже на ~10-15 function calls * 10,000 points = a lot jumping around! Однако, если бы ваши Expr объекты могли принимать массивы значений, например, вызывая eval с {{"x",[1,2,3...10000]}} , тогда всего было бы ~ 10-15 вызовов функций в оптимизированном C . Это может легко масштабироваться до большего количества точек и при этом быть очень быстрым.

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

Затем вы в основном объединяете строки машинного кода с семантикой типа «поместить литерал в стек», «выполнить двоичную операцию над двумя самыми верхними элементами стека и поместить результат в стек» и «извлечь результат из стека»