AlliedModders

AlliedModders (https://forums.alliedmods.net/index.php)
-   Scripting Help (https://forums.alliedmods.net/forumdisplay.php?f=11)
-   -   Recursion. Is it a big performance impact in amxx? (https://forums.alliedmods.net/showthread.php?t=117954)

vilaemail 02-06-2010 13:42

Recursion. Is it a big performance impact in amxx?
 
Hi. Let's say that I need recursive function and the maximum times it calls itself is about 15.

Two questions:
  • How many recursive calls may there be in amxx?
  • Will that number of calls (15) make a big impact to my code performance? Since I need it done fast.
My function:

Code:

gcd(a,b) {

if (b==0)
return a;
else
return gcd(b, a % b);
}


Owyn 02-06-2010 15:56

Re: Recursion. Is it a big performance impact in amxx?
 
what are you trying to make?

you can allways use profiler

Emp` 02-06-2010 20:18

Re: Recursion. Is it a big performance impact in amxx?
 
Assuming your function is trying to find the greatest common denominator, you can use the following:

Code:

gcd( a, b )
{
  for( new i=min(a,b); i>0; i-- )
  {
      if( (a%i) == 0 && (b%i) == 0 )
        return i;
  }
  return 0;
}


joropito 02-06-2010 21:07

Re: Recursion. Is it a big performance impact in amxx?
 
Some time ago I had the same question.

I think using stock for recursion will be better than a function.

I don't have an example, but think in a recursive stock/function that runs over a graph (to find all relations, bigger, best route, etc).

Of course the size of graph will be the key performance.

vilaemail 02-07-2010 04:56

Re: Recursion. Is it a big performance impact in amxx?
 
Quote:

Originally Posted by Owyn (Post 1080704)
what are you trying to make?

you can allways use profiler

Thank you big time. Will try it immediately!

vilaemail 02-07-2010 04:57

Re: Recursion. Is it a big performance impact in amxx?
 
Quote:

Originally Posted by Emp` (Post 1081009)
Assuming your function is trying to find the greatest common denominator, you can use the following:

Code:

gcd( a, b )
{
  for( new i=min(a,b); i>0; i-- )
  {
      if( (a%i) == 0 && (b%i) == 0 )
        return i;
  }
  return 0;
}


Your code is not optimized. For example if I have numbers 50 and 45.. Why would I test if both of them are dividable by 44, 43 etc. It is much easier to start from half of the bigger number AND EVEN BETTER look up table with simple numbers to hundred (since I am not going pass that).

But as you can see recursive function should be the best solution.

vilaemail 02-07-2010 05:11

Re: Recursion. Is it a big performance impact in amxx?
 
I found function very fast.

Thank you all for your help.

joropito 02-07-2010 07:30

Re: Recursion. Is it a big performance impact in amxx?
 
Quote:

Originally Posted by vilaemail (Post 1081324)
I found function very fast.

Thank you all for your help.

Why don't you post your solution here?

Sylwester 02-07-2010 08:43

Re: Recursion. Is it a big performance impact in amxx?
 
It's probably this:
PHP Code:

public gcd(a,b){
    new 
c
    
while(b!=0){
        
c=a%b
        a
=b
        b
=c
    
}
    return 
a


Iterative version of function from first post.

vilaemail 02-07-2010 10:02

Re: Recursion. Is it a big performance impact in amxx?
 
Solution so to say is what I first posted:

Code:

gcd(a,b) {

if (b==0)
return a;
else
return gcd(b, a % b);
}

I called function with this parameters:
Code:

200,195
1856,1947
125,324
200,200
456,1875
200,195

I got correct results, and this:

Code:

type |name | calls | time / min / max
  f | gcd |33 | 0.000073 / 0.000001 / 0.000008

So average time is around 0.000002~3, which is great.

EDIT: I find recursion much more elegant than while loop.


All times are GMT -4. The time now is 07:19.

Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.