PHP 的 shuffle 函數(shù)不能用于洗牌算法?
近期在測(cè)試公司的游戲時(shí)我發(fā)現(xiàn)一個(gè)問題，那就是在游戲中，每次發(fā)牌后，似乎每個(gè)人的牌都很好，這讓我對(duì)發(fā)牌的隨機(jī)性產(chǎn)生了質(zhì)疑。 盡管我們都知道，所謂的隨機(jī)其實(shí)都是偽隨機(jī)，但看到大家的牌都這么好，我不禁開始懷疑洗牌的算法到底怎么樣。
在網(wǎng)上研究了一下洗牌算法，發(fā)現(xiàn)其算法似乎并不多（常見的貌似就兩三種吧）。于是我嘗試使用了一些網(wǎng)上提供的算法，但發(fā)現(xiàn)它們與系統(tǒng)自帶的函數(shù)在洗牌（隨機(jī)）效果上相差無幾。
難道這些算法真的都不行？這確實(shí)令人困惑！然而，要證明這些算法的隨機(jī)性存在問題，確實(shí)是一個(gè)挑戰(zhàn)。畢竟只有52張牌，要完全隨機(jī)地洗牌并分配給每個(gè)人，似乎應(yīng)該是一個(gè)相對(duì)簡單的過程。那么，有沒有可能通過一些測(cè)試或統(tǒng)計(jì)方法來驗(yàn)證這些洗牌算法的隨機(jī)性呢？或者有沒有專門的工具或軟件可以幫助我們進(jìn)行這樣的驗(yàn)證呢？
面對(duì)這種情況，或許只能繼續(xù)借助搜索引擎，進(jìn)行更深入的搜索和了解。希望能夠找到更多有用的信息和解決方案，以便更好地驗(yàn)證洗牌算法的隨機(jī)性，確保游戲的公平和公正。
功夫不負(fù)有心人吧，找到了下面的關(guān)于國際撲克的各種牌型出現(xiàn)的概率的列表，圖片如下。
圖片來源是 https://www.moshike.com/a/3015.html 是這個(gè)網(wǎng)址，里面有詳細(xì)的數(shù)學(xué)論證，有興趣的可以研究一下。我這里只需要結(jié)果??！
有了這個(gè)結(jié)論，那么就好辦了，我自己通過程序多次生成牌、發(fā)牌、判斷牌型來測(cè)試一下，看看各種牌型的出現(xiàn)概率和這個(gè)網(wǎng)站給出的結(jié)論是否接近就行。
在完成測(cè)試后，我發(fā)現(xiàn)各種牌型的出現(xiàn)概率與網(wǎng)上給出的數(shù)據(jù)相當(dāng)接近（上圖就是）。由此看來，我們最初使用的系統(tǒng)函數(shù)算法與網(wǎng)上提供的洗牌算法在實(shí)現(xiàn)上應(yīng)該是相似的。為了進(jìn)一步驗(yàn)證這一結(jié)論，我建議我們查看源代碼，以比較兩者的具體實(shí)現(xiàn)。通過仔細(xì)對(duì)比和分析，我們可以確認(rèn)兩者之間的相似性，從而為我們之前的假設(shè)提供有力的證據(jù)。這將有助于我們更好地理解算法的工作原理，并提高我們對(duì)牌型出現(xiàn)概率的準(zhǔn)確預(yù)測(cè)能力。
我用的是 shuffle 函數(shù)，在源碼中找到了下面的函數(shù)：
/* {{{ 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 中還有另外一個(gè)類似的函數(shù)，str_shuffle 函數(shù)，順便看看
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));}}
兩個(gè)函數(shù)的功能類似，均由 while 循環(huán)實(shí)現(xiàn)。在 str_shuffle 中，while 循環(huán)使用 temp 變量，其類型為 char。而在 shuffle 中，while 循環(huán)使用的 temp 變量類型為 zval，zval 是 PHP 底層的一種變量類型。由于 shuffle 是用于處理數(shù)組的函數(shù)，因此使用 zval 類型更為合適。盡管兩個(gè)函數(shù)使用的變量類型不同，但它們所采用的算法是相同的。
另外，洗牌算法不僅用于洗牌，實(shí)際上它在許多其他隨機(jī)處理場景中也有應(yīng)用。例如，負(fù)載均衡算法中就使用了洗牌算法。Eureka 注冊(cè)中心的 Client 通過打亂服務(wù)器 IP 列表的順序，然后逐個(gè)取出，實(shí)現(xiàn)了隨機(jī)的負(fù)載均衡。此外，JDK 的 Collections 類的 shuffle 方法也是基于類似的原理。這些都是我在查閱資料時(shí)看到的，雖然沒有親自查看源碼，但這些信息應(yīng)該也能讓我們更好地理解洗牌算法的應(yīng)用范圍。
最后給一個(gè)結(jié)論，我自己認(rèn)為 PHP 的 shuffle 是適合當(dāng)做洗牌算法的！
我的網(wǎng)站：https://www.netor0x86.com
公眾號(hào)內(nèi)回復(fù) 【mongo】 下載 SpringBoot 整合操作 MongoDB 的文檔。
公眾號(hào)內(nèi)回復(fù) 【 cisp知識(shí)整理 】 下載 CISP 讀書筆記。
公眾號(hào)內(nèi) 回復(fù)【java開發(fā)手冊(cè)】獲取《Java開發(fā)手冊(cè)》黃山版。