...

View Full Version : Speed issues with weighted randomizer



Zegg90
11-30-2006, 07: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! :)


<?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;

}


// 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, 08: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 <?

Zegg90
11-30-2006, 08: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
11-30-2006, 11:48 PM
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)];
}
ksort($results);
print_r($results);



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum