Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 4 of 4
  1. #1
    New Coder
    Join Date
    Jan 2006
    Posts
    53
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Speed issues with weighted randomizer

    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 Code:
    <?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(032767) / 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 />";

    ?>

  • #2
    Regular Coder ralph l mayo's Avatar
    Join Date
    Nov 2005
    Posts
    951
    Thanks
    1
    Thanked 31 Times in 29 Posts
    Turn on reporting of notice-level events and you'll see that while loop is running out of control, perhaps that > should be a <?

  • #3
    New Coder
    Join Date
    Jan 2006
    Posts
    53
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Oh, right. Thanks!
    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.

  • #4
    Regular Coder ralph l mayo's Avatar
    Join Date
    Nov 2005
    Posts
    951
    Thanks
    1
    Thanked 31 Times in 29 Posts
    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.

    PHP Code:
    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(43201);

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


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •