PHP 的 shuffle 函数不能用于洗牌算法?
共 11037字,需浏览 23分钟
·
2024-03-23 02:30
近期在测试公司的游戏时我发现一个问题,那就是在游戏中,每次发牌后,似乎每个人的牌都很好,这让我对发牌的随机性产生了质疑。 尽管我们都知道,所谓的随机其实都是伪随机,但看到大家的牌都这么好,我不禁开始怀疑洗牌的算法到底怎么样。
在网上研究了一下洗牌算法,发现其算法似乎并不多(常见的貌似就两三种吧)。于是我尝试使用了一些网上提供的算法,但发现它们与系统自带的函数在洗牌(随机)效果上相差无几。
难道这些算法真的都不行?这确实令人困惑!然而,要证明这些算法的随机性存在问题,确实是一个挑战。毕竟只有52张牌,要完全随机地洗牌并分配给每个人,似乎应该是一个相对简单的过程。那么,有没有可能通过一些测试或统计方法来验证这些洗牌算法的随机性呢?或者有没有专门的工具或软件可以帮助我们进行这样的验证呢?
面对这种情况,或许只能继续借助搜索引擎,进行更深入的搜索和了解。希望能够找到更多有用的信息和解决方案,以便更好地验证洗牌算法的随机性,确保游戏的公平和公正。
功夫不负有心人吧,找到了下面的关于国际扑克的各种牌型出现的概率的列表,图片如下。
图片来源是 https://www.moshike.com/a/3015.html 是这个网址,里面有详细的数学论证,有兴趣的可以研究一下。我这里只需要结果!!
有了这个结论,那么就好办了,我自己通过程序多次生成牌、发牌、判断牌型来测试一下,看看各种牌型的出现概率和这个网站给出的结论是否接近就行。
在完成测试后,我发现各种牌型的出现概率与网上给出的数据相当接近(上图就是)。由此看来,我们最初使用的系统函数算法与网上提供的洗牌算法在实现上应该是相似的。为了进一步验证这一结论,我建议我们查看源代码,以比较两者的具体实现。通过仔细对比和分析,我们可以确认两者之间的相似性,从而为我们之前的假设提供有力的证据。这将有助于我们更好地理解算法的工作原理,并提高我们对牌型出现概率的准确预测能力。
我用的是 shuffle 函数,在源码中找到了下面的函数:
/* {{{ php_array_data_shuffle */
PHPAPI bool php_array_data_shuffle(const php_random_algo *algo, php_random_status *status, zval *array) /* {{{ */
{
int64_t idx, j, n_elems, rnd_idx, n_left;
zval *zv, temp;
HashTable *hash;
n_elems = zend_hash_num_elements(Z_ARRVAL_P(array));
if (n_elems < 1) {
return true;
}
hash = Z_ARRVAL_P(array);
n_left = n_elems;
if (!HT_IS_PACKED(hash)) {
if (!HT_HAS_STATIC_KEYS_ONLY(hash)) {
Bucket *p = hash->arData;
zend_long i = hash->nNumUsed;
for (; i > 0; p++, i--) {
if (p->key) {
zend_string_release(p->key);
p->key = NULL;
}
}
}
zend_hash_to_packed(hash);
}
if (EXPECTED(!HT_HAS_ITERATORS(hash))) {
if (hash->nNumUsed != hash->nNumOfElements) {
for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) {
zv = hash->arPacked + idx;
if (Z_TYPE_P(zv) == IS_UNDEF) continue;
if (j != idx) {
ZVAL_COPY_VALUE(&hash->arPacked[j], zv);
}
j++;
}
}
while (--n_left) {
rnd_idx = algo->range(status, 0, n_left);
if (EG(exception)) {
return false;
}
if (rnd_idx != n_left) {
ZVAL_COPY_VALUE(&temp, &hash->arPacked[n_left]);
ZVAL_COPY_VALUE(&hash->arPacked[n_left], &hash->arPacked[rnd_idx]);
ZVAL_COPY_VALUE(&hash->arPacked[rnd_idx], &temp);
}
}
} else {
zend_long iter_pos = zend_hash_iterators_lower_pos(hash, 0);
if (hash->nNumUsed != hash->nNumOfElements) {
for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) {
zv = hash->arPacked + idx;
if (Z_TYPE_P(zv) == IS_UNDEF) continue;
if (j != idx) {
ZVAL_COPY_VALUE(&hash->arPacked[j], zv);
if (idx == iter_pos) {
zend_hash_iterators_update(hash, idx, j);
iter_pos = zend_hash_iterators_lower_pos(hash, iter_pos + 1);
}
}
j++;
}
}
while (--n_left) {
rnd_idx = algo->range(status, 0, n_left);
if (EG(exception)) {
return false;
}
if (rnd_idx != n_left) {
ZVAL_COPY_VALUE(&temp, &hash->arPacked[n_left]);
ZVAL_COPY_VALUE(&hash->arPacked[n_left], &hash->arPacked[rnd_idx]);
ZVAL_COPY_VALUE(&hash->arPacked[rnd_idx], &temp);
zend_hash_iterators_update(hash, (uint32_t)rnd_idx, n_left);
}
}
}
hash->nNumUsed = n_elems;
hash->nInternalPointer = 0;
hash->nNextFreeElement = n_elems;
return true;
}
/* }}} */
/* {{{ Randomly shuffle the contents of an array */
PHP_FUNCTION(shuffle)
{
zval *array;
ZEND_PARSE_PARAMETERS_START(1, 1)
Z_PARAM_ARRAY_EX(array, 0, 1)
ZEND_PARSE_PARAMETERS_END();
php_array_data_shuffle(php_random_default_algo(), php_random_default_status(), array);
RETURN_TRUE;
}
/* }}} */
在 PHP 中还有另外一个类似的函数,str_shuffle 函数,顺便看看
PHPAPI bool php_binary_string_shuffle(const php_random_algo *algo, php_random_status *status, char *str, zend_long len) /* {{{ */
{
int64_t n_elems, rnd_idx, n_left;
char temp;
/* The implementation is stolen from array_data_shuffle */
/* Thus the characteristics of the randomization are the same */
n_elems = len;
if (n_elems <= 1) {
return true;
}
n_left = n_elems;
while (--n_left) {
rnd_idx = algo->range(status, 0, n_left);
if (EG(exception)) {
return false;
}
if (rnd_idx != n_left) {
temp = str[n_left];
str[n_left] = str[rnd_idx];
str[rnd_idx] = temp;
}
}
return true;
}
/* }}} */
/* {{{ Shuffles string. One permutation of all possible is created */
PHP_FUNCTION(str_shuffle)
{
zend_string *arg;
ZEND_PARSE_PARAMETERS_START(1, 1)
Z_PARAM_STR(arg)
ZEND_PARSE_PARAMETERS_END();
RETVAL_STRINGL(ZSTR_VAL(arg), ZSTR_LEN(arg));
if (Z_STRLEN_P(return_value) > 1) {
php_binary_string_shuffle(
php_random_default_algo(),
php_random_default_status(),
Z_STRVAL_P(return_value),
Z_STRLEN_P(return_value)
);
}
}
两个函数的功能类似,均由 while 循环实现。在 str_shuffle 中,while 循环使用 temp 变量,其类型为 char。而在 shuffle 中,while 循环使用的 temp 变量类型为 zval,zval 是 PHP 底层的一种变量类型。由于 shuffle 是用于处理数组的函数,因此使用 zval 类型更为合适。尽管两个函数使用的变量类型不同,但它们所采用的算法是相同的。
另外,洗牌算法不仅用于洗牌,实际上它在许多其他随机处理场景中也有应用。例如,负载均衡算法中就使用了洗牌算法。Eureka 注册中心的 Client 通过打乱服务器 IP 列表的顺序,然后逐个取出,实现了随机的负载均衡。此外,JDK 的 Collections 类的 shuffle 方法也是基于类似的原理。这些都是我在查阅资料时看到的,虽然没有亲自查看源码,但这些信息应该也能让我们更好地理解洗牌算法的应用范围。
最后给一个结论,我自己认为 PHP 的 shuffle 是适合当做洗牌算法的!
我的网站:https://www.netor0x86.com
公众号内回复 【mongo】 下载 SpringBoot 整合操作 MongoDB 的文档。
公众号内回复 【 cisp知识整理 】 下载 CISP 读书笔记。
公众号内 回复【java开发手册】获取《Java开发手册》黄山版。