자바스크립트 랜덤셔플링 알고리즘 심층 분석_자바스크립트 기술-JS 튜토리얼-php.cn

자바스크립트 랜덤셔플링 알고리즘 심층 분석_자바스크립트 기술

WBOY

풀어 주다： 2016-05-16 16:45:32

원래의

1659명이 탐색했습니다.

셔플링 알고리즘은 게임이나 무작위 정렬을 할 때 자주 접하는 일반적인 무작위 문제입니다. 이는 다음과 같이 추상화될 수 있습니다. M 내의 모든 자연수의 무작위 시퀀스 배열을 얻습니다.

Baidu에서 "Shuffling Algorithm"을 검색하면 첫 번째 결과는 "Baidu Library-Shuffling Algorithm"입니다. 내용을 스캔한 후 결국 배열 대신 연결된 목록을 사용하는 것을 포함하여 많은 내용이 쉽게 다른 사람을 잘못된 길로 인도할 수 있습니다. 또한 제한된 최적화일 뿐입니다(연결된 목록도 읽기 효율성을 떨어뜨립니다).

이 글의 첫 번째 방법은 간단하게 설명할 수 있습니다. 카드를 무작위로 뽑아 다른 그룹에 넣습니다. 빈 카드를 뽑으면 다시 뽑습니다.
"빈 카드를 뽑았다면 다시 뽑으세요." 이렇게 하면 나중에 빈 카드를 뽑을 확률이 높아지는 것은 분명 불합리한 일입니다.
한 단계로 최적화할 수 있습니다. 카드를 제거한 후 원래 카드가 줄어듭니다. (빈 카드를 놔두는 대신)
코드는 다음과 같습니다.

코드를 복사하세요코드는 다음과 같습니다.

function shuffle_pick_1(m) //셔플//카드 그리기 방법
{
//m개의 카드 생성
var arr = new Array(m);
for (var i=0 ; i arr[i] = i;
}

//매번 카드 한 장을 뽑아 다른 더미에 넣습니다. 배열에서 요소를 추출하고 모든 후속 요소를 하나씩 앞으로 당겨야 하기 때문에 시간이 많이 걸립니다.
var arr2 = new Array();
for (var i=m; i>0; i--) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}

또한 배열이 매우 큰 경우 중간에 요소를 삭제하면 후속 대기열이 앞으로 이동하게 되어 매우 시간이 많이 걸리는 작업이기 때문에 분명히 문제가 있습니다.
"왜 그 요소를 삭제하는가?"를 기억하세요. 목적은 빈 카드를 생성하는 것이 아닙니다.
해당 요소를 삭제하는 것 외에 빈 카드를 제거할 수 있는 다른 방법이 있나요?
---네, 뽑지 않은 마지막 카드를 뽑은 위치에 놓기만 하면 됩니다.
이 아이디어를 다음과 같이 최적화할 수 있습니다.

코드 복사 코드는 다음과 같습니다.

function shuffle_pick(m) //shuffle/ /pump 카드 최적화 카드
{
// m개의 카드 생성
var arr = new Array(m);
for (var i=0; i arr [i] = 나;
}

//매번 카드 한 장을 뽑아 다른 더미에 넣습니다. 뽑지 않은 마지막 카드를 빈 자리에 놓습니다.
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2 .push(arr[rnd]);
arr[rnd] = arr[--i];
}
return arr2;
}

그리기 제외 카드 아이디어는 카드를 바꾸는 아이디어도 사용할 수 있습니다.
"Baidu Wenku - Shuffling Algorithm"에서는 카드 변경 아이디어에 대해 다음과 같이 언급합니다. "두 위치를 무작위로 총 n번 교환합니다. n이 클수록 무작위성에 가까워집니다."
이 접근 방식은 잘못된 것입니다. n이 매우 큰 경우(예: 카드 10개, 스왑 10개) "일부 카드의 위치가 전혀 변경되지 않았을" 가능성이 여전히 높습니다.
이 아이디어에 따라 약간의 조정을 해보세요. i번째 카드의 위치를 다른 카드로 변경한 다음 라운드를 마무리하세요.
코드는 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

function shuffle_swap(m) //shuffle/ /swap 카드 방법
{
// m개의 카드 생성
var arr = new Array(m);
for (var i=0; i arr[ 나는 ] = 나는;
}

//한 라운드 후에 i번째 카드를 다른 카드로 교체
for (var i=0; i var rnd = Math.floor( Math.random()* (i 1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}

카드를 뽑고 교환하는 아이디어 외에도 카드를 삽입하는 아이디어도 활용할 수 있습니다. 먼저 카드가 하나 있고, 두 번째 카드에는 무작위로 삽입할 수 있는 위치가 두 군데 있습니다(전후 첫 번째 카드), 세 번째 카드를 무작위로 삽입할 수 있는 위치는 세 군데(뒤, 첫 번째, 두 번째) 등
코드는 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

function shuffle_insert_1(m) //shuffle/ /insert Card 메소드 
{
 //매번 가장 큰 카드를 생성하여 임의의 카드 앞에 삽입합니다. 배열에 요소를 삽입하고 모든 후속 요소를 한 위치 뒤로 밀어야 하기 때문에 시간이 많이 걸립니다. 
 var arr = [0];
 for (var i=1; i arr.splice(Math.floor(Math.random()*(i 1)), 0,i);
 }
 return arr;
}

위 코드에도 몇 가지 문제가 있습니다. 카드 수가 늘어날수록 카드를 삽입하면 이후에 많은 카드가 뒤로 밀려나게 되기 때문에 카드 삽입이 점점 더 어려워집니다.
물론 적절하게 최적화할 수도 있습니다. 먼저 n-1개의 카드가 있고 n번째 카드가 끝에 배치된 다음 임의의 카드와 위치를 바꿉니다.
코드는 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

function shuffle_insert(m) //shuffle/ /insert 카드 방식의 최적화된 버전은 이러한 종류의 셔플링이 균일하다는 수학적 귀납법을 통해 증명할 수 있습니다. 
{
 //매번 가장 높은 카드를 생성하고 무작위 카드로 장소를 바꿉니다
 var arr = new Array(m);
 arr[0] = 0;
 for (var i=1; i var rnd = Math.floor(Math.random()*(i 1));
 arr[i] = arr[rnd] ;
 arr [rnd] = i;
 }
 return arr;
}

전체 코드는 다음과 같습니다. 관심 있는 학생들은 자신의 컴퓨터에서 실행해 보고 각자의 실행 효율성과 최종 결과가 이론적으로 무작위인지 확인할 수 있습니다.

코드 복사 코드는 다음과 같습니다.

< title>JK：자바스크립트 셔플링 알고리즘