Which method is more efficient?

Siveroo · **Author**

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

Natsheh · *Last edited by Natsheh; 10-13-2020 at 15:02.*

PHP Code:


			
random_coord_within_region(Float:x, Float:y, radius=5.0, Float:random_coord[2])
{
   random_coord[0] = random_float(-radius, radius) + x;
   random_coord[1] = random_float(-radius, radius) + y;
}

shouldn't be so complicated.

Siveroo · 10-14-2020 , 00:50 Re: Which method is more efficient?

Quote:

Originally Posted by Natsheh

PHP Code:


			
random_coord_within_region(Float:x, Float:y, radius=5.0, Float:random_coord[2])

{

   random_coord[0] = random_float(-radius, radius) + x;

   random_coord[1] = random_float(-radius, radius) + y;

}

shouldn't be so complicated.

but i think that will result in a rectangular region instead of a circle

Black Rose · *Last edited by Black Rose; 10-15-2020 at 14:58.*

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

Code:

#include <amxmodx>

/*
Measures the actual time (even if the server is frozen due to working) for up to almost 25d.
new hTimer = TimerStart();
// ...
TimerStop(hTimer);
*/
#define TimerStart()            tickcount()
#define TimerMid(%0)            ( tickcount() - %0 )
#define TimerStop(%0)         ( %0 = tickcount() - %0 )

#define TimerDays(%0)         ( %0 / 86400000 )
#define TimerHours(%0)      ( %0 % 86400000 / 3600000 )
#define TimerMinutes(%0)        ( %0 % 3600000 / 60000 )
#define TimerSeconds(%0)        ( %0 % 60000 / 1000 )
#define TimerMilliseconds(%0)   ( %0 % 1000 )

