Raised This Month: $ Target: $400
 0% 

Recursion. Is it a big performance impact in amxx?


Post New Thread Reply   
 
Thread Tools Display Modes
Author Message
vilaemail
Member
Join Date: Jan 2009
Location: Tu i tamo, svuda pomalo
Old 02-06-2010 , 13:42   Recursion. Is it a big performance impact in amxx?
Reply With Quote #1

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);
} 
__________________
If you are putting me to credits of some kind please put "Filip Vilicic" instead of "vilaemail". Or put both. Thanks.
vilaemail is offline
Owyn
Veteran Member
Join Date: Nov 2007
Old 02-06-2010 , 15:56   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #2

what are you trying to make?

you can allways use profiler
__________________
☜ Free Mozy ☂backup\҉sync user
Quote:
Американский форум - Задаёшь вопрос, потом тебе отвечают.
Израильский форум - Задаёшь вопрос, потом тебе задают вопрос.
Русский форум - Задаёшь вопрос, потом тебе долго рассказывают, какой ты мудак.

Last edited by Owyn; 02-06-2010 at 15:59.
Owyn is offline
Send a message via ICQ to Owyn
Emp`
AMX Mod X Plugin Approver
Join Date: Aug 2005
Location: Decapod 10
Old 02-06-2010 , 20:18   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #3

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;
}
Emp` is offline
Send a message via AIM to Emp` Send a message via MSN to Emp` Send a message via Yahoo to Emp` Send a message via Skype™ to Emp`
joropito
AlliedModders Donor
Join Date: Mar 2009
Location: pfnAddToFullPack
Old 02-06-2010 , 21:07   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #4

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

Divide et vinces
approved plugins | steam account

I don't accept PM for support. Just ask on forums.
If you're looking for private work, PM me.
joropito is offline
Send a message via MSN to joropito
vilaemail
Member
Join Date: Jan 2009
Location: Tu i tamo, svuda pomalo
Old 02-07-2010 , 04:56   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #5

Quote:
Originally Posted by Owyn View Post
what are you trying to make?

you can allways use profiler
Thank you big time. Will try it immediately!
__________________
If you are putting me to credits of some kind please put "Filip Vilicic" instead of "vilaemail". Or put both. Thanks.
vilaemail is offline
vilaemail
Member
Join Date: Jan 2009
Location: Tu i tamo, svuda pomalo
Old 02-07-2010 , 04:57   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #6

Quote:
Originally Posted by Emp` View Post
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.
__________________
If you are putting me to credits of some kind please put "Filip Vilicic" instead of "vilaemail". Or put both. Thanks.
vilaemail is offline
vilaemail
Member
Join Date: Jan 2009
Location: Tu i tamo, svuda pomalo
Old 02-07-2010 , 05:11   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #7

I found function very fast.

Thank you all for your help.
__________________
If you are putting me to credits of some kind please put "Filip Vilicic" instead of "vilaemail". Or put both. Thanks.
vilaemail is offline
joropito
AlliedModders Donor
Join Date: Mar 2009
Location: pfnAddToFullPack
Old 02-07-2010 , 07:30   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #8

Quote:
Originally Posted by vilaemail View Post
I found function very fast.

Thank you all for your help.
Why don't you post your solution here?
__________________

Divide et vinces
approved plugins | steam account

I don't accept PM for support. Just ask on forums.
If you're looking for private work, PM me.
joropito is offline
Send a message via MSN to joropito
Sylwester
Veteran Member
Join Date: Oct 2006
Location: Poland
Old 02-07-2010 , 08:43   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #9

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.
__________________
Impossible is Nothing
Sylwester is offline
vilaemail
Member
Join Date: Jan 2009
Location: Tu i tamo, svuda pomalo
Old 02-07-2010 , 10:02   Re: Recursion. Is it a big performance impact in amxx?
Reply With Quote #10

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.
__________________
If you are putting me to credits of some kind please put "Filip Vilicic" instead of "vilaemail". Or put both. Thanks.

Last edited by vilaemail; 02-07-2010 at 10:08.
vilaemail is offline
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


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


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