Qual è il modo migliore per randomizzare l'ordine di un array in PHP senza utilizzare la funzione shuffle()?

Question

Questa domanda mi è stata posta durante un colloquio di lavoro.L’intervistatore e io non eravamo d’accordo su quale fosse la risposta corretta.Chiedo se qualcuno ha dati a riguardo.

Aggiornamento:Avrei dovuto dire che l'uso di shuffle() era severamente vietato...Scusa.

Answer 1

Potresti usare il Mescolamento Fisher-Yates.

Answer 2

shuffle($arr);

:)

modificare:dovrei chiarire...la mia definizione di migliore coinvolge non solo l'efficienza dell'algoritmo ma anche la leggibilità e la manutenibilità del codice.Usare le funzioni della libreria standard significa mantenere meno codice e anche leggere molto meno.Oltre a ciò, puoi partecipare a dibattiti di un anno con professori di dottorato sulla migliore funzione "vero casuale", quindi qualcuno non sarà sempre d'accordo con te sulle domande sulla randomizzazione.

Answer 3

Bene, ecco la soluzione che ho trovato:

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

Ed ecco la sua soluzione:

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

Ho eseguito una serie di prove su entrambi i metodi (provando ciascuno 1.000.000 di volte) e la differenza di velocità era trascurabile.Tuttavia, dopo aver verificato l'effettiva casualità dei risultati, sono rimasto sorpreso da quanto fossero diverse le distribuzioni.Ecco i miei risultati:

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

Come puoi vedere, il primo metodo fornisce una distribuzione quasi perfetta, indicando che è più o meno veramente casuale, mentre il secondo metodo è ovunque.

Answer 4

Probabilmente ti sta mettendo alla prova su un errore relativamente comune che la maggior parte delle persone commette quando implementa un algoritmo di mescolamento (anche questo era in realtà al centro di un controversia coinvolgendo un sito di poker online qualche anno fa)

Modo errato di mescolare:

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

Modo corretto per mescolare:

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

Disegna la distribuzione di probabilità per questi casi ed è facile capire perché la prima soluzione non è corretta.

Answer 5

Il modo "corretto" è piuttosto vago.Il modo migliore (più veloce/più semplice/più elegante) per ordinare un array sarebbe utilizzare semplicemente la funzione shuffle() incorporata.

Answer 6

PHP ha una funzione integrata --> shuffle() .Direi che dovrebbe fare quello che vuoi, ma molto probabilmente sarà tutt'altro che totalmente "casuale".

Controllo http://computer.howstuffworks.com/question697.htm per una breve descrizione del motivo per cui è molto, molto difficile ottenere la completa casualità da un computer.

Answer 7

Risposta breve:PHP array_rand() funzione

Dato che l'uso della funzione shuffle è vietato, utilizzerei $keys = array_rand($myArray, count($myArray)) per restituire un array di chiavi da $myArray in ordine casuale.Da lì dovrebbe essere semplice riassemblarli in un nuovo array randomizzato.Qualcosa di simile a:

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

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