|
|
|
| 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 : |
7445 |
| 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 | | | grab the result of any calculation you submit to the Google Calculator.
Categories : PHP, Arrays, Web Services, Regexps, Math. | | | create a grid out of <INPUT TYPE=TEXT> then saving to a database. Uses
a 'multi-dimension array', but not really as the array is just one big array
with the index of "[$i][$j]". Have a look at the code and you'll see what I
mean.
Categories : PHP, MySQL, Arrays, Databases | | | Link Submition - Allow your visitors to submit links to the site.
Categories : PHP, Arrays, Filesystem, Beginner Guides | | | Simple conversion functions to change MySQL dates to arrays, arrays to MySQL dates.
Categories : PHP, Arrays, Date Time, Databases, MySQL | | | CSS style switcher
Categories : PHP, CSS, HTML and PHP, Arrays, Sessions | | | dynamic table columns
Categories : PHP, HTML and PHP, Arrays, Databases, MySQL | | | Library of math functions to expand the functionality of PHP3. Version 1.2.1 fixes a major problem with the gcd function.
Categories : Algorithms, PHP, Math. | | | Dynamic Loading of XML array data into ComboBox and Display XML data using PHP + DOM + Javascript.
Categories : PHP, Java Script, DOM XML, XML, Arrays | | | BBCode Formatting String
Categories : PHP, HTML, Regexps, Arrays | | | Array Insertion
Categories : PHP, PHP Classes, Arrays | | | PHPDRAW, the php wannabe Photoshop ;-)
Categories : PHP, PHP Classes, GD image library, Arrays | | | How to pass an array from one PHP Script to another via an HTML form
Categories : PHP, HTML and PHP, Arrays | | | How to load a query result into a PHP Array
Categories : PHP, Databases, Arrays, MySQL | | | array -- Create an array
Categories : PHP, PHP Functions, Arrays | |
|
|
