Shuffle () fonksiyonu kullanmadan PHP bir dizinin sırası rastgele için en iyi yolu nedir?

7 Cevap php

Ben bir iş görüşmesi bu soruyu sordu. Görüşmeci ve ben doğru cevap neydi aynı fikirde. Herkes bu konuda herhangi bir veri olup olmadığını merak ediyorum.

Güncelle: Ben shuffle () kullanımı kesinlikle yasak olduğunu belirtti olmalıydı ... üzgünüm.

7 Cevap

Sen Fisher-Yates shuffle kullanabilirsiniz.

($ dizi) shuffle; :)

edit: Ben en iyi benim tanımı gibi iyi verim ancak kod okunabilirliği ve bakımı algoritma değil içerir ... açıklamak gerekir. Standart kütüphane fonksiyonları kullanılarak daha az kod bakımı ve çok az okuma anlamına gelir. Bunun ötesinde, en iyi "gerçek rastgele" işlevi hakkında doktora profesör ile yıl uzun tartışmaların içine alabilirsiniz, bu yüzden birileri hep rasgele sorular size katılmıyorum.

Peki burada ben ile geldi çözüm:

function randomize_array_1($array_to_randomize) {
    $new_array = array();
    while (count($array_to_randomize) > 0) {
    	$rand_num = rand(0, count($array_to_randomize)-1);
    	$extracted = array_splice($array_to_randomize, $rand_num, 1);
    	$new_array[] = $extracted[0];
    }
    return $new_array;
}

Ve burada yaptığı çözüm:

function randomize_array_2($array_to_randomize) {
    usort($array_to_randomize, "rand_sort");
    return $array_to_randomize;
}
function rand_sort($a, $b) {
    return rand(-1, 1);
}

Ben (her 1.000.000 kere denedikten) her iki yöntem üzerinde çalışmaların bir demet koştu ve hız farkı yok denecek kadar azdı. Ancak, sonuçların gerçek rasgeleliğini kontrol üzerine ben dağılımları ne kadar farklı olduğunu şaşırdı. İşte benim sonuçlar:

randomize_array_1:
    [2, 3, 1] => 166855
    [2, 1, 3] => 166692
    [1, 2, 3] => 166690
    [3, 1, 2] => 166396
    [3, 2, 1] => 166629
    [1, 3, 2] => 166738

randomize_array_2:
    [1, 3, 2] => 147781
    [3, 1, 2] => 73972
    [3, 2, 1] => 445004
    [1, 2, 3] => 259406
    [2, 3, 1] => 49222
    [2, 1, 3] => 24615

Gördüğünüz gibi ikinci yöntem her yerde ise, ilk yöntem, daha çok veya daha az gerçekten rastgele davranıyor belirten neredeyse kusursuz bir şekilde dağılımını sağlar.

"Doğru" yol oldukça belirsiz. Bir dizi sıralamak için en iyi (hızlı / kolay / en zarif) sadece dahili shuffle () fonksiyonu kullanmak olacaktır.

) (> Shuffle - PHP bir fonksiyonu inşa etti. Ben ne gibi yapmanız gerektiğini söyleyebilirim, ama büyük olasılıkla bir şey ama tamamen 'rastgele' olacaktır.

Tam rastgele bir bilgisayar formu almak için neden onun çok, çok zor bir küçük açıklama için http://computer.howstuffworks.com/question697.htm edin.

Muhtemelen çoğu kişi yapmak nispeten yaygın hata sizi test ediyor bir karıştırma algoritması uygularken (bu bir kaç yıl önce bir online poker sitesi içeren bir controversy merkezinde aslında da oldu)

Shuffle Yanlış yol:

for (i is 1 to n) Swap i with random position between 1 and n

Shuffle doğru yolu:

for (i is 1 to n) Swap i with random position between i and n

Bu durumlar için olasılık dağılımını grafik ve ilk çözüm yanlıştır neden görmek kolaydır.

Kısa cevap: PHP'nin array_rand () fonksiyonu

Shuffle fonksiyonunun kullanımının yasak olduğu düşünüldüğünde rasgele sırayla $ myArray gelen tuşları bir dizi dönmek için, ben $ tuşlarını kullanabilirsiniz = array_rand ($ myArray, saymak ($ ​​myArray)). Oradan randomize edilmiştir, yeni bir diziye yeniden birleştirmek için basit olmalıdır. Gibi bir şey:

$keys = array_rand($myArray, count($myArray));
$newArray = array();

foreach ($keys as $key) {
$newArray[$key] = $myArray[$key];
}