数学表达式评估 - 使用Objective-C非常快速

Question

我希望能够评估一个数学表达式，比如y = 2（x * x）+ 2。

但是我需要在循环中进行，其中x可能会变化100000次。

我编写了代码来将表达式转换为解析树。

然后我有一个方法来评估这个解析树。

- (double) evaluate:(TreeNode *)node variable:(double)x
{
    if ([node _operand] != 0) 
    {
        return [node _operand];
    }

    else if ([node _variable] != NULL) 
    {
        return x;
    }

    else if ([node _operator] != NULL) 
    {
        if ([[node _operator] isEqualToString: @"+"]) 
        {
            return ([self evaluate:[node left] variable:x] + [self evaluate:[node right] variable:x]);
        }
        else if ([[node _operator] isEqualToString: @"-"]) 
        {
            return ([self evaluate:[node left] variable:x] - [self evaluate:[node right] variable:x]);
        }
        else if ([[node _operator] isEqualToString: @"*"]) 
        {
            return ([self evaluate:[node left] variable:x] * [self evaluate:[node right] variable:x]);
        }
        else if ([[node _operator] isEqualToString: @"/"]) 
        {
            return ([self evaluate:[node left] variable:x] / [self evaluate:[node right] variable:x]);
        }
    }

    return 0;
}

有人说：如果我需要速度，我可以将表达式翻译成C代码，即时编译并链接成dll，然后加载它（大约需要一秒钟）。再加上数学函数的记忆版本，可以获得最佳性能。

我该如何实现这个想法？

我该如何将数学表达式编译成C代码，并将其编译和链接成dll或其他形式。然后即时加载它以加速循环运行？

非常感谢！

Chris

- Chris2810

---

我敢打赌你的表达式计算器可以在一秒钟内完成10万次迭代（或者至少非常接近）。你有测量过它的性能吗？ - Greg Hewgill

是的，它很快，但对我来说还是太慢了。 上面的代码还没有完成。 我有更多的“if”用于sin、cos、tan等函数。 因此，如果我添加更多函数，它将变得更慢。 - Chris2810

你考虑过GCMathParser或者DDMathParser吗？它们都被称为非常快速。 - Itai Ferber

@Itai，他们cough也值得得到赞吗？;) - Dave DeLong

@Dave 哦，对了。 - Itai Ferber

Answer 1

我的建议是：不要自己编写这个代码。 如果你想要正确和完整地解析数学表达式，那么这不是一个简单的问题。你必须考虑每个运算符的结合性：如果在表达式中找到了多个相同的运算符，会发生什么？哪个先计算？如何处理其优先级取决于上下文的运算符？（例如，否定运算符）这些都是很难回答的问题，很少有实现能够做得很好。

正如在问题的评论中提到的，已经有一些可以帮助你完成此任务的工具：

1. NSPredicate。 优点：内置，速度较快，精度还可以。 缺点：指数以错误的结合性解析，不可扩展，不支持隐式乘法（即2(x*x)），不能正确解析否定运算符。
2. GCMathParser。 优点：非常快，精度还可以。 缺点：不可扩展，不支持隐式乘法，不能正确解析否定运算符。
3. DDMathParser。 优点：精度极高，可扩展，支持隐式乘法。 缺点：由于解析引擎和高精度数学的原因，速度不如其他两个。

显然，我推荐 DDMathParser（我写的）。 在你的情况下，你需要做类似这样的事情：

NSError *error = nil;
NSString *math = [DDExpression expressionFromString:@"2($x * $x) + 2" error:&error];

for (int x = 0; x < 100; ++x) {
  NSNumber *variable = [NSNumber numberWithInt:x];
  NSDictionary *sub = [NSDictionary dictionaryWithObject:variable forKey:@"x"];
  NSNumber *value = [math evaluateWithSubstitutions:sub evaluator:nil error:&error];
  NSLog(@"value: %@", value);
}

