Как оценивать пользовательское выражение 44100 раз в секунду

Question

Я работаю над плагином VST с использованием C++. Плагин позволит пользователю ввести математическое выражение, которое затем будет запускаться 44100 раз в секунду для генерации звука. Я новичок в таких вещах в реальном времени, как и интерпретация введенных пользователем выражений.

Проблема в том, что я не могу найти метод для оценки определенной пользователем функции, которая может быстро работать. Моя лучшая попытка состояла в том, чтобы преобразовать введенное пользователем выражение в RPN, когда оно было введено, а затем, когда функция оценивает выражение RPN для генерации звука. Я выполнил функцию оценки RPN и жестко закодировал выражение RPN, чтобы проверить его. Хотя кажется, что он правильно оценивает, он, похоже, не делает этого достаточно быстро.

Вот моя функция оценки, в дополнении к паре RPN выражений:

#include <string> 
#include <stack> 
#include <deque> 


/* 
* an RPN expression is stored as a deque of strings 
* 
* each string is either an operator, a number, or the single variable t 
* 
* the deque is read from front to back 
*/ 

std::deque<std::string> simpleCase, complexCase; 

//simple expression, just the variable t 
simpleCase.push_back("t"); 

//more complex expression, t*(42&(t>>11)) 
complexCase.push_back("t"); 
complexCase.push_back("42"); 
complexCase.push_back("t"); 
complexCase.push_back("11"); 
complexCase.push_back(">>"); 
complexCase.push_back("&"); 
complexCase.push_back("*"); 

/* 
* The evalRPN function takes an RPN deque, plugs in a supplied t, 
* and evaluates it. 
* 
* The idea is that t increases continually, and that the integer overflow 
* causes the output to oscillate between 0 and 255. 
* 
* t is a double, but I convert it to a uint32_t. 
* 
* Allowed operators: bitwise logic (&, |, ^), bitshifts (<<, >>), 
* and math (+, -, *, /, %) 
* 
* Allowed vars: t 
* 
* Supplied numbers are converted from string to char arrays then to an int 
* 
* This also assumes the RPN is not ill-formatted. 
*/ 
uint8_t evalRPN(std::deque<std::string> rpnExpr, double tVal) 
{ 
    std::stack<uint8_t> numberStack; 
    std::string token; 

    while(rpnExpr.size() > 0) 
    { 

     token = rpnExpr.front(); 
     rpnExpr.pop_front(); 

     if(token.find_first_not_of("") == std::string::npos) 
     { 
      //if token is a number 
      numberStack.push((uint8_t)atoi(token.c_str())); 
     } 
     else if (token == "t") 
     { 
      numberStack.push((uint8_t)tVal); 
     } 
     else 
     { 
      uint8_t last = numberStack.top(); 
      numberStack.pop(); 
      uint8_t first = numberStack.top(); 
      numberStack.pop(); 

      if(token == "^") 
      { 
       numberStack.push(first^last); 
      } 
      else if (token == "&") 
      { 
       numberStack.push(first & last); 
      } 
      else if (token == "|") 
      { 
       numberStack.push(first | last); 
      } 
      else if (token == "<<") 
      { 
       numberStack.push(first >> last); 
      } 
      else if (token == ">>") 
      { 
       numberStack.push(first >> last); 
      } 
      else if (token == "+") 
      { 
       numberStack.push(first + last); 
      } 
      else if (token == "-") 
      { 
       numberStack.push(first - last); 
      } 
      else if (token == "*") 
      { 
       numberStack.push(first * last); 
      } 
      else if (token == "/") 
      { 
       numberStack.push(first/last); 
      } 
      else if (token == "%") 
      { 
       numberStack.push(first % last); 
      } 
     } 
    } 

    //assume one left in numberStack 
    return(numberStack.top()); 
} 

Есть ли какие-либо оптимизации я могу сделать в моей обработке RPN, чтобы сделать его потенциально работать достаточно быстро? Альтернативно, есть ли другой способ обработки вычислений RPN, который более эффективен?

Кроме того, существует ли другой метод, совместимый с C++ для ввода введенной пользователем строки, представляющей стандартное математическое выражение, и затем выполнение этого выражения достаточно быстро, чтобы завершить его в течение 1/44100 секунды?

Answer 1

Это отличный вопрос.

Компиляция вашего выражения в RPN - хорошее начало, и на самом деле это похоже на то, что ваш код, вероятно, сможет выполнять более 88K выражений в секунду, если они не достаточно длинные.

НО, вы можете, безусловно, сделать намного лучше, не слишком много неприятностей.

Я хотел бы сделать интерфейс, как это:

class Expression 
{ 
    public: 
    virtual uint32_t eval(uint32_t tVal) = 0; 
}; 