/* TimerFormat(hTimer, output[], maxlen, mode = 1, bool:full = 0)
* Formats the result of a timer handle into a string.
*
* Parameters:
*
* hTimer
*    Timer Handle
*
* output[]
*    The output string
*
* maxlen
*    Maximum size of the output string
*
* mode
*    1: 00:00:00:00.000
*    2: 0d 0h 0m 0s 0ms
*
* bool:full
*    If full is set to true it will print all fields, even those which contains no value.
*    If full is set to false and mode is set to 1, it will print the first field that contains a value and everything after that point. For example: 03:00:00.295
*    If full is set to false and mode is set to 2, it will print only the fields that contains a value. For example: 3h 295ms
*/
stock TimerFormat(hTimer, output[], maxlen, mode = 1, bool:full = false) {
    new len;
    
    if ( full || TimerDays(hTimer) )
        len = formatex(output, maxlen, mode == 1 ? "%02d:" : "%dd ", TimerDays(hTimer));

    if ( full || ( len && mode == 1 ) || TimerHours(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%02d:" : "%dh ", TimerHours(hTimer));

    if ( full || ( len && mode == 1 ) || TimerMinutes(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%02d:" : "%dm ", TimerMinutes(hTimer));
        
    if ( full || ( len && mode == 1 ) || TimerSeconds(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%02d." : "%ds ", TimerSeconds(hTimer));

    if ( full || ! len || mode == 1 || TimerMilliseconds(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%03d" : "%dms", TimerMilliseconds(hTimer));
}



public plugin_init() {
    register_plugin("Test Plugin 2", "1.0", "[ --{-@ ]");

    new cyc = 1000000

    test(5, cyc, 1);
    test(50, cyc, 1);
    test(500, cyc, 1);
    test(5000, cyc, 1);

    test(5, cyc, 2);
    test(50, cyc, 2);
    test(500, cyc, 2);
    test(5000, cyc, 2);

}

test(range, cycles, method) {

    new test[2];
    new hTimer;

    if ( method == 1 ) {
        hTimer = TimerStart();
        for ( new i ; i < cycles ; i++ ) {
            random_coord1(test, range);
        }
        TimerStop(hTimer);
    }

    else {
        hTimer = TimerStart();
        for ( new i ; i < cycles ; i++ ) {
            random_coord2(test, range);
        }
        TimerStop(hTimer);
    }

    new output[32];
    TimerFormat(hTimer, output, charsmax(output), 2);
    server_print("Testing %dM cycles of method %d. Time: %s", cycles/1000000, method, output)
}

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 )
}

stock random_coord2(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 = range * 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)   

    Origin[0] += rand_coord[0];
    Origin[1] += rand_coord[1];
}

Code:

Testing 1M cycles of method 1. Time: 375ms
Testing 1M cycles of method 1. Time: 406ms
Testing 1M cycles of method 1. Time: 405ms
Testing 1M cycles of method 1. Time: 403ms
Testing 1M cycles of method 2. Time: 765ms
Testing 1M cycles of method 2. Time: 765ms
Testing 1M cycles of method 2. Time: 762ms
Testing 1M cycles of method 2. Time: 784ms

**HamletEagle** · *Last edited by HamletEagle; 10-16-2020 at 03:06.*

Quote:

Originally Posted by Natsheh

PHP Code:


			
random_coord_within_region(Float:x, Float:y, radius=5.0, Float:random_coord[2])
{
   random_coord[0] = random_float(-radius, radius) + x;
   random_coord[1] = random_float(-radius, radius) + 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

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

Code:

#include <amxmodx>

/*
Measures the actual time (even if the server is frozen due to working) for up to almost 25d.
new hTimer = TimerStart();
// ...
TimerStop(hTimer);
*/
#define TimerStart()            tickcount()
#define TimerMid(%0)            ( tickcount() - %0 )
#define TimerStop(%0)         ( %0 = tickcount() - %0 )

#define TimerDays(%0)         ( %0 / 86400000 )
#define TimerHours(%0)      ( %0 % 86400000 / 3600000 )
#define TimerMinutes(%0)        ( %0 % 3600000 / 60000 )
#define TimerSeconds(%0)        ( %0 % 60000 / 1000 )
#define TimerMilliseconds(%0)   ( %0 % 1000 )

/* TimerFormat(hTimer, output[], maxlen, mode = 1, bool:full = 0)
* Formats the result of a timer handle into a string.
*
* Parameters:
*
* hTimer
*    Timer Handle
*
* output[]
*    The output string
*
* maxlen
*    Maximum size of the output string
*
* mode
*    1: 00:00:00:00.000
*    2: 0d 0h 0m 0s 0ms
*
* bool:full
*    If full is set to true it will print all fields, even those which contains no value.
*    If full is set to false and mode is set to 1, it will print the first field that contains a value and everything after that point. For example: 03:00:00.295
*    If full is set to false and mode is set to 2, it will print only the fields that contains a value. For example: 3h 295ms
*/
stock TimerFormat(hTimer, output[], maxlen, mode = 1, bool:full = false) {
    new len;
    
    if ( full || TimerDays(hTimer) )
        len = formatex(output, maxlen, mode == 1 ? "%02d:" : "%dd ", TimerDays(hTimer));

    if ( full || ( len && mode == 1 ) || TimerHours(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%02d:" : "%dh ", TimerHours(hTimer));

    if ( full || ( len && mode == 1 ) || TimerMinutes(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%02d:" : "%dm ", TimerMinutes(hTimer));
        
    if ( full || ( len && mode == 1 ) || TimerSeconds(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%02d." : "%ds ", TimerSeconds(hTimer));

    if ( full || ! len || mode == 1 || TimerMilliseconds(hTimer) )
        len += formatex(output[len], maxlen - len, mode == 1 ? "%03d" : "%dms", TimerMilliseconds(hTimer));
}



public plugin_init() {
    register_plugin("Test Plugin 2", "1.0", "[ --{-@ ]");

    new cyc = 1000000

    test(5, cyc, 1);
    test(50, cyc, 1);
    test(500, cyc, 1);
    test(5000, cyc, 1);

    test(5, cyc, 2);
    test(50, cyc, 2);
    test(500, cyc, 2);
    test(5000, cyc, 2);

}

test(range, cycles, method) {

    new test[2];
    new hTimer;

    if ( method == 1 ) {
        hTimer = TimerStart();
        for ( new i ; i < cycles ; i++ ) {
            random_coord1(test, range);
        }
        TimerStop(hTimer);
    }

    else {
        hTimer = TimerStart();
        for ( new i ; i < cycles ; i++ ) {
            random_coord2(test, range);
        }
        TimerStop(hTimer);
    }

    new output[32];
    TimerFormat(hTimer, output, charsmax(output), 2);
    server_print("Testing %dM cycles of method %d. Time: %s", cycles/1000000, method, output)
}

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 )
}

stock random_coord2(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 = range * 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)   

    Origin[0] += rand_coord[0];
    Origin[1] += rand_coord[1];
}

Code:

Testing 1M cycles of method 1. Time: 375ms
Testing 1M cycles of method 1. Time: 406ms
Testing 1M cycles of method 1. Time: 405ms
Testing 1M cycles of method 1. Time: 403ms
Testing 1M cycles of method 2. Time: 765ms
Testing 1M cycles of method 2. Time: 765ms
Testing 1M cycles of method 2. Time: 762ms
Testing 1M cycles of method 2. Time: 784ms

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(theta, radian)
rand_coord[1] = r*floatsin(theta, radian)

PHP Code:


			
x = r * cos(theta)
y = r * 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.

Siveroo · 10-19-2020 , 03:31 Re: Which method is more efficient?

Quote:

Originally Posted by HamletEagle

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(theta, radian)

rand_coord[1] = r*floatsin(theta, radian)

PHP Code:


			
x = r * cos(theta)

y = r * 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.

**HamletEagle** · *Last edited by HamletEagle; 10-19-2020 at 04:52.*

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.

Siveroo · *Last edited by Siveroo; 10-19-2020 at 05:51.*

Quote:

Originally Posted by HamletEagle

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

fysiks · *Last edited by fysiks; 10-19-2020 at 22:38.*

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

meTaLiCroSS · 10-20-2020 , 23:07 Re: Which method is more efficient?

Quote:

Originally Posted by HamletEagle

It is slower because of the usage of sin and cos functions

We're in 2020, as a reminder