|
|
|
| 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 : |
10998 |
| 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 | | | PHP Script to find url links in a page
Categories : PHP, URLs, Regexps, Arrays | | | Beginners Array Functions
Categories : PHP, Beginner Guides, Arrays | | | columned txt file to array()?
Categories : Arrays, Strings, Regexps, PHP | | | How to judge if an integer is odd or is even in Php3?
Categories : Math., PHP, Algorithms | | | Arbitrary Precision Math using BCMATH routines
Categories : PHP, Math., BC math | | | translate.php - Assocciative array example, passing a reference to a function.
Categories : PHP, Arrays, Languages, Variables | | | Link Submition - Allow your visitors to submit links to the site.
Categories : PHP, Arrays, Filesystem, Beginner Guides | | | Function to create a separated list
Categories : PHP, Arrays, Strings | | | HTML_Graphs uses PHP to provide a consistent interface for creating HTML based charts. The user of the class sets up arrays that are passed to html_graph() which then takes care of all the messy HTML layout.
Categories : Graphics, Arrays, PHP, PHP Classes, Charts and Graphs | | | Tag content retrieval from websites with preg_match
Categories : PHP, Regexps, Arrays, HTML and PHP | | | Greatest Common Denominator - A simple class that finds the greatest common denominator for two integers.
Categories : PHP, PHP Classes, Math. | | | quick sort for associative arrays
Categories : Algorithms, Arrays, PHP | | | Stepping through a numbered array with each() and list()
Categories : PHP, Arrays | |
| |
| |
|
