1

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

下面的代码遍历二叉树（left/right = child/next）。我确实相信这里有一个不那么有条件的空间（down布尔值）。最快的答案获胜！

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

目前这段代码访问一个测试树中的62200000个节点需要5897ms，调用这个函数200000次。

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

5 回答 5

5

为什么不是递归解决方案？

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改用？

于 2009-08-19T20:19:10.107 回答
3

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

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

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

希望这是一些帮助:)

于 2009-08-19T21:32:22.627 回答
1

创建一个“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);
   }        
}

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

于 2009-08-19T20:28:17.983 回答
1

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

假设有一种方法可以删除 down bool ......这真的会对执行时间产生任何真正的影响吗？我们谈论的是少量的 CPU 操作和堆栈上的一些额外字节。

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

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

我的意思是我认为你从错误的角度接近优化。

于 2009-08-19T20:41:23.010 回答
1

以下是如何只有一个递归调用而不是两个：

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();
  }
}
于 2009-08-19T21:22:45.313 回答