math expression evaluation - very fast - with objective-c

Question

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

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;
}

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.

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 ?

Thanks a lot !

Chris

Answer 1

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. 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

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 is available on GitHub: https://github.com/davedelong/DDMathParser . Please be mindful of its license (free for use with attribution).

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.

Answer 2

If you were to performance analyze that code, you'd [very most likely almost 100% assuredly] find that string comparison is what is killing your performance.

An easy fix is to split parsing from evaluation. That is, parse the expression into an intermediate form (like what jills and Rudy allude to, but simpler) and then evaluate that intermediate form.

That is, you might create a "parse:" method that [recursively] walks your tree of nodes, parses each, and then sets a property to some # representing the operator.

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

@property(nonatomic) OperatorID operatorID;

Then, your evaluate:variable:'s if/else would be replaced with a switch statement.

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

Hi, thanks a lot. But i already parsed the expression and have build a tree, which i evaluate with the method above. What i need is a faster evaluation in a loop.

Don't represent the parse tree as strings.

I.e. instead of _operator returning an NSString, make it return an int (or OperatorID, if using the above) then use a switch statement.

@property(nonatomic) OperatorID _operator;

Since you are already parsing the expression, this should be even easier / more straightforward to do.