[PHP-DEV] Bug #7045 Updated: Shuffle() does not behave correctly
ID: 7045
Updated by: lobbin
Reported By: [EMAIL PROTECTED]
Status: Open
Bug Type: Arrays related
Operating System: Linux RH 6 and 7
PHP Version: 4.1.0
Assigned To: rodif_bl
New Comment:
Can someone check/commit this? :)
Previous Comments:
[2002-01-12 20:45:00] [EMAIL PROTECTED]
here is a patch that fixes the
shuffle and adds ashuffle.
Im pretty new to this list and if someone could tell me
if i can/should apply this to cvs?
--- ext/standard/array.c.oldSat Jan 12 04:23:55 2002
+++ ext/standard/array.cSat Jan 12 10:03:17 2002
@@ -1415,13 +1415,72 @@
}
/* }}} */
-
-static int array_data_shuffle(const void *a, const void *b TSRMLS_DC)
+static int php_rand_sort(void *base, size_t nmemb, size_t size, int
(*cmp)(const void *, const void *))
{
- return (php_rand(TSRMLS_C) % 2) ? 1 : -1;
+Bucket *t, **new_order;
+HashTable *ht;
+int i, j;
+ulong num_key;
+char *string_key;
+
+int status, *tmp;
+
+new_order = emalloc(sizeof(Bucket *) * nmemb);
+
+ALLOC_HASHTABLE(ht);
+zend_hash_init(ht, 0, NULL, ZVAL_PTR_DTOR, 0);
+
+for(i = 0;i nmemb;i++)
+{
+zval *z_rand;
+MAKE_STD_ZVAL(z_rand);
+ZVAL_LONG(z_rand,rand());
+
+t = *(((Bucket **)base) + i);
+if(t-nKeyLength == 0)
+status = zend_hash_index_update(ht, t-h, z_rand,
sizeof(zval *), NULL);
+else
+status = zend_hash_update(ht, t-arKey, t-nKeyLength,
z_rand, sizeof(zval *), NULL);
+}
+
+set_compare_func(SORT_NUMERIC TSRMLS_CC);
+zend_hash_sort(ht, qsort, array_data_compare, 0);
+
+zend_hash_internal_pointer_reset(ht);
+for(i = 0;i nmemb;i++)
+{
+switch(zend_hash_get_current_key(ht, string_key,
num_key, 1))
+{
+case HASH_KEY_IS_STRING:
+for(j = 0;j nmemb;j++)
+{
+t = *(((Bucket **)base) + j);
+
if(!strncmp(t-arKey,string_key,t-nKeyLength))
+{
+new_order[i] = *(((Bucket **)base) + j);
+break;
+}
+}
+break;
+case HASH_KEY_IS_LONG:
+for(j = 0;j nmemb;j++)
+{
+t = *(((Bucket **)base) + j);
+if(t-h == num_key)
+{
+new_order[i] = *(((Bucket **)base) + j);
+break;
+}
+}
+break;
+}
+zend_hash_move_forward(ht);
+}
+memcpy(base, new_order, size * nmemb);
+zend_hash_destroy(ht);
+efree(new_order);
}
-
/* {{{ proto bool shuffle(array array_arg)
Randomly shuffle the contents of an array */
PHP_FUNCTION(shuffle)
@@ -1431,7 +1490,23 @@
if (zend_parse_parameters(1 TSRMLS_CC, a, array) == FAILURE) {
RETURN_FALSE;
}
- if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_mergesort,
array_data_shuffle, 1 TSRMLS_CC) == FAILURE) {
+ if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_rand_sort,
NULL, 1 TSRMLS_CC) == FAILURE) {
+ RETURN_FALSE;
+ }
+ RETURN_TRUE;
+}
+/* }}} */
+
+/* {{{ proto bool ashuffle(array array_arg)
+ Randomly shuffle the contents of an array keeping keys intact*/
+PHP_FUNCTION(ashuffle)
+{
+ zval *array;
+
+ if (zend_parse_parameters(1 TSRMLS_CC, a, array) == FAILURE) {
+ RETURN_FALSE;
+ }
+ if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_rand_sort,
NULL, 0 TSRMLS_CC) == FAILURE) {
RETURN_FALSE;
}
RETURN_TRUE;
@@ -2880,7 +2955,7 @@
}
if (num_req_val == num_avail) {
- if (zend_hash_sort(Z_ARRVAL_P(return_value),
(sort_func_t)php_mergesort, array_data_shuffle, 1 TSRMLS_CC) ==
FAILURE) {
+ if (zend_hash_sort(Z_ARRVAL_P(return_value),
(sort_func_t)php_rand_sort, NULL, 1 TSRMLS_CC) == FAILURE) {
zval_dtor(return_value);
RETURN_FALSE;
}
--- ext/standard/php_array.h.oldSat Jan 12 10:11:26 2002
+++ ext/standard/php_array.hSat Jan 12 10:11:40 2002
@@ -55,6 +55,7 @@
PHP_FUNCTION(array_fill);
PHP_FUNCTION(range);
PHP_FUNCTION(shuffle);
+PHP_FUNCTION(ashuffle);
PHP_FUNCTION(array_multisort);
PHP_FUNCTION(array_push);
PHP_FUNCTION(array_pop);
--- ext/standard/basic_functions.c.old Sat Jan 12 10:10:36 2002
+++ ext/standard/basic_functions.c Sat Jan 12
[PHP-DEV] Bug #7045 Updated: Shuffle() does not behave correctly
attaching diff's
__
Do You Yahoo!?
Send FREE video emails in Yahoo! Mail!
http://promo.yahoo.com/videomail/
--- ext/standard/array.c.oldSat Jan 12 04:23:55 2002
+++ ext/standard/array.cSat Jan 12 10:03:17 2002
@@ -1415,13 +1415,72 @@
}
/* }}} */
-
-static int array_data_shuffle(const void *a, const void *b TSRMLS_DC)
+static int php_rand_sort(void *base, size_t nmemb, size_t size, int (*cmp)(const void
+*, const void *))
{
- return (php_rand(TSRMLS_C) % 2) ? 1 : -1;
+Bucket *t, **new_order;
+HashTable *ht;
+int i, j;
+ulong num_key;
+char *string_key;
+
+int status, *tmp;
+
+new_order = emalloc(sizeof(Bucket *) * nmemb);
+
+ALLOC_HASHTABLE(ht);
+zend_hash_init(ht, 0, NULL, ZVAL_PTR_DTOR, 0);
+
+for(i = 0;i nmemb;i++)
+{
+zval *z_rand;
+MAKE_STD_ZVAL(z_rand);
+ZVAL_LONG(z_rand,rand());
+
+t = *(((Bucket **)base) + i);
+if(t-nKeyLength == 0)
+status = zend_hash_index_update(ht, t-h, z_rand, sizeof(zval *),
+NULL);
+else
+status = zend_hash_update(ht, t-arKey, t-nKeyLength, z_rand,
+sizeof(zval *), NULL);
+}
+
+set_compare_func(SORT_NUMERIC TSRMLS_CC);
+zend_hash_sort(ht, qsort, array_data_compare, 0);
+
+zend_hash_internal_pointer_reset(ht);
+for(i = 0;i nmemb;i++)
+{
+switch(zend_hash_get_current_key(ht, string_key, num_key, 1))
+{
+case HASH_KEY_IS_STRING:
+for(j = 0;j nmemb;j++)
+{
+t = *(((Bucket **)base) + j);
+if(!strncmp(t-arKey,string_key,t-nKeyLength))
+{
+new_order[i] = *(((Bucket **)base) + j);
+break;
+}
+}
+break;
+case HASH_KEY_IS_LONG:
+for(j = 0;j nmemb;j++)
+{
+t = *(((Bucket **)base) + j);
+if(t-h == num_key)
+{
+new_order[i] = *(((Bucket **)base) + j);
+break;
+}
+}
+break;
+}
+zend_hash_move_forward(ht);
+}
+memcpy(base, new_order, size * nmemb);
+zend_hash_destroy(ht);
+efree(new_order);
}
-
/* {{{ proto bool shuffle(array array_arg)
Randomly shuffle the contents of an array */
PHP_FUNCTION(shuffle)
@@ -1431,7 +1490,23 @@
if (zend_parse_parameters(1 TSRMLS_CC, a, array) == FAILURE) {
RETURN_FALSE;
}
- if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_mergesort,
array_data_shuffle, 1 TSRMLS_CC) == FAILURE) {
+ if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_rand_sort, NULL, 1
+TSRMLS_CC) == FAILURE) {
+ RETURN_FALSE;
+ }
+ RETURN_TRUE;
+}
+/* }}} */
+
+/* {{{ proto bool ashuffle(array array_arg)
+ Randomly shuffle the contents of an array keeping keys intact*/
+PHP_FUNCTION(ashuffle)
+{
+ zval *array;
+
+ if (zend_parse_parameters(1 TSRMLS_CC, a, array) == FAILURE) {
+ RETURN_FALSE;
+ }
+ if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_rand_sort, NULL, 0
+TSRMLS_CC) == FAILURE) {
RETURN_FALSE;
}
RETURN_TRUE;
@@ -2880,7 +2955,7 @@
}
if (num_req_val == num_avail) {
- if (zend_hash_sort(Z_ARRVAL_P(return_value),
(sort_func_t)php_mergesort, array_data_shuffle, 1 TSRMLS_CC) == FAILURE) {
+ if (zend_hash_sort(Z_ARRVAL_P(return_value),
+(sort_func_t)php_rand_sort, NULL, 1 TSRMLS_CC) == FAILURE) {
zval_dtor(return_value);
RETURN_FALSE;
}
--- ext/standard/basic_functions.c.old Sat Jan 12 10:10:36 2002
+++ ext/standard/basic_functions.c Sat Jan 12 10:10:54 2002
@@ -748,6 +748,7 @@
PHP_FE(uasort, first_arg_force_ref)
PHP_FE(uksort, first_arg_force_ref)
PHP_FE(shuffle, first_arg_force_ref)
+ PHP_FE(ashuffle,first_arg_force_ref)
PHP_FE(array_walk, first_arg_force_ref)
PHP_FE(count,
NULL)
PHP_FE(end, first_arg_force_ref)
--- ext/standard/php_array.h.oldSat Jan 12 10:11:26 2002
+++ ext/standard/php_array.hSat Jan 12 10:11:40 2002
@@ -55,6 +55,7 @@
[PHP-DEV] Bug #7045 Updated: Shuffle() does not behave correctly
ID: 7045
Updated by: rodif_bl
Reported By: [EMAIL PROTECTED]
Status: Open
Bug Type: Arrays related
Operating System: Linux RH 6 and 7
PHP Version: 4.1.0
Old Assigned To:
Assigned To: rodif_bl
Previous Comments:
[2001-12-13 16:21:02] [EMAIL PROTECTED]
Still behaves the same on PHP 4.1.0/Linux
[2001-10-15 09:00:00] [EMAIL PROTECTED]
Any news on this?
Derick
[2000-10-30 10:07:36] [EMAIL PROTECTED]
This is probably the property of sort algorithm used in shuffle.
Whoever wrote it, please take attention!
[2000-10-05 18:36:22] [EMAIL PROTECTED]
Shuffle() does NOT behave correctly
[2000-10-05 18:33:23] [EMAIL PROTECTED]
Description
I use shuffle() on an array and pick the first element of the array
When repeating this operation the distribution of the value of the
first element is not balanced
Test script
srand((double)microtime()*100);
$result = array();
$A=array();
$N = 10;
for ($i=0;$i$N;$i++) $result[$i] = 0;
for ($i=0;$i1;$i++)
{
for ($j=0;$j$N;$j++) $A[$j]=$j;
shuffle($A);
$r = $A[0];
// echo nbsp;.$r;
$result[$r]++;
}
echo br;
for ($i=0;$i$N;$i++) echo $i.=. $result[$i].br;
Results script runned 3 times
0=1248
1=1216
2=1328
3=1224
4=1260
5=1264
6=803
7=778
8=555
9=324
0=1266
1=1236
2=1302
3=1198
4=1226
5=1246
6=841
7=778
8=567
9=340
0=1246
1=1251
2=1309
3=1207
4=1243
5=1274
6=826
7=782
8=537
9=325
php.ini
[PHP]
;;;
; About this file ;
;;;
; This file controls many aspects of PHP's behavior. In order for PHP
to
; read it, it must be named 'php.ini'. PHP looks for it in the
current
; working directory, in the path designated by the environment
variable
; PHPRC, and in the path that was defined in compile time (in that
order).
; Under Windows, the compile-time path is the Windows directory. The
; path in which the php.ini file is looked for can be overriden using
; the -c argument in command line mode.
;
; The syntax of the file is extremely simple. Whitespace and Lines
; beginning with a semicolon are silently ignored (as you probably
guessed).
; Section headers (e.g. [Foo]) are also silently ignored, even though
; they might mean something in the future.
;
; Directives are specified using the following syntax:
; directive = value
; Directive names are *case sensitive* - foo=bar is different from
FOO=bar.
;
; The value can be a string, a number, a PHP constant (e.g. E_ALL or
M_PI), one
; of the INI constants (On, Off, True, False, Yes, No and None) or an
expression
; (e.g. E_ALL ~E_NOTICE), or a quoted string (foo).
;
; Expressions in the INI file are limited to bitwise operators and
parentheses:
; | bitwise OR
; bitwise AND
; ~ bitwise NOT
; ! boolean NOT
;
; Boolean flags can be turned on using the values 1, On, True or Yes.
; They can be turned off using the values 0, Off, False or No.
;
; An empty string can be denoted by simply not writing anything after
the equal
; sign, or by using the None keyword:
;
; foo = ; sets foo to an empty string
; foo = none ; sets foo to an empty string
; foo = none; sets foo to the string 'none'
;
; If you use constants in your value, and these constants belong to a
dynamically
; loaded extension (either a PHP extension or a Zend extension), you
may only
; use these constants *after* the line that loads the extension.
;
; All the values in the php.ini-dist file correspond to the builtin
; defaults (that is, if no php.ini is used, or if you delete these
lines,
; the builtin defaults will be identical).
; Language Options ;
engine = On ; Enable the PHP scripting language engine
under Apache
short_open_tag = On ; allow the ? tag. otherwise, only ?php and
script tags are recognized.
asp_tags= Off ; allow ASP-style % % tags
precision = 14 ; number of significant digits displayed in
floating
point numbers
y2k_compliance = Off ; whether to be year 2000 compliant (will cause
problems with non y2k compliant browsers)
output_buffering= Off ; Output buffering allows you to send header
lines (including cookies)
; even after you send body
content, in the price of slowing
PHP's
[PHP-DEV] Bug #7045 Updated: Shuffle() does not behave correctly
ID: 7045
Updated by: rodif_bl
Reported By: [EMAIL PROTECTED]
Status: Open
Bug Type: Arrays related
Operating System: Linux RH 6 and 7
PHP Version: 4.1.0
Assigned To: rodif_bl
New Comment:
here is a patch that fixes the
shuffle and adds ashuffle.
Im pretty new to this list and if someone could tell me
if i can/should apply this to cvs?
--- ext/standard/array.c.oldSat Jan 12 04:23:55 2002
+++ ext/standard/array.cSat Jan 12 10:03:17 2002
@@ -1415,13 +1415,72 @@
}
/* }}} */
-
-static int array_data_shuffle(const void *a, const void *b TSRMLS_DC)
+static int php_rand_sort(void *base, size_t nmemb, size_t size, int
(*cmp)(const void *, const void *))
{
- return (php_rand(TSRMLS_C) % 2) ? 1 : -1;
+Bucket *t, **new_order;
+HashTable *ht;
+int i, j;
+ulong num_key;
+char *string_key;
+
+int status, *tmp;
+
+new_order = emalloc(sizeof(Bucket *) * nmemb);
+
+ALLOC_HASHTABLE(ht);
+zend_hash_init(ht, 0, NULL, ZVAL_PTR_DTOR, 0);
+
+for(i = 0;i nmemb;i++)
+{
+zval *z_rand;
+MAKE_STD_ZVAL(z_rand);
+ZVAL_LONG(z_rand,rand());
+
+t = *(((Bucket **)base) + i);
+if(t-nKeyLength == 0)
+status = zend_hash_index_update(ht, t-h, z_rand,
sizeof(zval *), NULL);
+else
+status = zend_hash_update(ht, t-arKey, t-nKeyLength,
z_rand, sizeof(zval *), NULL);
+}
+
+set_compare_func(SORT_NUMERIC TSRMLS_CC);
+zend_hash_sort(ht, qsort, array_data_compare, 0);
+
+zend_hash_internal_pointer_reset(ht);
+for(i = 0;i nmemb;i++)
+{
+switch(zend_hash_get_current_key(ht, string_key,
num_key, 1))
+{
+case HASH_KEY_IS_STRING:
+for(j = 0;j nmemb;j++)
+{
+t = *(((Bucket **)base) + j);
+
if(!strncmp(t-arKey,string_key,t-nKeyLength))
+{
+new_order[i] = *(((Bucket **)base) + j);
+break;
+}
+}
+break;
+case HASH_KEY_IS_LONG:
+for(j = 0;j nmemb;j++)
+{
+t = *(((Bucket **)base) + j);
+if(t-h == num_key)
+{
+new_order[i] = *(((Bucket **)base) + j);
+break;
+}
+}
+break;
+}
+zend_hash_move_forward(ht);
+}
+memcpy(base, new_order, size * nmemb);
+zend_hash_destroy(ht);
+efree(new_order);
}
-
/* {{{ proto bool shuffle(array array_arg)
Randomly shuffle the contents of an array */
PHP_FUNCTION(shuffle)
@@ -1431,7 +1490,23 @@
if (zend_parse_parameters(1 TSRMLS_CC, a, array) == FAILURE) {
RETURN_FALSE;
}
- if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_mergesort,
array_data_shuffle, 1 TSRMLS_CC) == FAILURE) {
+ if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_rand_sort,
NULL, 1 TSRMLS_CC) == FAILURE) {
+ RETURN_FALSE;
+ }
+ RETURN_TRUE;
+}
+/* }}} */
+
+/* {{{ proto bool ashuffle(array array_arg)
+ Randomly shuffle the contents of an array keeping keys intact*/
+PHP_FUNCTION(ashuffle)
+{
+ zval *array;
+
+ if (zend_parse_parameters(1 TSRMLS_CC, a, array) == FAILURE) {
+ RETURN_FALSE;
+ }
+ if (zend_hash_sort(Z_ARRVAL_PP(array), (sort_func_t)php_rand_sort,
NULL, 0 TSRMLS_CC) == FAILURE) {
RETURN_FALSE;
}
RETURN_TRUE;
@@ -2880,7 +2955,7 @@
}
if (num_req_val == num_avail) {
- if (zend_hash_sort(Z_ARRVAL_P(return_value),
(sort_func_t)php_mergesort, array_data_shuffle, 1 TSRMLS_CC) ==
FAILURE) {
+ if (zend_hash_sort(Z_ARRVAL_P(return_value),
(sort_func_t)php_rand_sort, NULL, 1 TSRMLS_CC) == FAILURE) {
zval_dtor(return_value);
RETURN_FALSE;
}
--- ext/standard/php_array.h.oldSat Jan 12 10:11:26 2002
+++ ext/standard/php_array.hSat Jan 12 10:11:40 2002
@@ -55,6 +55,7 @@
PHP_FUNCTION(array_fill);
PHP_FUNCTION(range);
PHP_FUNCTION(shuffle);
+PHP_FUNCTION(ashuffle);
PHP_FUNCTION(array_multisort);
PHP_FUNCTION(array_push);
PHP_FUNCTION(array_pop);
--- ext/standard/basic_functions.c.old Sat Jan 12 10:10:36 2002
+++ ext/standard/basic_functions.c Sat Jan 12 10:10:54 2002
@@ -748,6 +748,7 @@
PHP_FE(uasort, first_arg_force_ref)
PHP_FE(uksort, first_arg_force_ref)
[PHP-DEV] Bug #7045 Updated: Shuffle() does not behave correctly
ID: 7045
Updated by: sniper
Reported By: [EMAIL PROTECTED]
Old Summary: Shuffle() does behave correctly
Status: Open
Bug Type: Arrays related
Operating System: Linux RH 6 and 7
Old PHP Version: 4.0.1pl2
PHP Version: 4.1.0
New Comment:
updated php version and short summary.
Previous Comments:
[2001-12-13 16:21:02] [EMAIL PROTECTED]
Still behaves the same on PHP 4.1.0/Linux
[2001-10-15 09:00:00] [EMAIL PROTECTED]
Any news on this?
Derick
[2000-10-30 10:07:36] [EMAIL PROTECTED]
This is probably the property of sort algorithm used in shuffle. Whoever wrote it,
please take attention!
[2000-10-05 18:36:22] [EMAIL PROTECTED]
Shuffle() does NOT behave correctly
[2000-10-05 18:33:23] [EMAIL PROTECTED]
Description
I use shuffle() on an array and pick the first element of the array
When repeating this operation the distribution of the value of the first element is
not balanced
Test script
srand((double)microtime()*100);
$result = array();
$A=array();
$N = 10;
for ($i=0;$i$N;$i++) $result[$i] = 0;
for ($i=0;$i1;$i++)
{
for ($j=0;$j$N;$j++) $A[$j]=$j;
shuffle($A);
$r = $A[0];
// echo nbsp;.$r;
$result[$r]++;
}
echo br;
for ($i=0;$i$N;$i++) echo $i.=. $result[$i].br;
Results script runned 3 times
0=1248
1=1216
2=1328
3=1224
4=1260
5=1264
6=803
7=778
8=555
9=324
0=1266
1=1236
2=1302
3=1198
4=1226
5=1246
6=841
7=778
8=567
9=340
0=1246
1=1251
2=1309
3=1207
4=1243
5=1274
6=826
7=782
8=537
9=325
php.ini
[PHP]
;;;
; About this file ;
;;;
; This file controls many aspects of PHP's behavior. In order for PHP to
; read it, it must be named 'php.ini'. PHP looks for it in the current
; working directory, in the path designated by the environment variable
; PHPRC, and in the path that was defined in compile time (in that order).
; Under Windows, the compile-time path is the Windows directory. The
; path in which the php.ini file is looked for can be overriden using
; the -c argument in command line mode.
;
; The syntax of the file is extremely simple. Whitespace and Lines
; beginning with a semicolon are silently ignored (as you probably guessed).
; Section headers (e.g. [Foo]) are also silently ignored, even though
; they might mean something in the future.
;
; Directives are specified using the following syntax:
; directive = value
; Directive names are *case sensitive* - foo=bar is different from FOO=bar.
;
; The value can be a string, a number, a PHP constant (e.g. E_ALL or M_PI), one
; of the INI constants (On, Off, True, False, Yes, No and None) or an expression
; (e.g. E_ALL ~E_NOTICE), or a quoted string (foo).
;
; Expressions in the INI file are limited to bitwise operators and parentheses:
; | bitwise OR
; bitwise AND
; ~ bitwise NOT
; ! boolean NOT
;
; Boolean flags can be turned on using the values 1, On, True or Yes.
; They can be turned off using the values 0, Off, False or No.
;
; An empty string can be denoted by simply not writing anything after the equal
; sign, or by using the None keyword:
;
; foo = ; sets foo to an empty string
; foo = none ; sets foo to an empty string
; foo = none; sets foo to the string 'none'
;
; If you use constants in your value, and these constants belong to a dynamically
; loaded extension (either a PHP extension or a Zend extension), you may only
; use these constants *after* the line that loads the extension.
;
; All the values in the php.ini-dist file correspond to the builtin
; defaults (that is, if no php.ini is used, or if you delete these lines,
; the builtin defaults will be identical).
; Language Options ;
engine = On ; Enable the PHP scripting language engine
under Apache
short_open_tag = On ; allow the ? tag. otherwise, only ?php and
script tags are recognized.
asp_tags= Off ; allow ASP-style % % tags
precision = 14 ; number of significant digits displayed in
floating point numbers
y2k_compliance = Off ; whether to be year 2000 compliant (will cause
problems with non y2k compliant browsers)
output_buffering= Off ; Output buffering allows you to send header lines
(including cookies)
; even after you send body
