このツリーのトラバーサルをより効率的にするにはどうすればよいですか？

Question

私は一連のルールを処理するプロジェクトを持っています。現在のルールは、1つまたは複数の句で構成され、構文はそのようなので、見えます：

struct Rule { 
    list<Clause*> Clauses; 
}; 

bool ProcessRule(const Rule* Rule) { 
    for (const auto& Clause : Rule->Clauses) { 
     if (!ProcessClause(Clause)) return false; 
    } 
    return true; 
} 

私は、無料の論理を実装するか、構築する使命を帯びています：以下のように

A 
A & B 
A & B & C 
etc 

これが成文化されましたそのように見えたの構文：

A 
A & B 
A | B 
A & B & C 
A & B | C 
A | B & C 
A | B | C 
etc 

私が最も明白なアプローチを行って、使用してリストを使用してから、Rule構造の実装を変更ツリー：

enum NodeType { 
    LogicalAnd, 
    LogicalOr, 
    Leaf, 
}; 

struct Node { 
    NodeType Type; 
}; 

struct LogicalNode : Node { 
    list<Node*> Children; 
}; 

struct LeafNode : Node { 
    Clause* Clause; 
}; 

struct Rule { 
    Node* Root; 
} 

bool ProcessRule(const Rule* Rule) { 
    return ProcessNode(Rule->Root); 
} 

bool ProcessNode(const Node* Node) { 
    switch (Node->Type) { 
     case LogicalAnd: 
      for (const auto& Child : ((const LogicalNode*)Node)->Children) { 
       if (!ProcessNode(Child)) return false; 
      } 
      return true; 
     case LogicalOr: 
      for (const auto& Child : ((const LogicalNode*)Node)->Children) { 
       if (ProcessNode(Child)) return true; 
      } 
      return false; 
     case Leaf: 
      return ProcessClause(((const LeafNode*)Node)->Clause); 
    } 
} 

それはすべての非常に簡単そうですが、問題は、15％程度のオーダーのルールの正確な同じセットを使用して、パフォーマンスの比較的深刻な劣化です。私は両方のバージョンをプロファイラで実行しましたが、劣化はProcessNode()関数のオーバーヘッドに起因しています。私はswitch文と関数呼び出しのために仮定します。ProcessRule()は何百万回も呼び出されます。このオーバーヘッドを軽減する方法はありますか？それは少し過度に見えるので、私は明らかな何かを見逃しているように感じる。

Answer 1

スイッチを取り除き、AndNodeとOrNodeクラスを追加し、適切なオーバーライドを持つ仮想関数を使用します。