c++ - ツリー反復子、これをさらに最適化できますか?

Question

このコードの小さな部分に関する最初の質問のフォローアップとして、これまでに思いついたものよりもうまくできるかどうかを確認するためにフォローアップを依頼することにしました。

以下のコードは、二分木 (左/右 = 子/次) を反復処理します。downここには、条件式 (ブール値)を 1 つ減らす余地があると思います。最速の答えが勝ちます！

ステートメントは複数のcntステートメントになる可能性があるため、これが 1 回だけ表示されるようにします。
child()およびnext()メンバー関数は、hasChild() および hasNext() 操作の約 30 倍遅くなります。
反復を維持 <-- 提示された再帰的なソリューションがより高速だったため、この要件を削除しました。
これは C++ コードです
ノードの訪問順序は、以下の例のように維持する必要があります。(最初に親をヒットし、次に子をヒットし、次に「次の」ノードをヒットします)。
BaseNodePtr は boost::shared_ptr であるため、割り当てが遅いため、一時的な BaseNodePtr 変数は避けてください。

現在、このコードはテストツリー内の 62200000 ノードにアクセスするのに 5897 ミリ秒かかり、この関数を 200,000 回呼び出しています。

void processTree (BaseNodePtr current, unsigned int & cnt )
{
    bool down = true;

    while ( true )
    {
        if ( down )
        {
            while (true) {

                cnt++; // this can/will be multiple statesments

               if (!current->hasChild()) break;
               current = current->child();
            }
        }

        if ( current->hasNext() )
        {
            down = true;
            current = current->next();
        }
        else
        {
            down = false;
            current = current->parent();
            if (!current)
                return; // done.
        }
    }
}

score 5 · Accepted Answer

再帰的なソリューションではないのはなぜですか?

void processTree (const BaseNodePtr &current, unsigned int & cnt )
{
  cnt++;

  if (current->hasChild())
    processTree(current->child());
  if (current->hasNext())
    processTree(current->next());
}

あなたのボトルネックのように見えるのでshared_ptr、それを改善しませんか? スレッドを使用していますか？そうでない場合は、シンボルを未定義にしますBOOST_HAS_THREADS。参照カウントは、shared_ptrおそらくパフォーマンス低下の原因であるミューテックスによって保護されています。

データ構造をまったく使用しないように変更してみませんshared_ptrか? 生ポインタを自分で管理しますか? たぶんscoped_ptr代わりに使用しますか？

score 3 · Accepted Answer

究極のスピードアップのために必要なことは、メモリ内のノードを並べ替えて、アクセスした順序で連続したブロックに格納されるようにすることです。

たとえば、次のように定義されたツリーがあるとします。

        1
       / \
      2   3
     / \  /\
    4   5 6 7
   /\    /  /\
  8  9  10 11 12
 / \           \
13 14          15

次に、説明した訪問機能が次の順序でノードを訪問します。

ここで、メモリ内のノードを 15 個の割り当ての連続したブロックとして順序付けし、ノードを上記の順序で格納すると、通常、「空間的局所性」を持つノードにアクセスすることになります。これにより、ノード構造のサイズに応じてキャッシュヒットが改善され、実行速度が向上します。

ツリー内のすべてのノードを 1 回だけ、再帰なしで訪問する迅速な反復方法を作成する。

unsigned int g_StackDepth = 0;
BaseNodePtr* g_Stack[MAX_STACK_DEPTH];

void processTree (BaseNodePtr root, unsigned int & cnt )
{
    g_Stack[g_StackDepth++] = root;
    while( g_StackDepth > 0 )
    {
        BaseNodePtr curr = g_Stack[--g_StackDepth];
        cnt++;

        if ( curr->HasNext() )
        {
            g_Stack[g_StackDepth++] = curr->Next();
        }


        if ( curr->HasChild() )
        {
            g_Stack[g_StackDepth++] = curr->Child();
        }

    }
}

上記の順序と組み合わせると、私の知る限り、得ることができる最高の速度が得られるはずです。

スタックがどれだけ大きくなる可能性があるかを事前に知る必要があるため、明らかにこれには制限があります。代わりに std::vector を使用することでこれを回避できますが。ただし、 std::vector を使用すると、上記の反復法が提供するすべての利点が失われます。

それが助けになることを願っています:)

score 1 · Accepted Answer

再帰呼び出しを2回ではなく1回だけにする方法は次のとおりです。

void processTree (const BaseNodePtr &current, unsigned int & cnt )
{
  for(bool gotNext = true; gotNext; current = current->next()) { 
    cnt++;
    if (current->hasChild())
      processTree(current->child());
    gotNext = current->hasNext();
  }
}

score 1 · Accepted Answer

答えが「それをしないでください」で質問を却下するのは嫌いですが、ここに行きます...

ダウンブールを削除する方法があったとしましょう...それは本当に実行時間に実際の違いをもたらしますか? ほんの一握りの CPU 操作と、スタック上の数バイトの追加について話しているのです。

速度が必要な場合は、child() および parent() の呼び出しを高速化することに重点を置いてください。それ以外の場合は、時間を無駄にしています (IMOHO)。

編集:おそらく、ツリー(この「遅い」コードを使用)を1回歩き、ツリーへのポインターの配列を目的の順序で構築します。この「インデックス」を後で使用します。

私が言いたいのは、あなたは間違った角度から最適化に取り組んでいると思うということです。

score 1 · Accepted Answer

「nextvisit」関数を作成し、それを呼び出し続けて、コードを簡素化します。その次に、共有ポインターに const 参照 iso 値セマンティクスを使用します...これにより、貴重な共有 ptr コピーを節約できます。

// define the order of visitation in here
BaseNodePtr& next( const BaseNodePtr& p ) {
    if( p->hasChild() ) return p->child();
    if( p->hasNext() ) return p->next();
    BaseNodePtr ancestor = p->parent();
    while( ancestor != 0 && !ancestor->hasNext() ) ancestor = ancestor->parent();
    return ancestor;
}

void processTree( const BaseNodePtr& p, unsigned int& cnt ) {
   while( p != NULL ) {
     ++cnt;
     p = next(p);
   }        
}

しかし、読みやすさ、明快さ、保守性のために...念のため、再帰を使用してください。スタックが十分に大きくない限り。

c++ - ツリー反復子、これをさらに最適化できますか?

5 に答える 5

Related

Reference