Was ist der beste Weg, um ein Array, um in PHP randomisieren, ohne den shuffle () Funktion?

Question

Ich habe diese Frage in einem Vorstellungsgespräch gefragt. Der Interviewer und ich nicht einverstanden, was die richtige Antwort war. Ich frage mich, ob jemand irgendwelche Daten auf diese hat.

Update:. Ich erwähnt habe, sollte, dass die Verwendung von shuffle () war streng verboten ... sorry

Answer 1

Sie können die Fisher-Yates mische .

Answer 2

shuffle($arr);

:)

edit: sollte ich klären ... meine Definition der besten beinhaltet auch nicht nur Effizienz, sondern Code Lesbarkeit und Wartbarkeit. Standardbibliothek Funktionen bedeutet weniger Code zu erhalten und zu viel weniger zu lesen. Darüber hinaus können Sie jahrelange Debatten mit PhD Professoren über den best „echten Zufall“ -Funktion erhalten in, so jemand mit Ihnen immer auf Randomisierung Fragen nicht zustimmen wird.

Answer 3

hier Nun, die Lösung, die ich kam mit:

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;
}

Und hier ist seine Lösung:

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);
}

lief ich ein paar Versuche auf beiden Methoden (versuchen jeweils 1.000.000 mal) und die Geschwindigkeitsdifferenz war vernachlässigbar. Doch bei der tatsächlichen Zufälligkeit der Ergebnisse überprüfen ich war überrascht, wie unterschiedlich die Verteilungen waren. Hier sind meine Ergebnisse:

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

Wie Sie sehen können, die erste Methode bietet eine nahezu perfekte Verteilung anzeigt, dass es zu sein mehr oder weniger wirklich zufällig, während das zweite Verfahren ganz über den Platz ist.

Answer 4

Er testet Sie wahrscheinlich auf einem relativ häufiger Fehler machen die meisten Menschen, wenn ein Misch-Algorithmus Implementierung (dies war auch tatsächlich in der Mitte eines Kontroverse eine Online-Poker-Website vor ein paar Jahren)

Beteiligung>

Falsche Art und Weise zu mischen:

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

Die richtige Art und Weise zu mischen:

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

die Wahrscheinlichkeitsverteilung für diese Fälle Graph und es ist leicht einzusehen, warum die erste Lösung ist falsch.

Answer 5

Der „richtige“ Weg ist ziemlich vage. Die beste (schnellste / einfachste / eleganteste), um ein Array zu sortieren wäre, nur die eingebaute in shuffle () Funktion zu verwenden.

Answer 6

PHP in Funktion eine gebaut hat -> shuffle (). Ich würde sagen, sollte das tun, was Sie wollen, aber es wird wahrscheinlich meist alles andere als völlig ‚zufällig‘.

Überprüfen Sie http://computer.howstuffworks.com/question697.htm für ein wenig Beschreibung, warum seine sehr, sehr schwierig, eine vollständige Zufälligkeit zu bekommen einen Computer bilden.

Answer 7

Kurze Antwort: PHP array_rand() Funktion

Da die Verwendung der Shuffle-Funktion verboten ist, würde ich $keys = array_rand($myArray, count($myArray)) ein Array des Schlüssels von $myArray in zufälliger Reihenfolge zurückzukehren. Von dort sollte es einfach sein, sie in ein neues Array wieder zusammenzusetzen, die randomisiert wurde. So etwas wie:

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

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