|
|
|
| Title : |
Weighted Random - Random Scripts usually chose one out of each item, and each item have an equal chance to be chosen. But what if you want an item to be chosed more frequently than other? |
| Categories : |
PHP, Math., Arrays |
Chao Xu |
| Date : |
Dec 03rd 2006 |
| Grade : |
1 of 5 (graded 4 times) |
| Viewed : |
7637 |
| File : |
No file for this code example. |
| Images : |
No Images for this code example. |
|
| Search : |
More code by Chao Xu |
|
| Action : |
Grade This Code Example
|
|
| Tools : |
My Examples List |
|
|
|
|
|
|
|
Like this code?
Show the author your appreciation.
|
|
| |
I started to find ways to build a weighted random system and improved it to make it the fastest around. My first version:
|
<?php
function rand_string_pro($array){
foreach($array as $var){
$i = 0;
while($i < $var['w']){
$string[] = $var['s'];
$i++;
}
}
return $string[array_rand($string)];
}
?> | |
The input is an array like this(where $i can be any interger)
| <?php
$array[$i]['s'] = 'string';
$array[$i]['w'] = 30;//only interger
?> | |
I thought that code is perfect, until weeks ago I saw the flaws and
start writing improvements. The list of flaws:
o Huge weights can slow the script down, even produce memory overflow.
o Huge strings with reasonable amount of weight can produce memory overflow too.
o It does not seems FAST...
This list does not include error handling, because I don't think I
need to program something to notice kind exprinced programmers.
Yes Yes, I know it is a bad act.
I did some improvement and released my 1.0 verion
| <?php
/*
Weighted Random Ver 1.0 by Mgccl(mgcclx@gmail.com)
Useage: input an numbered array
$array[$i][’s’] is the string you want to return
$array[$i][’w'] is the weight of the string
you can allow the function to find the GCD
sometimes it speeds up the script
To use GCD, use the function like
rand_string_pro($array, true);
Note: You need the math functions I wrote in
order to use GCD, you can find them further on this page.
and on http://www.webdevlogs.com/2006/11/21/some-math-functions/
*/
function rand_string_pro($seed, $gcd = false){
$count = count($seed);
if($gcd == true){
foreach($seed as $var){
$gcd_array[] = $var[‘w’];
}
$gcd = math_gcd_array($gcd_array);
if($gcd != 1){
$i = 0;
while($i < $count){
$seed[$i][‘w’] /= $gcd;
++$i;
}
}
unset($gcd, $gcd_array);
}
$i = 0;
while($i < $count){
$n = 0;
while($n < $seed[$i][‘w’]){
$key[] = $i;
++$n;
}
++$i;
}
return $seed[$key[mt_rand(0, count($key)-1)]][’s’];
}
?> | |
The new version has these improvements:
o Weight divided by the GCD so we have smaller weights.
o Produce a new array to store the key, and the key refer to the "key name" of the variable seed. No more huge array in the size of value
o Used ++$i instead of $i++, small speed up
But there is still a flaw in the system. It still creates a huge
array if the GCD is small compare to the weight. The proformance
could still be slow.
I released the version 1.1, more like a useablity improvement version
| <?php
/*
Weighted Random Ver 1.1 by Mgccl(mgcclx@gmail.com)
Update: Nov/25/06 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)
o $array[$i] is the string you want to return
o $weight[$i] is the weight of the string if one of the $array[$i] does not have a
o $weight[$i] as a match, it automatically set $weight[$i] as 1
To use the weighted function, call the function like this :
rand_string_pro($array, $weight);
you can allow the function to find the GCD sometimes it speeds up
the script. To use GCD, use the function like this :
rand_string_pro($array, $weight, true);
Note: You need the math functions I wrote in
order to use GCD, you can find them further down this page or
at : http://www.webdevlogs.com/2006/11/21/some-math-functions/
*/
function rand_string_pro($seed, $weighted = false, $gcd = false){
$count = count($seed);
if($weighted === false){
return $seed[mt_rand(0, $count - 1)];
}else{
if($gcd === true){
if(count($weighted) != $count){
}else{
foreach($weighted as $var){
$gcd_array[] = $var;
}
$gcd = math_gcd_array($gcd_array);
if($gcd != 1){
$i = 0;
while($i < count($gcd_array)){
$weighted[$i] /= $gcd;
++$i;
}
}
unset($gcd, $gcd_array);
}
}
$i = 0;
while($i < $count){
if(empty($weighted[$i])){
$key[] = $i;
}else{
$n = 0;
while($n < $weighted[$i]){
$key[] = $i;
++$n;
}
}
++$i;
}
return $seed[$key[mt_rand(0, count($key)-1)]];
}
}
?> | |
this version seprated the input of the string array and the weight array
it also made the function useable when there is no weight present.
And finally, Version 1.2 is where I made the speed to the max.
| <?
/*
Weighted Random Ver 1.2 by Mgccl(mgcclx@gmail.com)
http://www.webdevlogs.com
Update: Nov/29/06
o Faster Speed
o 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)
o $array[$i] is the string you want to return
o $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 use the 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];
}
}
?> | |
This code is way more faster than the old version because:
1. The loop will break at the selected string
2. It use one numeric variable instead of a huge array
The useage of those functions are already written in the comments.
Basically, this one will be the fastest code possible. :)
There are more improvements, like what if a user want to chose 10000
random items? run the function 10000 times? Well it's late now(12:38AM),
you guys have to think yourself
Related Functions
| <?php
//greatest common denominator of 2 numbers
// thx to xJeff at lifelesspeople.com
function gcd($a, $b) {
if ($b == 0) return $a;
else return gcd($b, $a % $b);
}
//greatest common denominator of an array
//thx to pterodactyl at lifelesspeople.com
//for the use of array_splice(smart)
function math_gcd_array($array){
while (count($array) > 1) {
array_splice($array, 0, 2, gcd($array[0], $array[1]));
}
return $array[0];
}
//Least Common Multiple
//Thx to Wikipedia
//http://en.wikipedia.org/wiki/Least_common_multiple
function math_lcm_array($array){//The
$product = 1;
foreach($array as $num){
$product *= $num;
}
return ($product/math_gcd_array($array));
}
//Get log with a base other than e or 10
//thx to my school
//I still have to know is log() or log10() faster
function math_log_base($base, $number){
return log10($number)/log10($base);
}
//better rounding function, by laserlight
//original post http://phpbuilder.com/board/showthread.php?t=10325643
function func_round($value, $precision = 0, $func = ’round’) {
if ($func == ’round’) {
return round($value, $precision);
} elseif ($func == ‘floor’ || $func == ‘ceil’) {
$multiplier = pow(10, $precision);
return $func($value * $multiplier) / $multiplier;
} else {
return $value;
}
}
?> | |
|
|
| grab the result of any calculation you submit to the Google Calculator.
Categories : PHP, Arrays, Web Services, Regexps, Math. | | | Convert number to words
Categories : PHP, Math., Arrays | | | Variable serialization and unserialization. Loading and saving variable structures
to and from file.
Categories : Arrays, Filesystem, Variables, Strings, PHP | | | Latitude-Longitude to Miles
Categories : PHP, Utilities, Math. | | | Math operations on big numbers
Categories : PHP, Math. | | | Simple way of scaling any image to fit either given width or height.
Categories : PHP, Graphics, Arrays | | | Tag content retrieval from websites with preg_match
Categories : PHP, Regexps, Arrays, HTML and PHP | | | WWW interface to Unix Manual(phpMan)
Categories : Program Execution, Strings, Arrays, PHP | | | Tweak Array, insert/add elements to any position of your arrays - delete elements from your arrays - move elements within your arrays - replace elements from your arrays ... the array, 'dynamically' grows or shrinks to whatever we tweak it.
Categories : PHP Classes, Arrays, PHP | | | A recursive function to traverse a multi-dimensional array where the
dimensions are not known
Categories : Arrays, PHP, Algorithms | | | Print out array key => value in colored HTML
Categories : PHP, Arrays, HTML and PHP | | | Array values from javascript to php
Categories : PHP, Java Script, Arrays | | | Get TemplateMonster data
Categories : Arrays, Ecommerce, PHP, Strings | | | Looping through two arrays
Categories : PHP, Databases, Arrays | | | Form Submission Using Array's
Categories : PHP, HTML and PHP, Beginner Guides, Arrays | |
|
|
