树迭代器，你能进一步优化它吗？

Question

作为我最初关于一小段代码的问题的后续行动，我决定提出后续行动，看看您是否可以做得比我们迄今为止提出的更好。

下面的代码迭代二叉树（左/右=子/下一个）。我确实相信这里有空间容纳一个较少的条件（down 布尔值）。最快回答者获胜！

1. cnt 语句可以是多个语句，因此请确保它仅出现一次
2. child() 和 next() 成员函数大约为 30 倍与 hasChild() 和 hasNext() 操作一样慢。
3. 保持迭代<--放弃了这个要求，因为提出的递归解决方案更快。
4. 这是 C++ 代码，
5. 节点的访问顺序必须保持如下例所示。 （首先击中父节点，然后击中子节点，然后击中“下一个”节点）。
6. BaseNodePtr 是 boost::shared_ptr，因此分配速度很慢，请避免任何临时 BaseNodePtr 变量。

目前，此代码需要 5897 毫秒来访问测试树中的 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 ¤t, 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

为了最终加快速度，您需要做的就是对内存中的节点进行排序，以便它们按照您访问它们的顺序存储在连续的块中。

例如，如果您有一棵定义如下的树。

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

然后，所描述的访问函数将按以下顺序访问节点

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

现在，如果您将内存中的节点排序为 15 个分配的连续块，并按照上面演示的顺序存储节点，那么您通常会访问具有“空间局部性"。这可以提高缓存命中率，具体取决于节点结构的大小，从而使运行速度更快。

创建一种快速迭代方法，仅访问树中的所有节点一次并且无需递归。

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

希望有一些帮助:)

Answer 3

我讨厌当答案用“不要那样做”来驳回问题时，但我走了......

假设有一种方法可以删除下布尔......这真的会对执行时间产生真正的影响吗？我们讨论的是一小部分 CPU 操作和堆栈上的一些额外字节。

如果您需要速度，请专注于使 child() 和 Parent() 调用更快。否则你就是在浪费时间（恕我直言）。

编辑：
也许遍历树（使用这个“慢”代码）一次并按照所需的顺序将指针数组构建到树中。稍后使用这个“索引”。

我想说的是，我认为你从错误的角度进行优化。

Answer 4

以下是如何只进行一次递归调用而不是两次：

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

Answer 5

创建一个“nextvisit”函数，并继续调用它，以简化代码；接下来，对共享指针使用 const 引用 iso 值语义...这可能会为您节省宝贵的共享指针副本：

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

但是为了可读性、清晰度、可维护性，...看在上帝的份上，请使用递归。除非你的筹码不够大。