DDMathParser 可在GitHub上找到：https://github.com/davedelong/DDMathParser。请注意其许可证（署名后可免费使用）。

然而，如果您可以牺牲一些精度（以及一些不正确的情况），换取极快的速度，我建议使用 GCMathParser。

- Dave DeLong

---

你好， 感谢您提供精确的答案。 我已经使用了GCMathParser。我也尝试了您的DDMathParser。但是我需要更快的循环计算方法。我想用辛普森规则计算积分，并且由于精度问题，我需要在循环中频繁进行计算（100000次或更多）。我该如何实现更快的计算？我能否通过即时生成的字节码来实现？ - Chris2810

@Chris2810 我真的很怀疑。目前来看，我会说你最好选择GCMathParser来提高速度。它真的非常快。如果你在使用它时遇到速度问题，请发表另一个问题，问 "如何优化这个？"，我会很乐意在那里帮助你。这样我们就不会被卷入长时间而且限制性很强的评论讨论中。 - Dave DeLong

也许你有什么想法，我该如何开始动态编译表达式？ 你能帮我吗？ 那就是我所需要的。 - Chris2810

@Chris2810，“GCMathParser”页面有一个示例，可以让您编译一次表达式，然后多次使用不同的x值重新评估它。 - Dave DeLong

嗨，Dave，我已经使用了GCMathParser。 但是它对我来说太慢了。 因此，我用解析树和递归制作了自己的解析器。 它更快，但在循环中执行1000000次仍然太慢。 我需要这样的循环，因为需要精确的结果。有比遍历解析树更快的方法吗？ - Chris2810

@Chris2810在一个新问题中发布你的代码，寻求帮助进行优化。 - Dave DeLong

Answer 2

如果您对该代码进行性能分析，那么您会[非常有可能几乎100%肯定]发现字符串比较是导致性能下降的罪魁祸首。

一个简单的解决方法是将解析和评估分离。也就是说，将表达式解析为中间形式（类似于Jills和Rudy所提到的，但更简单），然后评估该中间形式。

也就是说，您可以创建一个“解析：”方法，[递归地]遍历节点树，解析每个节点，然后设置一个属性来表示某个运算符的#。

typedef enum {
PlusOperator,
SinOperator,
..... etc ....
} OperatorID;

@property(nonatomic) OperatorID operatorID;

那么，你的 evaluate:variable: 中的 if/else 语句将被替换为 switch 语句。

