|
|
|
| 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 2 times) |
| Viewed : |
3439 |
| 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;
}
}
?> | |
|
|
| Convert number to words
Categories : PHP, Math., Arrays | | | Math operations on big numbers
Categories : PHP, Math. | | | Latitude-Longitude to Miles
Categories : PHP, Utilities, Math. | | | Array values from javascript to php
Categories : PHP, Java Script, Arrays | | | clearing variables in php3
Categories : Variables, Arrays, PHP | | | PHP Random rss feeds - selects 49 random feeds from an unlimited list and displays them on your website. It's Ideal for those moments when you got 5 minutes and dont know which one of your feeds to read.
Categories : PHP, Rich Site Summary (RSS), Arrays | | | Display list of files within current and subdirectories (recursively) showing
each file as an anchored link and each directory as a category header.
Categories : Filesystem, Directories, Arrays, PHP | | | Dump the contents of a PHP variable in html format with a recursive list of subfolders and files from a given root directory.
Categories : PHP, Directories, Variables, Arrays | | | BBCode Formatting String
Categories : PHP, HTML, Regexps, Arrays | | | Array Insertion
Categories : PHP, PHP Classes, Arrays | | | PHP Script to find url links in a page
Categories : PHP, URLs, Regexps, Arrays | | | Tag content retrieval from websites with preg_match
Categories : PHP, Regexps, Arrays, HTML and PHP | | | Check for functional file links (broken Files)
Categories : PHP, Data Validation, FTP, Regexps, Arrays | | | This gets the http response headers for a given url and returns them in an assoc array. i.e. to test if a url exists: $array = get_http_headers($url); if($array[result]=200) { }
Categories : HTTP, Arrays, PHP | | | Beginners Array Functions
Categories : PHP, Beginner Guides, Arrays | |
|
|
|
