оценка математического выражения - очень быстро - с целью-c - PullRequest
Новая
       35

оценка математического выражения - очень быстро - с целью-c

7 голосов
/ 25 июля 2011

я хочу оценить математическое выражение, например, y = 2 (x * x) + 2.

Но мне это нужно в цикле, где х меняется, может быть, 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

Ответы [ 6 ]

13 голосов
/ 25 июля 2011

Мой совет: Не пишите этот код самостоятельно . Написав код, который делает это, нужно помнить о некоторых вещах:

Разбор математических выражений не является тривиальной проблемой, если вы собираетесь делать это правильно и полностью. Вы должны учитывать такие вещи, как ассоциативность каждого оператора: что произойдет, если вы найдете более одного оператора в выражении? Какой из них вы оцениваете первым? Как вы справляетесь с операторами, чей приоритет меняется в зависимости от их контекста? (например, оператор отрицания) Это сложные вопросы, и очень немногие реализации понимают это правильно.

Как уже упоминалось в комментарии к вопросу, есть некоторые вещи, которые могут сделать это для вас уже:

  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.

2 голосов
/ 25 июля 2011

Если бы вы проанализировали производительность этого кода, вы [весьма вероятно почти на 100% уверены] обнаружите, что сравнение строк - это то, что убивает вашу производительность.

Легкое решение - разделить анализ от оценки. То есть разберите выражение в промежуточную форму (например, на что намекают Джиллс и Руди, но проще), а затем оцените эту промежуточную форму.

То есть вы можете создать метод "parse:", который [рекурсивно] обходит ваше дерево узлов, анализирует каждый и затем устанавливает свойство для некоторого #, представляющего оператор. 

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

@property(nonatomic) OperatorID operatorID;

Тогда ваши evaluate:variable:, если / еще, будут заменены оператором switch. 

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

Привет, спасибо большое. Но я уже проанализировал выражение и создал дерево, которое я оцениваю с помощью метода выше. Что мне нужно, так это быстрее оценка в цикле.

Не представлять дерево разбора в виде строк.

т.е. вместо _operator, возвращающего NSString, сделайте так, чтобы он возвращал int (или OperatorID, если используется вышеуказанное), а затем используйте оператор switch. 

@property(nonatomic) OperatorID _operator;

Поскольку вы уже анализируете выражение, это должно быть еще проще / проще сделать.

1 голос
/ 25 января 2017

Я хочу оценить математическое выражение, например, y = 2 (x * x) + 2. Но мне это нужно в цикле, где х меняется, может быть, 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 практически мгновенно. Это довольно быстро.

0 голосов
/ 25 июля 2011

Что не так с простым использованием OO design? 

@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 ++ может быть немного быстрее.

0 голосов
/ 25 июля 2011

Вы не можете сгенерировать и выполнить машинный код на iOS, но вы все равно можете добиться большего успеха, чем обходить дерево разбора. Из дерева разбора сгенерируйте инструкции для вымышленной стековой машины (например, Forth, машинный код x87, байт-код java, байт-код CLR). Во время генерации вы можете определить, сколько стекового пространства (чисел) вам нужно. Затем интерпретируйте эти инструкции для каждого значения x. Это быстрее, потому что инструкции более компактны и имеют лучшую локальность, чем дерево разбора, и потому что рекурсия C не используется.

РЕДАКТИРОВАТЬ: Например, выражение sqrt (x + 1) переводится в четыре инструкции: одну для помещения переменной x в стек, одну для вставки константы 1, одну для выталкивания двух чисел и нажатия суммы и один, чтобы заменить сумму с квадратным корнем. Любое дерево разбора можно легко перевести в такой список инструкций с помощью рекурсивной функции. Инструкция может быть представлена ​​структурой, содержащей перечисление для типа инструкции и число для инструкций константы push. «Стек» - это не стек C, а просто массив чисел с целым числом, указывающим, сколько из них используется в данный момент (которое начинается с 0 и заканчивается на 1).

0 голосов
/ 25 июля 2011

Вы можете получить существующий синтаксический анализатор выражений. Некоторые из них могут «скомпилировать» такие выражения на лету во некоторый внутренний формат, который ускорит оценку выражения, а затем позволит вам предоставить ему значения для переменных. «Компиляция» будет выполняться перед циклом и заменой один раз за каждую итерацию цикла.

Я знаю, что такие парсеры / оценщики выражений существуют для Delphi, но я не знаю ничего для C, извините. Я предполагаю, что вы можете найти их в Интернете, поскольку C имеет гораздо большую базу кода по всему миру, чем Delphi. Просто Google (или Bing и т. Д.) Для «синтаксический анализатор выражений», а затем посмотрите, могут ли те, которые вы нашли, могут сделать такие замены без повторного анализа выражения.

...