Вы затем скомпилировать выражение в реализации этого интерфейса.

Вы можете иметь реализацию констант:

class ConstExpression : public Expression 
{ 
    private: 
    uint32_t m_constVal; 

    public: 
    // ... 

    uint32_t eval(uint32_t tVal) 
    { 
     return m_constVal; 
    } 
}; 

... реализация для ссылки на t

class RefExpression : public Expression 
{ 
    public: 
    // ... 

    uint32_t eval(uint32_t tVal) 
    { 
     return m_tVal; 
    } 
}; 

... и реализации для бинарных операторов

class AddExpression : public Expression 
{ 
    private: 
    auto_ptr<Expression> m_left; 
    auto_ptr<Expression> m_right; 

    public: 
    // ... 

    uint32_t eval(uint32_t tVal) 
    { 
     return m_left->eval(tVal) + m_right->eval(tVal); 
    } 
}; 

... возможно, вы хотите сделать магию шаблонов, чтобы избежать необходимости га так много классов операторов.

В любом случае, после компиляции выражения в выражение, вы можете оценить его просто как Expression-> eval (t), и весь код выполняется достаточно эффективно, без синтаксического анализа, сравнения строк, манипулирования стеками и т. Д.

Answer 2

Как о генерации кода в реальном времени, скомпилировать его, а затем использовать в качестве функции бинарной библиотеки? Я уверен, что он будет работать намного быстрее.

Answer 3

Вам не обязательно. Если вы создаете vst, вам нужно использовать библиотеки vst. Хост-хозяин автоматически вызовет функции обновления.

Answer 4

Спасибо за все ваши советы! С тех пор я реализовал решение, в котором я очень доволен. Хотя ни один из ответов здесь напрямую не сообщил мне об этом подходе, они меня вдохновили.

Я решил разобрать введенные пользователем инфиксные выражения в польский нотации (префикс), а затем в двоичные деревья. Я специально для этого создал структуру TreeNode, которая по существу является дважды связанным списком, но с 2 детьми вместо 1. Каждый TreeNode может быть задан как переменная, фиксированное число или оператор. Если он задан как оператор, то его оппонент функции opFunc установлен на предопределенную функцию, которая выполняет этот оператор.

Каждый узел имеет функцию-член оценки (tVal). Если это фиксированное число, это просто возвращает это число. Если это переменная, она просто возвращает tVal. Если это оператор, он возвращает opFunc (first-> evaluation (tVal), last-> evaluation (tVal)), который рекурсивно вычисляет два узла под ним, а затем выполняет на нем свой оператор.

Я также внедрил класс ExpressionTree, который управляет деревом и анализирует ввод пользователя в дерево. У него есть публичные члены, которые рекурсивно разрушают дерево, строят дерево из пользовательской строки ввода и оценивают дерево (ему просто нужно оценить корневой узел).

Потому что это использует указатели функций в простом рекурсивном дереве, это невероятно быстро, чтобы оценить ExpressionTree, даже когда формулы получаются очень большими. По сути, я переместил более или менее такую ​​большую обработку, насколько это возможно, когда функция оценивается и когда вводится формула.

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

В настоящий момент также не выполняется проверка ошибок, поэтому недопустимые операторы, пробелы или несогласованные круглые скобки приведут к неопределенному поведению ATM.

Также обратите внимание, что выражения обрабатываются как uint32_t и превращаются в uint8_t в конце, так как это требует мое приложение. Когда я закончу этот проект, я могу обобщить это как библиотеку и опубликовать ее.

TreeExpressions.hpp:

#include <cstdint> 
#include <string> 
#include <map> 
#include <stack> 
#include <vector> 
#include <algorithm> 

struct TreeNode { 
private: 
    bool isOp = false; 
    bool isVar = false; 
    uint32_t value = 0; 
    uint32_t(*opFunc)(uint32_t, uint32_t) = NULL; 

    static inline uint32_t xorOp(uint32_t a, uint32_t b) { return(a^b); }; 
    static inline uint32_t andOp(uint32_t a, uint32_t b) { return(a & b); }; 
    static inline uint32_t orOp(uint32_t a, uint32_t b) { return(a | b); }; 
    static inline uint32_t lshiftOp(uint32_t a, uint32_t b) { return(a << b); }; 
    static inline uint32_t rshiftOp(uint32_t a, uint32_t b) { return(a >> b); }; 
    static inline uint32_t addOp(uint32_t a, uint32_t b) { return(a + b); }; 
    static inline uint32_t subOp(uint32_t a, uint32_t b) { return(a - b); }; 
    static inline uint32_t multOp(uint32_t a, uint32_t b) { return(a * b); }; 
    static inline uint32_t divOp(uint32_t a, uint32_t b) { return(a/b); }; 
    static inline uint32_t modOp(uint32_t a, uint32_t b) { return(a % b); }; 
public: 
    TreeNode *first = NULL; 
    TreeNode *last = NULL; 
    TreeNode *parent = NULL; 
    uint32_t evaluate(uint32_t tVal); 
    void setOp(std::string op); 
    void setVal(uint32_t val); 
    void setVar(); 
}; 

