树迭代器，你能进一步优化吗？ [英] Tree iterator, can you optimize this any further?

问题描述

作为对原始问题的跟进，关于这段代码的一小部分我决定跟进，看看你能做得更好，然后到目前为止我们想出的。

As a follow up to my original question about a small piece of this code I decided to ask a follow up to see if you can do better then what we came up with so far.

下面的代码遍历二叉树（左/右=子/下）。我相信这里有一个更少条件的空间（ down 布尔值）。最快的答案获胜！

The code below iterates over a binary tree (left/right = child/next ). I do believe there is room for one less conditional in here (the down boolean). The fastest answer wins!

1. cnt 语句可以是多个语句，所以让我们做确保只出现一次


2. child（）和 next（）成员函数的速度大约是hasChild（）和hasNext（）操作的30倍。


3. 保持迭代< - 删除此要求，因为呈现的递归解决方案更快。


4. 这是C ++代码


5. 节点的访问顺序必须保持原样，如下例所示。 （先点击父母，然后是孩子，然后是'下一个'节点）。


6. BaseNodePtr是一个boost :: shared_ptr，因为赋值很慢，避免任何临时的BaseNodePtr变量。

1. The cnt statement can be multiple statements so lets make sure this appears only once
2. The child() and next() member functions are about 30x as slow as the hasChild() and hasNext() operations.
3. Keep it iterative <-- dropped this requirement as the recursive solution presented was faster.
4. This is C++ code
5. visit order of the nodes must stay as they are in the example below. ( hit parents first then the children then the 'next' nodes).
6. BaseNodePtr is a boost::shared_ptr as thus assignments are slow, avoid any temporary BaseNodePtr variables.

目前，此代码需要5897ms才能访问测试树中的62200000个节点，将此功能调用200,000次。

Currently this code takes 5897ms to visit 62200000 nodes in a test tree, calling this function 200,000 times.

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.
        }
    }
}

推荐答案

为什么不是递归解？

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 引用计数由互斥锁保护，这可能是性能降低的原因。

Since shared_ptr seems to be your bottleneck, why not improve it? Are you using threads? If not, then undefine the symbol BOOST_HAS_THREADS. The shared_ptr reference count is guarded by a mutex which is probably the cause of the slow performance.

为什么不更改你的数据结构完全没有使用 shared_ptr ？自己管理原始指针？也许使用 scoped_ptr ？

Why not change your data structure to not use shared_ptr altogether? Manage the raw pointers yourself? Maybe use scoped_ptr instead?

这篇关于树迭代器，你能进一步优化吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！