weighted random selections

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
molebrain
Forum Newbie
Posts: 1
Joined: Fri Nov 08, 2002 9:23 am
Location: pittsburgh

weighted random selections

Post by molebrain »

Does anyone know how to do weighted random selections with PHP? I have a user table and each user has a different amount of points. They also have a url table linked to their userid. I want to randomly pick a url from the list according to which user has more points....a weighted random selection. Any ideas? I am simply doing a select .... order by rand() limit 1

tanks


__________________
8O
User avatar
BDKR
DevNet Resident
Posts: 1207
Joined: Sat Jun 08, 2002 1:24 pm
Location: Florida
Contact:

Post by BDKR »

Sounds like some cool stuff. I wish I could say I had an answer for you. I created (and am still not finished) a load balancer using PHP, but it's distributing traffic using a simple round robin approach. I'd like to use another distribution algorithm. If you find anything, let us know.

Cheers,
BDKR
User avatar
mr_griff
Forum Commoner
Posts: 64
Joined: Tue Sep 17, 2002 11:11 am
Location: Bozeman, Montana

Post by mr_griff »

I found this chunk of cold fusion code that shouldn't be too hard to convert. Most of the weighted random stuff I have seen is based on a timestamp (like display ads at random and try to give them equal display time), but this one should be similar to your situation.

Code: Select all

1    <!--- The Weightings --->
   2 <cfset ListItems = "One,Two,Three,Four,Five,Six">
   3 <cfset ListWeightings = "1,3,5,11,30,50">
   4    <!--- Get the number of Items in the List --->
   5 <cfset OptionsNumber = ListLen(ListWeightings)>
   6    <!--- Add up the List --->
   7 <cfset OptionsTotal = Evaluate(Replace(ListWeightings, ",", "+", "ALL"))>
   8    <!--- Set random number based on OptionsTotal --->
   9 <cfset RandNum = RandRange(1, OptionsTotal)>
  10    <!--- Default the ElectedOption to Zero --->
  11 <cfset ElectedOption = 0>
  12    <!--- Loop over list to get Option --->
  13 <cfloop list="#ListWeightings#" index="Option">
  14    <cfset ElectedOption = ElectedOption + 1>
  15    <cfif Option GTE RandNum>
  16       <cfbreak>
  17    <cfelse>
  18       <cfset RandNum = RandNum - Option>
  19    </cfif>
  20 </cfloop>
User avatar
BDKR
DevNet Resident
Posts: 1207
Joined: Sat Jun 08, 2002 1:24 pm
Location: Florida
Contact:

Post by BDKR »

Wow! CF is some ugly stuff. Looks like an HTML first timers nightmare.

BUT, I'm going to try do decipher it. Might be fun. :twisted:

Cheers,
BDKR
User avatar
BDKR
DevNet Resident
Posts: 1207
Joined: Sat Jun 08, 2002 1:24 pm
Location: Florida
Contact:

Post by BDKR »

Hey mr_griff,

I took that hunk of code you posted and created what you see below.

Code: Select all

&lt;?php

# The noise below is, I was told, a wieghted round robin algorithm. Looks rather ugly, 
# but perhaps there is truth in what was said. 

/*
&lt;!--- The Weightings ---&gt;
&lt;cfset ListItems = "One,Two,Three,Four,Five,Six"&gt;
&lt;cfset ListWeightings = "1,3,5,11,30,50"&gt;

&lt;!--- Get the number of Items in the List ---&gt;
&lt;cfset OptionsNumber = ListLen(ListWeightings)&gt;

&lt;!--- Add up the List ---&gt;
&lt;cfset OptionsTotal = Evaluate(Replace(ListWeightings, ",", "+", "ALL"))&gt;

&lt;!--- Set random number based on OptionsTotal ---&gt;
&lt;cfset RandNum = RandRange(1, OptionsTotal)&gt;

&lt;!--- Default the ElectedOption to Zero ---&gt;
&lt;cfset ElectedOption = 0&gt;

&lt;!--- Loop over list to get Option ---&gt;
&lt;cfloop list="#ListWeightings#" index="Option"&gt;
	&lt;cfset ElectedOption = ElectedOption + 1&gt;
  &lt;cfif Option GTE RandNum&gt;
		 cfbreak&gt;
  &lt;cfelse&gt;
		&lt;cfset RandNum = RandNum - Option&gt;
  &lt;/cfif&gt;
&lt;/cfloop&gt;
*/


# The weightings
$ListItems = "One,Two,Three,Four,Five,Six";
$ListWeightings = "1,3,5,11,30,50";

# Get number of Items in list
$OptionsNumber = sizeof(explode(",", $ListWeightings));

# Add up the list
$OptionsTotal = array_sum(explode(",", $ListWeightings));

# Set random number based on OptionsTotal
mt_srand(make_seed());
$RandNum=mt_rand(1, $OptionsTotal);

# Set the default var for ElectedOption to 0
$ElectedOption = 0;

# Let's just create a $ListWeightings array. We could iterate over a string as 
# CF does, but it's not worth the hassle
$arrListWeightings=explode(",", $ListWeightings);

# Now loop over the list to the the Option
while(list(, $val)=each($arrListWeightings))
	{ 
	++$ElectedOption; 
	if($val&gt;=$RandNum)
		{ break; }
	else
		{ $RandNum=($RandNum-$val); }
	}

echo "$RandNum\n";
exit;



##################################################################
# Functions
##################################################################

# seed with microseconds
function make_seed() 
    {
    list($usec, $sec) = explode(' ', microtime());
    return (float) $sec + ((float) $usec * 100000);
    }

?&gt;
Now I'm stil a little lost on how it works to provide a weighted round robin kind of, err...,
anything. Also, the PHP version could easily be made more effecient by dropping the strings
and using arrays.

Some things are definitely interesting though. How CF provides a built in way to iterate over llists that are really strings is interesting, but it has got to slow the language down a bit. Also how the evaluate() function works was strange too.

It's a neat language in a sense, if not a little ugly. I like the comparison operators.

Code: Select all

PHP                 CF
------               ------
&gt;=                   GTE
==                    IS
&lt;=                   LTE
&gt;                     GT
&lt;                     LT
There are more I'm sure, but it's kinda cool, and perhaps a little more intuitive when looked at as acronyms.

Anyways, have more of the code so I can get more of an idea on how this is to be "plugged in"? There are a number of vars that are worked with at the beginning of the code that don't seem to contribute in any way to the final result.

Cheers,
BDKR
Post Reply