FRIHOST • FORUMS • FAQ • TOS • BLOGS • DIRECTORY
You are invited to Log in or Register a Frihost Account!

Contest for the fastest weighted Random script, all my $f

   Frihost Forum Index -> Miscellaneous -> Contests
 


Mgccl
Requirement:
1. Only PHP is allowed
2. It can be either a function or a class
3. the input array of string is a numbered array, each one stores a string. It's created by using:
Code:
$array[] = 'string';

4. The input array of weight is also a numbered array, for a $weight[$i], it resemble the weight value of $array[$i]. $weight contain only positive integers. $weight[$i] does not need to be created, if there is no $weight[$i] match $array[$i], the weight 1 will be used
5. Return one of the string of the $array dependent on the $weight
Note: in case you don't know what is weighted random. two or more items, each have a weight, weight decide the chance it get chosen. A item with weight 5 have 5 times more chance to be chosen than a item with weight 1, 2.5 times more chance than a item with weight 2. let me give you an example of what it is like:
Code:
$array[] = 'weight 1';
$array[] = 'weight 2, have higher chance to be chosen than weight 1';
$array[] = $array[1];
echo $array[array_rand($array)];


Final Test for speed:
There will be three test it have to go though, here are the inputs for each:
Test 1:
Code:
$array[] = 'test for speed of no weight arrays';
$array[] = 'how fast is this';
$array[] = 'the final result for this * 2';

Test 2:
Code:
$array[] = 'test for weight';
$weight[] = 30000;
$array[] = 'with HUGE numbers';
$weight[] = 2000;
$array[] = 'final result for this * 5';
$weight[] = 50000;

Test 3:
Code:
$array[]= 'test for weight array only on some';
$weight[] = 20000;
$array[]= 'final result for this * 3';



Winner is the person who have the smallest number after the weighted number of all tests, which is
Final result for test 1 *2 + Final result for test 2 * 5 + final result for test 3 * 3

The Winner will get all my $F

Note: When would people need weighted random?
Most likely in games. Kill a monster, what will be dropped? Diamond weight 1 and wooden sword weight 1000000, then most likely you get the wooden sword.
Daniel15
I was bored, so I worked on this for you Razz I commented the main function which does all the work. I also included some testing code, and some code for measuring how long it took to load (this code isn't commented, though)

Please see my code at http://www.daniel15.com/stuff/php/weighted_random_src.php (I would post it here in a code tag, but I prefer PHP's highlight_file() function Very Happy), and an example at http://www.daniel15.com/stuff/php/weighted_random.php
Mgccl
ok... I will try to test the speed of it soon.. so I post mine version...
there are other people posted theirs own other forums... so I think I will make a page to introduce all of the scripts Smile

Code:
/*
        Weighted Random Ver 1.2 by Mgccl(mgcclx@gmail.com)
        http://www.webdevlogs.com
        Update: Nov/29/06
        Faster Speed
        allow non-weighted random, seprate the
        string storing array and the weight storing array
        Useage: input $array[$i] = 'string' format(where $i is a number)
        $array[$i]is the string you want to return
        $weight[$i]is the weight of the string
        if one of the $array[$i] does not have a
        $weight[$i] as a match, it automatically
        set $weight[$i] as 1
        To allow use weighted function, call the function like this
        rand_string_pro($array, $weight);
        */

function rand_string_pro($seed, $weighted = false){
        $count = count($seed);
        if($weighted === false){
                return $seed[mt_rand(0, $count - 1)];
        }else{
                $i = 0; $n = 0;
                $num = mt_rand(0, array_sum($weighted) + ($count-count($weighted)));
                while($i < $count){
                        if(empty($weighted[$i])){
                                ++$n;
                        }else{
                        $n += $weighted[$i];
                    }
                    if($n >= $num){
                        break;
                    }
                    ++$i;
                }
                return $seed[$i];
                }
}
Daniel15
Hmmm... How does your one work? Confused Please explain your algorithm and implementation...

EDIT: Please feel free to use my code for checking how fast the algorithms are. Just remove my function, and replace it with your one.
Mgccl
well... it works like this...
you want to chose a random string? ok. Now that's how it works:

Because each item have a weight, so the sum of all weight will be 100%.
so... generate a number between 0 and the weight.
And now start looping..
so it loops though array, and add a number(weight of the current item) to the $n. and when $n >= the random number, it breaks the loop...
in the loop, it also counts $i, and $i is the key to the random string array....

I don't have time to test your code now because it's kind late(11:21PM).. I will tomorrow...

Can I use your code on my next article on my site that is going to features all the code in the contest??

Here is the result on my computer for each test, score is calculated by test1*2 + test2*5 + test3*3

starting tests (each test done 10000 times)
Quote:
test1: 0.238054037094 s
test2: 0.225346565246 s
test3: 0.227444648742 s

score: 2.28517484665


And here is the result for my version of the code
Quote:
starting tests (each test done 10000 times)
test1: 0.143338680267 s
test2: 0.139352798462 s
test3: 0.1370408535 s

score: 1.39456391335
Reply to topic    Frihost Forum Index -> Miscellaneous -> Contests

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2007 Frihost, forums powered by phpBB.