力为的技术博客
联系 聚合 管理
  154 Posts :: 1 Stories :: 561 Comments :: 0 Trackbacks
递归引起的性能问题


程序模型

有类似这样的一个数据结构：

class MyData
{
public:
  MyData* Clone() const;


private:
  Array<MyData> m_arrData;
}

现在需要实现MyData::Clone方法，很自然的会使用这样的方法实现：

MyData* MyData::Clone() const
{
  MyData* pData = new MyData;
  const int nSize = m_arrData.size();
  pData->m_arrData.resize(nSize);
  for(int ii=0;ii<nSize; ++ii)
    pData[ii] = m_arrData[ii]->Clone();

  return pData;
}

姑且称m_arrData中的数据为MyData对象的子节点。假如MyData的某个对象有N层孙子节点。当调用Clone的时候，非常有可能发生堆栈溢出的情况。

在实际的应用的时候发现，在堆栈溢出的时候不会抛出异常，会有假死的症状，CPU会用满，出现程序好像还在艰难的思考的假象。

解决办法: 用循环代替递归调用。

疗效：程序变快了

注意：递归可以方便直观的实现算法，但有时候却会大大的影响程序性能，甚至引发程序非正常死亡。
posted on 2010-03-24 14:24 力为 阅读(2783) 评论(3)  编辑 收藏 引用 所属分类: 4. C++ FAQ

评论

# re: 递归引起的性能问题 2010-03-24 23:48 Quon
尾递归是解决优雅代码和性能的良方  回复  更多评论
  

# re: 递归引起的性能问题 2010-03-25 17:09 力为
关于尾递归：

尾递归与Continuation
http://blog.csdn.net/fisher_jiang/archive/2009/04/29/4133533.aspx  回复  更多评论
  

# re: 递归引起的性能问题 2010-03-26 16:58 sigepluto
正解，用尾递归就好了。  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理