2016-10-29 11 views
1

この質問がここにあるのかソフトウェアエンジニアリングなのかは完全にはわかりませんが、私はC++の実装に特に関心があるのでここで尋ねています。一般的なツリートラバーサルの分岐を減らす

これで、プリ・オーダー、イン・オーダー、ポスト・オーダーを1つに処理するための汎用のトラバース関数を持つ基本バイナリ・ツリーを実装しました。

void BiTree::_trav(BiNode* root, int offset, function<void (int&,int&)> lambda) { 

    if (root == NULL) {return;} 
    auto call = [&]() {lambda(root->data, root->sc);}; 

    if (offset == 0) { call();} 

    _trav(root->child[0], offset, lambda); 

    if (offset == 1) { call();} 

    _trav(root->child[1], offset, lambda); 

    if (offset == 2) { call();} 
} 

ご覧のとおり、この関数は再帰的に呼び出し、多くの分岐を持ちます。 C++のラムダやC++のラムダについて誰もが知っているわけではないので(私は昨日はなかった)、同じアイデアが問題に還元されました。

私のプログラミングの直感では、分岐を少なくしてより良い方法があると言われていますが、私はどのように理解できません。 switch文は、do-thing()が複数回呼び出されたり、さらに分岐しているため動作しません。だから私は、最小の分岐で一般的なツリートラバーサルを行う方法に興味があります。

+0

オールインワンで最大のパフォーマンスは、矛盾した目標になる傾向があります。それぞれの関数が5行のコードであることを前提に、3つの別々の関数、すなわち、先行予約、順不同、および後予約の3つの関数を記述することによって最大のパフォーマンスが達成されます。それは分岐を排除するだけでなく、呼び出しごとに 'offset 'を渡す必要もなくなります。 – user3386109

答えて

1

私はダミー関数の配列を使って私自身の質問に答えています。実際に実行したい場所で実行したいコードを関数に挿入しています。これでパフォーマンスが向上するかどうかはわかりませんが、分岐が少なくなっているようです。

void BiTree::_trav(BiNode* root, int offset, function<void (int&,int&)> lambda) { 
    if (root == NULL) {return;} 

    function<void (void)> branches[3]; 
    for(int i = 0; i < 3; i++) { 
     branches[i] = [&]() {}; 
    } 
    function<void (void)> call = [&]() {lambda(root->data, root->sc);}; 
    branches[offset] = call; 

    branches[0](); 

    _trav(root->child[0], offset, lambda); 

    branches[1](); 

    _trav(root->child[1], offset, lambda); 

    branches[2](); 
} 
関連する問題