数学表达式评估 - 非常快 - 使用 Objective-C [英] math expression evaluation - very fast - with objective-c

问题描述

我想计算一个像 y = 2(x * x) + 2 这样的数学表达式.

i want to evaluate a math expression like y = 2(x * x) + 2.

但我需要循环使用它，其中 x 可能会更改 100000 次.

But i need it in a loop, where the x changes maybe 100000 times.

我已经编写了代码来翻译解析树中的表达式.

I have written code to translate the expression in a parse tree.

然后我有一个评估解析树的方法.

Then i have a method to evaluate the parse tree.

- (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 中并加载它(大约需要一秒钟).再加上数学函数的记忆版本，可以给我最好的性能.

Someone said: if i gotta go for speed, i could translate the expression into C code, compile and link it into a dll on-the-fly and load it (takes about a second). That, plus memoized versions of the math functions, could give me the best performance.

我怎样才能做到这一点?我如何将数学表达式编译成 C 代码并将其编译并链接到一个 dll 左右.然后动态加载以加快循环速度?

How can i achive that ? How can i compile the math expression into C code and compile and link it into a dll or so. And then load it on the fly to speed the loop up ?

非常感谢！

克里斯

推荐答案

我的建议:不要自己编写这段代码.编写了执行此操作的代码后，需要注意一些事项:

My advice: Do not write this code yourself. Having written code that does this, there are some things to be aware of:

解析数学表达式不是一个简单的问题，如果您要正确且充分地做到这一点.您必须考虑诸如每个运算符的关联性之类的事情:如果您在表达式中找到多个相同的运算符会发生什么?你先评价哪一个?您如何处理优先级根据上下文而变化的运算符?(例如，否定运算符)这些都是难题，很少有实现正确.

Parsing mathematical expressions is not a trivial problem, if you're going to do it correctly and fully. You have to consider things like the associativity of each operator: what happens if you find more than one of the same operator in an expression? Which one do you evaluate first? How do you deal with operators whose precedence changes depending on their context? (for example, the negation operator) These are hard questions, and very few implementations get it right.

正如对该问题的评论中提到的，有些事情已经可以为您做到这一点:

As was mentioned in a comment on the question, there are some things that can do this for you already:

1. NSPredicate.优点:内置，速度相当快，精度不错.缺点:用不正确的关联性解析指数，不可扩展，不支持隐式乘法(即 2(x*x))，不能正确解析否定运算符.
2. GCMathParser.优点:非常快，精度不错.缺点:不可扩展，不支持隐式乘法，不能正确解析否定运算符.
3. DDMathParser.优点:出色的精度、可扩展性、支持隐式乘法.缺点:由于解析引擎和高精度数学，不如其他两个快

1. NSPredicate. Pros: built-in, reasonably fast, decent precision. Cons: the exponent is parsed with incorrect associativity, not extensible, does not support implicit multiplication (i.e., 2(x*x)), does not parse the negation operator correctly.
2. GCMathParser. Pros: very fast, decent precision. Cons: not extensible, does not support implicit multiplication, does not parse the negation operator correctly.
3. DDMathParser. Pros: excellent precision, extensible, supports implicit multiplication. Cons: not quite as fast as the other two, due to the parsing engine and high precision math

显然，我推荐 DDMathParser(我写的).在你的情况下，你想做这样的事情:

Obviously, I recommend DDMathParser (I wrote it). In your case, you'd want to do something like this:

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.请注意其许可(注明出处后免费使用).

DDMathParser is available on GitHub: https://github.com/davedelong/DDMathParser . Please be mindful of its license (free for use with attribution).

但是，如果您愿意牺牲一些精度(以及一些不正确的情况)以换取极快的速度，我建议您使用 GCMathParser.

However, if you're ok with sacrificing some precision (and a couple of cases of it being incorrect) in exchange for blazing fast speed, I'd recommend using GCMathParser.

这篇关于数学表达式评估 - 非常快 - 使用 Objective-C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！