提高递归函数的速度 [英] improve speed of recursive function

问题描述

我正在使用的递归函数的布局如下

Layout of recursive function that I am using is below

fun1()
{
for()
  {
    for()
     {
        if (this)
           {
            .....
           fun2()
           }
        else
           {
            ....
           fun2()
           }
     } 
  }
}


fun2()
{
 .........
........
   fun1();

}

它可以按我的要求很好地工作.唯一的限制是速度.多线程可以解决问题吗?或任何其他解决方案..或您没有解决方案.. thanx提前

It works fine as I want. The only constraint is speed. Can multithreading solve the problem ? or any another solution.. or u have no solution.. thanx in advance

推荐答案

哇！两个嵌套循环和递归！这一定很慢.
你到底在做什么?计算矩阵行列式?
当然，有更好的算法可用且免费.只是在谷歌上搜索它们(您也可以在CodeProject上找到它们).

Wow! Two nested for cycles AND recursion! This must be really slow.
What in the earth are you doing? Calculating matrix determinants?
Of course there are way better algorithms available and free. Just google for them (you can also find some here on CodeProject).

如果正确执行多线程处理可能会有所帮助，但是存在两个基本问题:

首先，是否可以并行执行此任务取决于代码的"...."部分.

其次，即使您拥有四核处理器，也最多可以获得4倍的加速，这对于像这样的算法来说还不够.

快速的理论评估(为什么多线程无济于事):算法的复杂性类似于(m * n) ^ (levels)，其中m和n代表第一和第二个循环的迭代次数，而levels是平均值递归级别.因此，如果您的任务平均需要执行10个级别的递归，则将得到(m * n) ^ 10，无论您使用多少个线程，它都将永远占用...

我猜您将不得不更加努力地创建更好的算法，如果不可能，那么您将必须非常非常有耐心...

Multithreading might help a bit if you do it properly, but there are 2 basic problems:

first, it depends on the "...." pieces of your code whether this task can be parallelized or not.

second, even if you had a quad-core processor, you could get at most 4x speedup which is not quite enough for an algorithm like this.

A quick theoretical evaluation (why multithreading does not help): the complexity of your algorithm is somemething like (m * n) ^ (levels), where m and n represent the number of iterations of the first and second loop and levels is the average level of recursion. So if your task needs in average say 10 levels of recursion to execute, you will get (m * n) ^ 10, which will probably take forever no matter how many threads you use...

I guess you will have to try harder to create a better algorithm and if it''s not possible, then you''ll have to be very, very patient...

WOW，只需WOW，2即可实现循环和递归.如果不知道每个....在做什么，很难说.也许您可以不露面地显示一些代码，而不必显示它们以提供更多细节.

如果您可以使用并行代码，那么多线程只会给您带来优势，否则会带来更大的麻烦.只需一段代码就可以锁定另一段代码，而地狱之门就会打开.


也许您可以重构....中的内容，而又不知道那里有什么，那就很难说了.

WOW, simply WOW, 2 for loops and recursion. It simply is hard to say with out knowing what each .... is doing. May be you can show some code with out exposion what ever you don''t want to show to give more detail.

Multithreading only gives you an advantage if you can have parallel code, otherwise you are inviting bigger headache. Simply one piece of code may lock other piece and the gates of hell will open loose.


May be you can refactor what is in the ...., again with out seeing what is there it is simply hard to tell.

这篇关于提高递归函数的速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！