class ExpressionTree 
{ 
private: 
    std::map<std::string, int> precedence; 
    TreeNode *treeRoot; 
    TreeNode *insertNode(TreeNode *leaf); 
    void destroyTree(TreeNode *leaf); 
public: 
    ExpressionTree(); 
    ~ExpressionTree(); 
    void destroyTree(); 
    bool build(std::string formulaStr); 
    uint8_t evaluate(uint32_t tVal); 
}; 

TreeExpressions.cpp:

#include "TreeExpressions.h" 

void TreeNode::setOp(std::string op) 
{ 
    isVar = false; 
    isOp = true; 


    if (op == "^") 
    { 
     opFunc = &xorOp; 
    } 
    else if (op == "&") 
    { 
     opFunc = &andOp; 
    } 
    else if (op == "|") 
    { 
     opFunc = &orOp; 
    } 
    else if (op == "<<") 
    { 
     opFunc = &lshiftOp; 
    } 
    else if (op == ">>") 
    { 
     opFunc = &rshiftOp; 
    } 
    else if (op == "+") 
    { 
     opFunc = &addOp; 
    } 
    else if (op == "-") 
    { 
     opFunc = &subOp; 
    } 
    else if (op == "*") 
    { 
     opFunc = &multOp; 
    } 
    else if (op == "/") 
    { 
     opFunc = &divOp; 
    } 
    else if (op == "%") 
    { 
     opFunc = &modOp; 
    } 

} 

void TreeNode::setVal(uint32_t val) 
{ 
    isVar = false; 
    isOp = false; 

    value = val; 
} 

void TreeNode::setVar() 
{ 
    isVar = true; 
    isOp = false; 
} 

uint32_t TreeNode::evaluate(uint32_t tVal) 
{ 
    if (isOp) 
    { 
     //if it's an op 
     return(opFunc(first->evaluate(tVal), last->evaluate(tVal))); 
    } 
    else if (isVar) 
    { 
     //if it's a var 
     return(tVal); 
    } 
    else 
    { 
     //if it's a number 
     return(value); 
    } 
} 



ExpressionTree::ExpressionTree() 
{ 
    treeRoot = NULL; 

    // http://en.cppreference.com/w/cpp/language/operator_precedence 
    precedence["*"] = 5; 
    precedence["/"] = 5; 
    precedence["%"] = 5; 
    precedence["+"] = 6; 
    precedence["-"] = 6; 
    precedence["<<"] = 7; 
    precedence[">>"] = 7; 
    precedence["&"] = 10; 
    precedence["^"] = 11; 
    precedence["|"] = 12; 
} 

ExpressionTree::~ExpressionTree() 
{ 
    destroyTree(); 
} 

void ExpressionTree::destroyTree(TreeNode *leaf) 
{ 
    if (leaf != NULL) 
    { 
     destroyTree(leaf->first); 
     destroyTree(leaf->last); 
     delete leaf; 
    } 
} 

TreeNode *ExpressionTree::insertNode(TreeNode *leaf) 
{ 
    if (leaf->first == NULL) 
    { 
     leaf->first = new TreeNode; 
     leaf->first->parent = leaf; 
     return(leaf->first); 
    } 
    else 
    { 
     leaf->last = new TreeNode; 
     leaf->last->parent = leaf; 
     return(leaf->last); 
    } 
} 

void ExpressionTree::destroyTree() 
{ 
    destroyTree(treeRoot); 
} 

