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

Question

作为我关于这段代码的一小段原始问题的后续跟踪,我决定跟进,看看你能做得更好,然后到目前为止我们想出的是什么.

下面的代码遍历二叉树(左/右=子/下).我相信这里有一个较少的条件空间(down布尔值).最快的答案获胜!

1. 该cnt语句可以是多个语句,因此请确保它只出现一次
2. 的child()和next()成员函数约为30X一样慢的hasChild()和hasNext()操作.
3. 保持迭代< - 放弃此要求,因为呈现的递归解决方案更快.
4. 这是C++代码
5. 访问节点的顺序必须保持原样,如下例所示.(首先击中父母然后是孩子然后是'下一个'节点).
6. BaseNodePtr是一个boost :: shared_ptr,因为赋值很慢,避免任何临时的BaseNodePtr变量.

目前,此代码在测试树中访问62200000个节点需要5897ms,将此功能调用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呢？