shuffle() 함수를 사용하지 않고 PHP에서 배열 순서를 무작위로 지정하는 가장 좋은 방법은 무엇입니까?
문제
취업 면접에서 이런 질문을 받았습니다.면접관과 저는 정답이 무엇인지에 대해 의견이 엇갈렸습니다.이에 대한 데이터를 가지고 있는 분이 있는지 궁금합니다.
업데이트: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];
}