樹型迭代器，你可以進一步優化它嗎？

Question

作爲一個關於這段代碼的一小部分的原始問題的後續行動，我決定詢問一下後續內容，看看你能做得更好，然後我們到目前爲止所做的更好。

下面的代碼迭代二叉樹（左/右=子/下）。我相信這裏有一個條件較少的空間（down布爾值）。最快的答案獲勝！

1. 的cnt語句可以是多條語句所以讓我們確保這個只出現一次
2. 的child()和next()成員函數約30倍的hasChild（）和hasNext（）操作一樣慢。
3. 保持迭代< - 由於呈現的遞歸解決方案速度更快，因此放棄了此要求。
4. 這是C++代碼
5. 節點的訪問順序必須保持原樣，如下例所示。 （首先打擊父母，然後是孩子，然後是'下一個'節點）。
6. BaseNodePtr是一個boost :: shared_ptr，因此賦值很慢，避免了任何臨時的BaseNodePtr變量。

目前這段代碼需要5897ms訪問測試樹中的62200000個節點，調用這個函數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. 
     } 
    } 
} 

Answer 1

爲什麼不是遞歸解決方案？

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代替？

Answer 2

創建一個「nextvisit」函數，並繼續調用該函數，以簡化代碼;旁邊，使用常量引用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); 
    }   
} 

但對於可讀性，清晰性，可維護性，...看在上帝的份上，使用遞歸。除非你的堆棧不夠大。

Answer 3

我HATE當答案解僱了「不這樣做，」但在這裏我去的問題...

說有一種方法來去除下來布爾......將那真的讓執行時間有任何真正的區別？我們正在談論少量的CPU操作，並在堆棧上多加幾個字節。

如果您需要速度，請重點關注如何使child（）和parent（）調用更快。否則你會浪費你的時間（IMOHO）。

編輯： 也許走樹（w /這個「慢」代碼）ONCE並建立一個指針數組到所需的順序樹中。稍後使用此「索引」。

我在說的是我認爲你正在從錯誤的角度接近優化。

Answer 4

這裏是如何只有一個遞歸調用，而不是兩個：

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(); 
    } 
} 

Answer 5

對於最終的加快，你需要做的是爲了在內存中的節點，以便它們存儲在一個連續的塊您訪問它們的順序。

例如如果你有一棵樹定義如下。

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

然後，訪問功能如所描述的，如果你爲了在存儲器節點作爲15只分配一個連續塊將訪問以下列順序

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

現在的節點和存儲節點的順序如上所示，那麼您通常會訪問具有「spatial locality」的節點。這可以提高緩存命中率，具體取決於節點結構的大小，從而使事情運行得更快。

創建一個訪問樹中所有節點的快速迭代方法，只有一次，沒有遞歸。

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會消除上述迭代方法提供的所有優點。

希望有些幫助:)