树型迭代器，你可以进一步优化它吗？

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会消除上述迭代方法提供的所有优点。

希望有些帮助:)