switch([node operatorID) {
case PlusOperator:
    ....
    break;
... etc ...

你好，非常感谢。但是我已经解析了表达式并构建了一棵树，使用上述方法进行了评估。我需要的是在循环中更快的评估。

不要将解析树表示为字符串。

即，不要让_operator返回NSString，而是让它返回int（或OperatorID，如果使用上述方法），然后使用switch语句。

@property(nonatomic) OperatorID _operator;

既然您已经在解析表达式，那么这应该更容易/更直接地完成。

- bbum

---

嗨，非常感谢。 但是我已经解析了表达式并构建了一棵树，使用上述方法进行评估。 我需要的是在循环中更快的评估。 - Chris2810

我该如何在Objective-C中实现这个？ - Chris2810

正如他所说：不使用字符串来存储解析树。运算符可以用整数来指定，而不必使用相对较慢的“isEqualToString:”（与简单的int相等性比较相比） - Rudy Velthuis

你用性能分析工具测量过吗？现在是什么在消耗你的CPU？即时编译表达式既不是魔术也不容易；如果不知道你的性能目标和现在的性能问题所在，就无法再多说了。 - bbum

不，除非你手头有性能数据清楚地显示CPU周期的消耗情况，否则这并不是你需要的。如果你现有的[工作但缓慢]解决方案无法得到足够的优化，那么Dave De Long的答案更好。无论如何，在你拥有性能数据之前，没有理由相信解决这个特定问题将解决实际问题。 - bbum

Answer 3

我希望对一个数学表达式进行评估，例如y = 2(x * x) + 2。 但我需要在循环中使用它，其中x可能会变化100000次。

你应该考虑使用TinyExpr数学表达式评估库。它是用C编写的，可以完全满足您的要求。如果您更喜欢自己编写代码，TinyExpr仅有500行代码，因此这可能是您能找到的最简单的完整示例。

以下是如何使用不断变化的x解决问题的方法：

double x;
te_variable vars[] = {{"x", &x}};

te_expr *expr = te_compile("2*(x*x)+2", vars, 1, 0);

for (x = 0; x < 100000; ++x) {
    double y = te_eval(expr);
    printf("x=%f, y=%f\n", x, y);
}

请注意，即使表达式只被“编译”一次，它也会自动重新评估为x的当前值。

如果您需要更快的速度，您可以在运行时生成代码，然后调用实际编译器。然而，运行编译器所需的时间可能会使速度节省变得微不足道，直到您进行了数十亿次评估。您在问题中给出的10万次评估数字可能会被TinyExpr几乎立即评估。它非常快。

- mollykk

Answer 4

仅仅使用面向对象设计有什么问题吗？

@implementation TreeNodeAdd

-(double)evaluateWithVariable:(double)x
{
  return [left evaluateWithVariable:x] + [right evaluateWithVariable:x];
}

@end

...

- (double) evaluate:(TreeNode *)node variable:(double)x
{
  return [node evaluateWithVariable:x];
}

在C++中相应的代码可能会更快。

- tc.

---

那将是非常多的类...但那会起作用。另一个有趣的想法是，OP可以存储每个运算符的SEL并直接使用它。 - bbum

@bbum，这可能与（每个类？）方法缓存不太兼容。或者，只需存储IMP！ - tc.

不用担心 - 使用方法缓存应该可以正常工作。保存IMP也很好，尽管您会失去任何KVO或重写能力。 - bbum

Answer 5

你可以获取一个现有的表达式解析器。其中一些可以即时“编译”这些表达式到某种内部格式，从而使表达式的计算更快，并允许您为变量提供值。在循环之前进行“编译”，并在每个循环迭代中进行替换。

我知道 Delphi 存在这样的表达式解析器/求值器，但是我不知道 C 有没有，抱歉。我假设你可以在网上找到它们，因为 C 拥有比 Delphi 更大的全球代码库。只需搜索“表达式解析器”，然后查看您找到的解析器是否可以进行此类替换而无需重新解析表达式。

- Rudy Velthuis

---

谢谢， 我有一个解析器，但在循环中执行100000次时速度很慢。 - Chris2810

Answer 6

在iOS上你不能生成并执行机器码，但你仍然可以比遍历解析树做得更好。从解析树中，为一个虚构的堆栈机器（类似于Forth、x87机器码、Java字节码、CLR字节码）生成指令。在生成指令时，你可以确定需要多少堆栈空间（数字）。然后为每个x的值解释这些指令。这样做更快是因为指令比解析树更紧凑且局部性更好，并且不使用C递归。

编辑：例如，表达式sqrt（x + 1）被翻译成四条指令：一条将变量x推送到堆栈上，一条将常量1推送到堆栈上，一条将两个数字弹出并将它们相加的和推送到堆栈上，一条用其平方根替换和值。 任何解析树都可以使用递归函数轻松地转换为这样的指令列表。指令可以由包含指令类型枚举和推送常量指令的数字的结构体表示。“堆栈”不是C堆栈，而只是一个数字数组，其中一个整数表示当前使用了多少个（起始为0，最终为1）。

- jilles

---

你好，Jilles，我应该如何比遍历解析树更好地完成任务？ 我不知道如何使用堆栈空间和解释指令来实现。你能给我一个例子吗？非常感谢！Chris - Chris2810

我添加了更多细节；如果还不清楚，请使用我提供的关键词在搜索引擎中查找。 - jilles