数学表达式评估 – 非常快 – 与objective-c
我想评估一个数学表达式，如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并加载它（大约需要一秒钟）。 那，加上数学函数的memoized版本，可以给我最好的表现。
我怎么能做到这一点？ 如何将数学表达式编译成C代码并将其编译并链接到dll左右。 然后加载它以加速循环？
非常感谢 ！
克里斯
我的建议： 不要自己编写这段代码 。 编写完成此代码的代码后，有一些事项需要注意：
如果你要正确而完整地解析数学表达式并不是一个小问题。 你必须考虑每个运算符的关联性：如果在表达式中找到多个相同的运算符会发生什么？ 你先评价哪一个？ 您如何处理其优先级根据其上下文而变化的运算符？ （例如，否定运算符）这些都是难题，很少有实现能够正确实现。
正如在对该问题的评论中所提到的，有些事情可以为您做到这一点：
-
NSPredicate。 优点：内置，合理快速，不错的精度。 缺点：指数被解析为具有不正确的关联性，不可扩展，不支持隐式乘法（即2(x*x)），不能正确解析否定运算符。 -
GCMathParser。 优点： 非常快 ，体面的精确度。 缺点：不可扩展，不支持隐式乘法，不能正确解析否定运算符。 -
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 。
如果您要对性能进行分析，那么[很可能几乎100％肯定]会发现字符串比较会影响您的性能。
一个简单的解决方法是从评估中拆分解析。 也就是说，将表达式解析为中间forms（就像jills和Rudy所提到的那样，但更简单），然后评估该中间forms。
也就是说，您可以创建一个“parse：”方法，[递归]遍历节点树，解析每个节点，然后将属性设置为表示运算符的某个＃。
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;
由于您已经在解析表达式，因此这应该更容易/更直接。
我想评估像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的当前值自动重新评估。
如果需要更快，可以始终在运行时生成代码，然后调用实际的编译器。 但是，运行编译器所花费的时间可能会使速度节省相形见绌，直到您进行数十亿次评估。 您在问题中提供的100,000评估编号可能会被TinyExpr几乎立即评估。 这很快。
您可以获得现有的表达式解析器。 他们中的一些人可以动态地将这些表达式“编译”成某种内部格式，这样可以更快地评估表达式，然后允许您为变量提供值。 “编译”将在循环之前完成，并且每次循环迭代都会替换一次。
我知道Delphi存在这样的表达式解析器/评估器，但我不知道C，对不起。 我假设你可以在网上找到它们，因为C拥有比Delphi更大的全球代码库。 只需google（或bing等）获取“表达式解析器”，然后查看您找到的那些是否可以进行此类替换，而无需重新解析表达式。
简单地使用OO设计有什么问题？
@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 ++中的等价物可能会快一点。
您无法在iOS上生成和执行机器代码，但您仍然可以比走一个解析树做得更好。 从解析树中，生成虚拟堆栈机器的指令（想想Forth，x87机器代码，java字节码，CLR字节码）。 生成时，您可以确定所需的堆栈空间（数量）。 然后为x的每个值解释这些指令。 这更快，因为指令比解析树更紧凑并且具有更好的局部性，并且因为没有使用C递归。
编辑：例如，表达式sqrt（x + 1）被转换为四个指令：一个用于将变量x推入堆栈，一个用于推送常量1，一个用于弹出两个数字并推送总和一个用于替换平方根的总和。 使用递归函数可以很容易地将任何解析树转换为这样的指令列表。 指令可以由结构表示，该结构包含用于指令类型的枚举和用于推送常量指令的数字。 “堆栈”不是C堆栈，而只是一个数字数组，其中一个整数表示当前正在使用的数量（从0开始，将以1结束）。