bool ExpressionTree::build(std::string formulaStr) 
{ 
    std::string::iterator stringIterator; 
    std::vector<std::string>::iterator stringVectorIterator; 

    std::vector<std::string> formulaTokens; 
    std::vector<std::string> pnTokens; 
    std::stack<std::string> stringStack; 
    std::string currentNumString = ""; 
    std::string currentTokenString = ""; 
    std::stack<TreeNode> nodeStack; 
    TreeNode *currentNode; 
    std::string currToken; 
    bool treeIsDone; 

    //tokenization 

    for (stringIterator = formulaStr.begin(); stringIterator != formulaStr.end(); stringIterator++) 
    { 
     std::string currCharString(1, *stringIterator); 

     currentTokenString.push_back(*stringIterator); 

     if ((precedence.find(currentTokenString) != precedence.end()) || (currentTokenString == "(") || (currentTokenString == ")")) 
     { 
      //if the current token string is found in the precedence list (or is a parentheses) 
      if (currentNumString != "") 
      { 
       formulaTokens.push_back(currentNumString); 
       currentNumString = ""; 
      } 

      formulaTokens.push_back(currentTokenString); 
      currentTokenString = ""; 
     } 
     else if (std::all_of(currentTokenString.begin(), currentTokenString.end(), ::isdigit)) 
     { 
      //if the current token string is all digits 
      currentNumString.append(currentTokenString); 
      currentTokenString = ""; 
     } 
     else if (currentTokenString == "t") 
     { 
      //if the current token string is the t variable 
      formulaTokens.push_back(currentTokenString); 
      currentTokenString = ""; 
     } 
    } 

    //convert to polish notation 

    std::reverse(formulaTokens.begin(), formulaTokens.end()); 

    stringStack.push(")"); 

    for (stringVectorIterator = formulaTokens.begin(); stringVectorIterator != formulaTokens.end(); stringVectorIterator++) 
    { 
     currToken = *stringVectorIterator; 
     if ((precedence.find(currToken) == precedence.end()) && (currToken != "(") && (currToken != ")")) 
     { 
      pnTokens.push_back(currToken); 
     } 
     else if (currToken == ")") 
     { 
      stringStack.push(currToken); 
     } 
     else if (precedence.find(currToken) != precedence.end()) 
     { 
      if (stringStack.size() > 0) 
      { 
       if (stringStack.top() != ")") 
       { 
        while (precedence[stringStack.top()] <= precedence[currToken]) 
        { 
         if (stringStack.top() != ")") 
         { 
          pnTokens.push_back(stringStack.top()); 
          stringStack.pop(); 
         } 

         if (stringStack.size() <= 0) 
         { 
          break; 
         } 

         if (stringStack.top() == ")") 
         { 
          break; 
         } 
        } 
       } 
      } 
      stringStack.push(currToken); 
     } 
     else if (currToken == "(") 
     { 
      if (stringStack.size() > 0) 
      { 
       while (stringStack.top() != ")") 
       { 
        pnTokens.push_back(stringStack.top()); 
        stringStack.pop(); 

        if (stringStack.size() <= 0) 
        { 
         break; 
        } 
       } 

       stringStack.pop(); 
      } 
     } 
    } 

    while (stringStack.size() > 0) 
    { 
     if (stringStack.top() != ")") 
     { 
      pnTokens.push_back(stringStack.top()); 
     } 
     stringStack.pop(); 
    } 

    std::reverse(pnTokens.begin(), pnTokens.end()); 

    //if it's gotten this far, the formula was valid 
    //destroy the current tree to make room 

    destroyTree(); 

    //parse polish notation into tree 
    treeRoot = new TreeNode; 
    currentNode = treeRoot; 
    treeIsDone = false; 

    for (stringVectorIterator = pnTokens.begin(); stringVectorIterator != pnTokens.end(); stringVectorIterator++) 
    { 
     currToken = *stringVectorIterator; 
     if (precedence.find(currToken) != precedence.end()) 
     { 
      //if the token is an operator 
      currentNode->setOp(currToken); 

      currentNode = insertNode(currentNode); 
     } 
     else 
     { 
      //if it's a number or a variable 
      if (currentNode->first != NULL) 
      { 
       //if the current node has it's first branch initialized 
       while (currentNode->last != NULL) 
       { 
        //while the last branch is initialized 
        currentNode = currentNode->parent; 
       } 

       currentNode = insertNode(currentNode); 
      } 

      if (std::all_of(currToken.begin(), currToken.end(), ::isdigit)) 
      { 
       //if it's a number 
       currentNode->setVal((uint32_t)atoi(currToken.c_str())); 
      } 
      else 
      { 
       //if it's something else, a variable 
       currentNode->setVar(); 
      } 

      if (currentNode != treeRoot) 
      { 
       currentNode = currentNode->parent; 
      } 

      //since we just moved up, we know at least the first branch is used 
      //so only check the last 
      while (currentNode->last != NULL) 
      { 
       //if the last node is not free 
       if (currentNode == treeRoot) 
       { 
        //if we're at the root, and it's totally populated 
        treeIsDone = true; 
        break; 
       } 

       currentNode = currentNode->parent; 
      } 

      if (!treeIsDone) 
      { 

       currentNode = insertNode(currentNode); 
      } 
     } 
    } 
    return(true); 
} 

uint8_t ExpressionTree::evaluate(uint32_t tVal) 
{ 
    return((uint8_t)treeRoot->evaluate(tVal)); 
}