View Full Version : Speed issues with weighted randomizer

11-30-2006, 08:56 PM
Hi, I tried to write a weighted randomizing function, but I am having problems with its speed.
When I try to view the file, it seems like the function works fine, but it always reaches the maximum execution time... :(
Which basically rules it out from being used practically...

Here is the function I write, and some tests at the bottom.
If anybody could also point out some improvements, that would be great!
Thanks! :)


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

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

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


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

echo "TEST 1:<br />";
echo item($array);
echo "<br /><hr /><br />";

//Test 2
$array2[] = 'test for weight';
$weight2[] = 30000;
$array2[] = 'with HUGE numbers';
$weight2[] = 2000;
$array2[] = 'final result for this * 5';
$weight2[] = 50000;

echo "TEST 2:<br />";
echo item($array2, $weight2);
echo "<br /><hr /><br />";

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

echo "TEST 3:<br />";
echo item($array3, $weight3);
echo "<br /><hr /><br />";


ralph l mayo
11-30-2006, 09:12 PM
Turn on reporting of notice-level events and you'll see that while loop is running out of control, perhaps that > should be a <?

11-30-2006, 09:23 PM
Oh, right. Thanks! :D
I changed the sign, and it works really fast now.
But the problem now is that lower numbers have more chance of occurring than items that have higher weights.

ralph l mayo
12-01-2006, 12:48 AM
I don't really get what's going on in that function. It's got some fencepost errors you can often see as notices in the first test. I haven't tested this very well but maybe at least the basic methodology will help you.

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)];