shuffle() 함수를 사용하지 않고 PHP에서 배열 순서를 무작위로 지정하는 가장 좋은 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/65970

  •  09-06-2019
  •  | 
  •  

문제

취업 면접에서 이런 질문을 받았습니다.면접관과 저는 정답이 무엇인지에 대해 의견이 엇갈렸습니다.이에 대한 데이터를 가지고 있는 분이 있는지 궁금합니다.

업데이트:shuffle()의 사용은 엄격히 금지되어 있다고 언급했어야 했는데...죄송합니다.

도움이 되었습니까?

해결책

당신은 피셔-예이츠 셔플.

다른 팁

shuffle($arr);

:)

편집하다:명확히 해야 할 것 같은데...내가 정의하는 최고에는 알고리즘 효율성뿐만 아니라 코드 가독성과 유지 관리성도 포함됩니다.표준 라이브러리 함수를 사용한다는 것은 더 적은 양의 코드를 유지하고 읽는 것도 훨씬 적다는 것을 의미합니다.그 외에도 최고의 "진정한 무작위" 기능에 관해 박사 학위 교수들과 1년 동안 토론을 벌일 수 있으므로 누군가는 무작위화 질문에 대해 항상 당신의 의견에 동의하지 않을 것입니다.

제가 생각해낸 해결책은 다음과 같습니다.

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

보시다시피, 첫 번째 방법은 거의 완벽한 분포를 제공하여 거의 완전한 무작위성을 나타내는 반면, 두 번째 방법은 모든 곳에 적용됩니다.

그는 아마도 셔플링 알고리즘을 구현할 때 대부분의 사람들이 저지르는 비교적 흔한 실수에 대해 테스트하고 있을 것입니다. 논쟁 몇 년 전 온라인 포커 사이트 관련)

잘못된 순서 섞기 방법:

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

이러한 경우의 확률 분포를 그래프로 그려 보면 첫 번째 솔루션이 잘못된 이유를 쉽게 알 수 있습니다.

"올바른" 방법은 매우 모호합니다.배열을 정렬하는 가장 좋은(가장 빠르고/쉬운/가장 우아한) 방법은 내장된 shuffle() 함수를 사용하는 것입니다.

PHP에는 내장 함수 --> shuffle() 이 있습니다.나는 그것이 당신이 좋아하는 일을 해야 한다고 말하고 싶지만, 대부분은 완전히 '무작위'가 아닐 것입니다.

확인하다 http://computer.howstuffworks.com/question697.htm 컴퓨터에서 완전한 무작위성을 얻는 것이 왜 매우 어려운지에 대한 간략한 설명입니다.

짧은 답변: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];
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top