Contest for the fastest weighted Random script

[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: [Select]

$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: [Select]

$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: [Select]

$array[] = 'test for speed of no weight arrays';
$array[] = 'how fast is this';
$array[] = 'the final result for this * 2';Test 2:

Code: [Select]

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

Code: [Select]

$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


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.

[Zeggy]

Is there a prize? XD
Nice competition, I'll give it a try.

btw, for the usage you noted at the bottom, there are other ways of doing this...

[Mgccl]

How about a link to my site as a prize?
tell me other ways you can do it
 

[codestryke]

Sorry I didn't understand your examples on what you wanted but here is a script for ya...

Code: [Select]

  $items[] = array("weight" => 1, "item" => "sword");
  $items[] = array("weight" => 5, "item" => "dagger");
 
  echo get_random_item($items, "weight", "item"); 
 
  function get_random_item($content, $weight, $value) {
 
  // Add all the weights together.
  $total_weight = 0;
  foreach ($content as $entry) {
  $total_weight += $entry[$weight];
  }


  // Generate random selection between 0 and totalweight - 1
  $pick = mt_rand(0, $total_weight - 1);

 
  // Find the content entry that matches the random number.
  $cumulative_weight = 0;
  foreach ($content as $entry) {
  $cumulative_weight += $entry[$weight];
  if ($pick < $cumulative_weight) {
  return $entry[$value];
  }
  }
   
    return false;
   
  }

Function takes 3 paramaters:
1. the array
2. key in the array that corresponds to the weight
3. key in the array that corresponds to the item you want returned

[ewwharhar]

Is there a prize for this?  Even though I don't know a thing about PHP? 

[Zeggy]

Wow, nice contest, it really made me look for some more complicated solutions Especially since you used really large numbers for the weight. It was insanely large compared to the default weight of 1 which I set in my function I dunno if that is the reason why my function is so slow, but it could be.

Anyways, I've made my function, and I ran into a lot of difficulties, mainly speed issues. I tried to reduce the speed problem by adding an extra section that will make sure that all weights are as small a ratio as they can be.
I checked to see if my function would work both locally and hosted on this server but both times it reached the maximum execution time...

Here's my function:

Code: [Select]

<?php
function item($item, $weight = array()) //$weight variable is optional
{
$pad = array_pad(array(), count($item), 1); //Change 1 to whatever you want the default weight to be
$weight = $weight+$pad;
ksort($weight); //Re-order the array

$weight2 = $weight; //Find smallest number of all weights
asort($weight2);

foreach($weight as $key=>$value)
{
$weight[$key] = round($value / $weight2[0]); //Divide all numbers to get smallest ratio with whole numbers
}

$total = 0;
foreach($weight as $w)
{
$total += $w; //Find total weight
}

$values_norm = array();
foreach($weight as $v) {
$values_norm[] = $v / $total; //Ratios...
}

$r = rand(0, 32767) / 32767; //Random number between 0 and 1
$n = 0;

//Check ratios and compare with the same random number
while ($r > $values_norm[$n]) { //Loop through each item
++$n;
}

$result = $item[$n];
return $result;

}
?>
It takes two parameters:
1. One with all the items in it, like in the examples/tests.
2. Array with weights, does NOT need to be the same length as the empty parts of the array will be padded by a default value of 1. Optional parameter

It returns the name of the item that was chosen.


Maybe somebody could improve my function to make it fast enough to use practically

[Mgccl]

well looks good

this is mine...

Code: [Select]

/*
        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];
                }
}
I haven't test who got the fastest script yet.. but I noticed some code can be better in you guy's script

$r = rand(0, 32767) / 32767;
if you want a random number between 0 and 1; use the built in PHP function
try use $r = lcg_value();

codestryke, your code looks fast.. I haven't test it yet... but here is a post I posted in lifelesspeople.com
http://www.lifelesspeople.com/forum/viewtopic.php?t=43799

you can go and test your speed with the other scripts...

I'm going to make a uniformed page about this contest's result. Can I post your guy's script on my site for it?

also, zeggy, fixed your script. now it can work(haven't tried with weight yet)

Code: [Select]

function item($item, $weight = array()) //$weight variable is optional
{
$pad = array_pad(array(), count($item), 1); //Change 1 to whatever you want the default weight to be
$weight = $weight+$pad;
ksort($weight); //Re-order the array

$weight2 = $weight; //Find smallest number of all weights
asort($weight2);

foreach($weight as $key=>$value)
{
$weight[$key] = round($value / $weight2[0]); //Divide all numbers to get smallest ratio with whole numbers
}

$total = 0;
foreach($weight as $w)
{
$total += $w; //Find total weight
}

$values_norm = array();
foreach($weight as $v) {
$values_norm[] = $v / $total; //Ratios...
}

$r = rand(0, 32767) / 32767; //Random number between 0 and 1
$n = 0;

//Check ratios and compare with the same random number
$count = count($values_norm)-1;
while (($n <$count) && ($r > $values_norm[$n]) ) {
++$n;
}
$result = $item[$n];
return $result;
}
Can I post the scripts by your guys on my site on the page full of what other people come up of?

[Zeggy]

Thanks for fixing my code
The while loop was going crazy...

I asked on codingforums.com if anybody could spot the problem with my code. I get over the speed problem now but it doesn't return the correct item

Anyways, here's what somebody else posted:

Code: [Select]

<?php
function weighted_random_element($array, $weights = false)
{
    $elements = count($array);
    if (!$weights)
    {
        return $array[(int) mt_rand(0, $elements - 1)]; 
    }
    if ($elements != count($array))
    {
        # You're on your own here, I don't understand how it's supposed to treat input with only some weights specified
        throw new Exception();
    }
    # Get weights to lowest-to-highest order while maintaining association with $array
    array_multisort($weights, $array);
    # Add up all weights
    $total     = array_sum($weights);
    $placement = mt_rand(0, $total); # This might have to be from 1 to total, I can't figure which introduces a bias

    # Everything from 0-lowest weight goes to that element, lowest weight to second lowest goes to the second lowest weighted element, etc
    for ($i = $sum = 0; $i < $elements; $sum += $weights[++$i])
    {
        if ($placement <= $sum)
        {
            return $array[$i];
        }
    }
    return $array[$elements - 1];
}

$test_ar = array('a', 'b', 'c', 'd');
$weights = array(4, 3, 20, 1);

$results = array();
for ($i = 0; $i < 1000000; ++$i)
{
    ++$results[weighted_random_element($test_ar, $weights)];
}
ksort($results);
print_r($results);
?>

He's basing it off mine, so he left some parts out. You may need to fix it up a bit before it works.

[Mr.Smiley]

I still don't understand how these scripts work.  Call me an idiot, but its just not clicking for me...  If I was to use your script Mgccl, how would I make their be 5 choices, the first choice being weight 1, the second choice being 5 times more likely then that (weight 5), the third choice 10 times more likely then the first one (weight 10), fourth 50 times (weight 50), and the fifth 2 times (weight 2).  Meaning, basically just how do you input multiple choices all with different weights?

[codestryke]

What all these scripts basically do is...

Item A - Least likely (sword of ultimate power or something)
Item B - Dagger of healing 5 times more likely to get then Item A
Item C - Plain Dagger, 50 times more likely to get then Item A

Add all those together 1 + 5 + 50 = 56

Pick a random number if it's 1 get Item 1, if it's 2-5 get Item B, if it's 6-50 get Item C

Mgccl though a curve ball in the requirements by saying you could pass items without weight and still have the function work.

Personally not my approach, instead I tend to go with bell curve algorithm I made.. Given two inputs the variance between the two dictate the outcome. Meaning if they are close to each other they are in the middle of the curve, the farther away they are from each other the more then hit the downslope of the curve. So the norm is more likely to happen then the not norm, if you can understand that LOL.

However, being that I was once into banner advertising, I pulled some of the old code for weighted distribution as my entry If client A pays for his banner to be displayed 250,000 times and client b pays for his to be 50,000 times weight and randomize those to accordingly

[Mgccl]

Personally not my approach, instead I tend to go with bell curve algorithm I made.. Given two inputs the variance between the two dictate the outcome. Meaning if they are close to each other they are in the middle of the curve, the farther away they are from each other the more then hit the downslope of the curve.

Can you show me some code of your approach?
basically I think the
"Item A - Least likely (sword of ultimate power or something)
Item B - Dagger of healing 5 times more likely to get then Item A
Item C - Plain Dagger, 50 times more likely to get then Item A

Add all those together 1 + 5 + 50 = 56"
is pretty fast. and I even released a library
www.phpclasses.org/browse/package/3608.html
just to do that... it even include a BCrand system to create very huge numbers...