3

就職面接でこんな質問をされました。インタビュアーと私はどちらが正解か意見が分かれました。誰かがこれに関するデータを持っているかどうか疑問に思っています。

更新: shuffle() の使用は固く禁じられていることを言及する必要がありました...申し訳ありません。

4

7 に答える 7

4 
shuffle($arr);

:)

編集:明確にする必要があります...私の定義には、アルゴリズムの効率だけでなく、コードの読みやすさと保守性も含まれます。標準ライブラリ関数を使用するということは、維持するコードが少なくなり、読む量も少なくなることを意味します。それを超えて、博士号の教授と、最良の「真のランダム」関数について 1 年にわたる議論に入ることができます。

于 2008-09-15T19:30:10.887 に答える
3

さて、私が思いついた解決策は次のとおりです。

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

そして、これが彼の解決策です：

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

両方の方法で一連の試行を実行しました (それぞれ 1,000,000 回試行) が、速度の違いはごくわずかでした。しかし、結果の実際のランダム性を確認したところ、分布がいかに異なっているかに驚きました。ここに私の結果があります：

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

ご覧のとおり、最初の方法はほぼ完全な分布を示しており、ほぼ完全にランダムであることを示していますが、2 番目の方法はいたるところにあります。

于 2008-09-15T20:49:34.190 に答える
2

フィッシャー-イェーツシャッフルを使用できます。

于 2008-09-15T20:32:26.290 に答える
1

彼はおそらく、ほとんどの人がシャッフル アルゴリズムを実装する際に犯す比較的一般的な間違いについてテストしているのでしょう (これは、数年前にオンライン ポーカー サイトを巻き込んだ論争の中心でもありました)。

シャッフルの間違った方法:

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

シャッフルする正しい方法:

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

これらのケースの確率分布をグラフにすると、最初の解が正しくない理由が簡単にわかります。

于 2008-09-15T20:44:30.427 に答える
0

PHPには組み込み関数->shuffle（）があります。私はそれがあなたが好きなことをするべきだと言うでしょう、しかしそれはほとんど完全に「ランダム」ではないでしょう。

コンピューターから完全なランダム性を取得することが非常に難しい理由の簡単な説明については、http：//computer.howstuffworks.com/question697.htmを確認してください。

于 2008-09-15T20:08:21.780 に答える
0

簡単な答え: PHP のarray_rand()機能

シャッフル関数の使用が禁止されていることを考えると$keys = array_rand($myArray, count($myArray))、キーの配列を$myArrayランダムな順序で返すために使用します。そこから、それらをランダム化された新しい配列に再構築するのは簡単なはずです。何かのようなもの：

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

foreach ($keys as $key) {
$newArray[$key] = $myArray[$key];
}
于 2008-09-15T20:35:49.793 に答える
0

「正しい」方法はかなりあいまいです。配列をソートするための最良の (最速 / 最も簡単 / 最もエレガント) は、組み込みの shuffle() 関数を使用することです。

于 2008-09-15T19:37:15.160 に答える