Re: Re: #18401 [Opn->Ana]: shuffle() broken (fwd)
| From: | Adam Maccabee Trachtenberg | Date: | Sat, 17 Aug 2002 03:18:51 +0000 |
| Subject: | Re: Re: #18401 [Opn->Ana]: shuffle() broken (fwd) | ||
| References: | 1 | Groups: | php.dev |
| Request: | Send a blank email to php-dev+get-86924@lists.php.net to get a copy of this message | ||
On Fri, 16 Aug 2002, Tim Converse wrote:
> --- Yasuo Ohgaki <yohgaki@ohgaki.net> wrote:
> If you don't believe me, take your algorithm and run it
> many times, tracking how often element i in the input moves
> to become element j in the output, and print the resulting
> counts out as an n-by-n table. You'll see a bias towards
> elements moving one position back in the array.
Yasuo --
Look at the following code. The php_shuffle() function is the
algorithm currently in the CVS; yasuo_shuffle() is what you're
proposing.
The test() function is a simple script to call each *_shuffle()
function 100,000 times on a three-element array, record the
permutations, and print out a record of the results. You'll see that
php_shuffle() evenly divides the elements, while yours does not:
<?php
function php_shuffle(&$array) {
$i = count($array);
while (--$i) {
$j = mt_rand(0, $i);
if ($i != $j) {
/* swap elements */
$tmp = $array[$j];
$array[$j] = $array[$i];
$array[$i] = $tmp;
}
}
}
function yasuo_shuffle(&$array) {
$s = count($array);
for ($i=0; $i < $s; $i++) {
$j = mt_rand(0, $s - 1);
if ($i != $j) {
/* swap elements */
$tmp = $array[$j];
$array[$j] = $array[$i];
$array[$i] = $tmp;
}
}
}
function test($function) {
$a = array();
$times = 100000;
for ($i = 0; $i < $times; $i++) {
$p = range(1,3);
$function($p);
$s = join('', $p);
$a[$s]++;
}
print "$function\n";
ksort($a);
foreach($a as $k => $v) {
print "$k: $v: " . sprintf('%0.3f', $v / $times) . "%\n";
}
}
test('php_shuffle');
test('yasuo_shuffle');
?>
This is what I get repeatedly:
php_shuffle
123: 16707: 0.167%
132: 16641: 0.166%
213: 16569: 0.166%
231: 16751: 0.168%
312: 16532: 0.165%
321: 16800: 0.168%
yasuo_shuffle
123: 14755: 0.148%
132: 18427: 0.184%
213: 18554: 0.186%
231: 18566: 0.186%
312: 14790: 0.148%
321: 14908: 0.149%
-adam
--
adam maccabee trachtenberg
adam@trachtenberg.com