Raised This Month: $60 Target: $400
 15% 

Which method is more efficient?


Post New Thread Reply   
 
Thread Tools Display Modes
Author Message
Siveroo
Junior Member
Join Date: Apr 2020
Old 10-13-2020 , 11:10   Which method is more efficient?
Reply With Quote #1

i have two functions that will generate a random xy coordinate within a certain radius, i don't really care about uniform distribution or something like that. which one of these function is more efficient, and why? or maybe you can show me another code that's actually more efficient than these two codes.

Btw, i don't care about the whether result being a float or an integer, i will use the coordinate both as a float and an integer later in my code

Code:
stock random_coord(coord[2], range) {     new newCoord[2];             newCoord[0] = coord[0] + random_num(-range, range);     newCoord[1] = coord[1] + random_num(-range, range);         while ( get_distance(iOrigin, Origin) > range ) {         newCoord[0] = coord[0] + random_num(-range, range);         newCoord[1] = coord[1] + random_num(-range, range);     doSomething(newCoord[0]);     doSomething(newCoord[1]); }


Code 2:
Code:
stock random_coord(Origin[2], range){     new Float:rand_coord[2]     new Float:theta     new Float:r     new Float:rand[2]             rand[0] = random_float(0.0, 1.0);   //randomize the smaller radius     rand[1] = random_float(0.0, 1.0);   //randomize the angle multiplication factor     r = FLAME_RADIUS * rand[0]     theta = rand[1] * 6                 // i use 6 instead of 2*PI , don't judge me (dont really need extra accuracy)     rand_coord[0] = r*floatcos(theta, radian)     rand_coord[1] = r*floatsin(theta, radian)        doSomething(Origin[0] + rand_coord[0]);     doSomething(Origin[1] + rand_coord[1]); }

Note : there might be some error, but i hope you can understand how each code works

Last edited by Siveroo; 10-13-2020 at 11:13.
Siveroo is offline
Natsheh
Veteran Member
Join Date: Sep 2012
Old 10-13-2020 , 15:01   Re: Which method is more efficient?
Reply With Quote #2

PHP Code:
random_coord_within_region(Float:xFloat:yradius=5.0Float:random_coord[2])
{
   
random_coord[0] = random_float(-radiusradius) + x;
   
random_coord[1] = random_float(-radiusradius) + y;


shouldn't be so complicated.
__________________
@User Tag Prefix 100% done !
@Mystery Box 100% done !
@VIP System 100% done !

Last edited by Natsheh; 10-13-2020 at 15:02.
Natsheh is offline
Send a message via MSN to Natsheh Send a message via Skype™ to Natsheh
Siveroo
Junior Member
Join Date: Apr 2020
Old 10-14-2020 , 00:50   Re: Which method is more efficient?
Reply With Quote #3

Quote:
Originally Posted by Natsheh View Post
PHP Code:
random_coord_within_region(Float:xFloat:yradius=5.0Float:random_coord[2])
{
   
random_coord[0] = random_float(-radiusradius) + x;
   
random_coord[1] = random_float(-radiusradius) + y;


shouldn't be so complicated.
but i think that will result in a rectangular region instead of a circle
Siveroo is offline
Black Rose
Veteran Member
Join Date: Feb 2011
Location: Upplands Väsby, Sweden
Old 10-15-2020 , 14:50   Re: Which method is more efficient?
Reply With Quote #4

Code:
stock random_coord1(coord[2], range) {     new newCoord[3], tempCoord[3];     tempCoord[0] = coord[0];     tempCoord[1] = coord[1];     do {         newCoord[0] = tempCoord[0] + random_num(-range, range);         newCoord[1] = tempCoord[1] + random_num(-range, range);     }     while ( get_distance(newCoord, tempCoord) > range ) }

I don't understand the second code so I'm not sure if it's correct. That itself should be a reason to chose the first code. But the first code is faster as well.

Spoiler
__________________

Last edited by Black Rose; 10-15-2020 at 14:58.
Black Rose is offline
HamletEagle
AMX Mod X Plugin Approver
Join Date: Sep 2013
Location: Romania
Old 10-16-2020 , 02:04   Re: Which method is more efficient?
Reply With Quote #5

Quote:
Originally Posted by Natsheh View Post
PHP Code:
random_coord_within_region(Float:xFloat:yradius=5.0Float:random_coord[2])
{
   
random_coord[0] = random_float(-radiusradius) + x;
   
random_coord[1] = random_float(-radiusradius) + y;

This is generating points inside the rectangle R(x - radius, x + radius, y - radius, y + radius), not in a circle.




Quote:
Originally Posted by Black Rose View Post
Code:
stock random_coord1(coord[2], range) {     new newCoord[3], tempCoord[3];     tempCoord[0] = coord[0];     tempCoord[1] = coord[1];     do {         newCoord[0] = tempCoord[0] + random_num(-range, range);         newCoord[1] = tempCoord[1] + random_num(-range, range);     }     while ( get_distance(newCoord, tempCoord) > range ) }

I don't understand the second code so I'm not sure if it's correct. That itself should be a reason to chose the first code. But the first code is faster as well.

Spoiler
The second code is actually very clever. To define a circle we need the center(which is the variable Origin) and a radius. We end up with circle C(Origin[0], Origin[1], r). Then by varying the radius, we can generate points inside the main circle, so ultimately we are generating points over the surface of the disk.
The only problem is these points will be specified in polar coordinates, we need to convert into cartesian coordinates which is what he is doing here(in order to have them fully defined in polar coordinates we need to pick a random theta angle in [0, 2pi))
PHP Code:
rand_coord[0] = r*floatcos(thetaradian)
rand_coord[1] = r*floatsin(thetaradian
PHP Code:
cos(theta)
sin(theta
This code is guaranteed to work and produce good results so I'd go with it. It is slower because of the usage of sin and cos functions, but if you REALLY need the last bit of speed you can build a table and cache the values of sin & cos for angles theta in [0, 2pi)

The first code appears to be faster in that particular test, but it is non deterministic. Technically, it may never converge to a point inside the circle.
__________________

Last edited by HamletEagle; 10-16-2020 at 03:06.
HamletEagle is offline
Siveroo
Junior Member
Join Date: Apr 2020
Old Today , 03:31   Re: Which method is more efficient?
Reply With Quote #6

Quote:
Originally Posted by HamletEagle View Post
This is generating points inside the rectangle R(x - radius, x + radius, y - radius, y + radius), not in a circle.






The second code is actually very clever. To define a circle we need the center(which is the variable Origin) and a radius. We end up with circle C(Origin[0], Origin[1], r). Then by varying the radius, we can generate points inside the main circle, so ultimately we are generating points over the surface of the disk.
The only problem is these points will be specified in polar coordinates, we need to convert into cartesian coordinates which is what he is doing here(in order to have them fully defined in polar coordinates we need to pick a random theta angle in [0, 2pi))
PHP Code:
rand_coord[0] = r*floatcos(thetaradian)
rand_coord[1] = r*floatsin(thetaradian
PHP Code:
cos(theta)
sin(theta
This code is guaranteed to work and produce good results so I'd go with it. It is slower because of the usage of sin and cos functions, but if you REALLY need the last bit of speed you can build a table and cache the values of sin & cos for angles theta in [0, 2pi)

The first code appears to be faster in that particular test, but it is non deterministic. Technically, it may never converge to a point inside the circle.
yup youre correct, the first code is simpler and easier to undestand, but it's just a bruteforce method, and as a people who likes math a lot, i try not to use it , so i think i'll try to use the second code using some caching method and then see which one is faster.. however, im still going to use the faster one no matter the method.. thanks.

Last edited by Siveroo; Today at 03:46. Reason: there's more thing to say :)
Siveroo is offline
HamletEagle
AMX Mod X Plugin Approver
Join Date: Sep 2013
Location: Romania
Old Today , 04:45   Re: Which method is more efficient?
Reply With Quote #7

With the first method, it is possible the algorithm will never converge or converge after a really long time(i.e all new generated points are inside the R\C area) which will end up being much slower than the second method. At the very least you should limit the max number of iterations to avoid (nearly) infinite loops. That's a very common practice when dealing with such algorithms.

Something like this:
PHP Code:
new maxIters 500
while(condition && maxIters-- > 0)
{
    
//do something

I should also mention that corectness is always more important than performance. No point in a fast yet flawed algorithm.
__________________

Last edited by HamletEagle; Today at 04:52.
HamletEagle is offline
Siveroo
Junior Member
Join Date: Apr 2020
Old Today , 05:29   Re: Which method is more efficient?
Reply With Quote #8

Quote:
Originally Posted by HamletEagle View Post
With the first method, it is possible the algorithm will never converge or converge after a really long time(i.e all new generated points are inside the R\C area) which will end up being much slower than the second method. At the very least you should limit the max number of iterations to avoid (nearly) infinite loops. That's a very common practice when dealing with such algorithms.

Something like this:
PHP Code:
new maxIters 500
while(condition && maxIters-- > 0)
{
    
//do something

I should also mention that corectness is always more important than performance. No point in a fast yet flawed algorithm.
yeah , dont worry im aware of that possibility.. and like i said i dont really like the first code even if the chance of it's not converging is really really stupid low. thanks for the response tho, really appreciate it!

EDIT : the chance of the first code doesnt converge after 10 attempts (in percent)


maybe if i wanna use the first code, im going to limit the iteration like 10 times only, and if it still cant find generate the point inside the circle, just going to replace it with the origin , since the occurence of this event happening are somewhat still "random", although i still hate this method..

Last edited by Siveroo; Today at 05:51.
Siveroo is offline
Old Today, 12:00
HamletEagle
This message has been deleted by HamletEagle.
fysiks
Veteran Member
Join Date: Sep 2007
Location: Flatland, USA
Old Today , 22:37   Re: Which method is more efficient?
Reply With Quote #9

If you're not running on a PC built in the 1970's then using sine and cosine won't add significant performance cost.
__________________

Last edited by fysiks; Today at 22:38.
fysiks 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 23:41.


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