셔플 링 알고리즘은 게임을하고 무작위로 정렬 할 때 발생하는 일반적인 무작위 문제입니다. 다음과 같이 추상화 될 수 있습니다.
Baidu에서 "Reshuffle Algorithm"을 검색 한 첫 번째 결과는 "Baidu Library -Ruffle Algorithm"이었습니다. 내용을 스캔 한 후, 많은 내용물이 결국 어레이를 대체하기 위해 링크 된 목록을 사용하여 제한된 최적화 일뿐입니다 (링크 목록은 또한 읽기 효율의 손실도 소개합니다).
이 기사의 첫 번째 방법은 다음과 같이 설명 할 수 있습니다. 빈 카드를 그릴 때 다시 그려서 반복적으로 그리십시오.
"카드를 다시 그린 후 카드를 그리십시오"는 나중에 카드를 그릴 가능성이 높아집니다. 이는 분명히 불합리합니다.
한 단계를 최적화 할 수 있습니다. 카드를 그린 후에는 원래 카드가 더 적습니다. (빈 카드를 남기지 않고)
코드는 다음과 같습니다.
코드 사본은 다음과 같습니다.
함수 shuffle_pick_1 (m) // shush // 카드 드로잉 메소드
{
// M 카드를 생성합니다
var arr = 새로운 배열 (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// 한 번에 하나의 카드를 그려 다른 파일에 넣습니다. 배열에서 요소를 추출하고 모든 후속 요소를 하나씩 앞으로 가져 가야하므로 시간이 많이 걸립니다.
var arr2 = 새로운 배열 ();
for (var i = m; i> 0; i-) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (Rnd, 1);
}
반환 ARR2;
}
배열이 크면 중간에 특정 요소를 삭제하면 대기열이 한 걸음 더 나아갈 수 있기 때문에 이것은 매우 문제가됩니다. 이는 매우 시간이 많이 걸리는 동작입니다.
"왜 우리는 그 요소를 삭제합니까?" 빈 카드를 피하는 것입니다.
해당 요소를 삭제하는 것 외에도 빈 카드를 제거하는 다른 방법이 있습니까?
---- 예, 마지막으로 자한 카드를 드로우 위치에 넣어야합니다.
따라서이 아이디어를 다음과 같이 최적화 할 수 있습니다.
코드 사본은 다음과 같습니다.
함수 shuffle_pick (m) // 카드 도면 메소드를 닫아 카드 최적화
{
// M 카드를 생성합니다
var arr = 새로운 배열 (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// 한 번에 하나의 카드를 그려 다른 파일에 넣습니다. 마지막으로 자리 잡은 카드를 열린 좌석에 올려 놓으십시오.
var arr2 = 새로운 배열 ();
for (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
반환 ARR2;
}
카드를 그리는 아이디어 외에도 카드 변경이라는 아이디어도 사용할 수 있습니다.
"Baidu Wenku-Shut Algorithm"은 카드 변경 아이디어를 언급합니다. "두 위치를 무작위로 전환하고 총으로 교환합니다. N이 클수록 무작위에 가까워집니다."
이 접근법은 잘못되었습니다. N이 매우 크지 만 (예 : 10 장의 카드, 10 스위치) "일부 카드는 위치를 전혀 변경하지 않을 가능성이 여전히 높습니다."
이 아이디어를 따르고 약간 조정하십시오. 카드로 I-TH 카드를 변경하고 한 라운드로 변경하십시오.
코드는 다음과 같습니다.
코드 사본은 다음과 같습니다.
함수 shuffle_swap (m) // shush // 카드 변경 방법
{
// M 카드를 생성합니다
var arr = 새로운 배열 (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// I-TH 카드는 좌석을 변경하는 데 사용되며 한 라운드로 변경할 수 있습니다.
for (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
온도 = ARR [rnd];
arr [rnd] = arr [i];
arr [i] = 온도;
}
반환 ARR;
}
카드 그리기 및 교체 아이디어 외에도 카드 삽입 아이디어를 사용할 수 있습니다. 먼저 하나의 카드가 있습니다. 두 번째 카드에는 무작위로 삽입 할 두 가지 위치가 있습니다 (첫 번째 카드 앞이나 뒤에), 세 번째 카드에는 무작위로 삽입 또는 첫 번째 위치에 삽입되거나 삽입 된 세 가지 위치가 있습니다).
코드는 다음과 같습니다.
코드 사본은 다음과 같습니다.
함수 shuffle_insert_1 (m) // 션트 // 카드 삽입 방법
{
// 매번 가장 큰 카드가 임의의 카드 앞에서 생성되어 삽입됩니다. 배열에 요소를 삽입하고 모든 후속 요소를 하나씩 짜야하므로 시간이 많이 걸립니다.
var arr = [0];
for (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
반환 ARR;
}
위의 코드에는 몇 가지 문제가 있습니다. 카드 수가 증가함에 따라 카드를 삽입하기가 점점 더 어려워집니다. 카드를 삽입하면 한 단계 뒤를 따르는 많은 카드가 발생할 수 있기 때문입니다.
물론, 우리는 또한 적절하게 최적화 할 수 있습니다. 먼저 N-1 카드가 있고 N-th 카드가 끝에 배치 된 다음 모든 카드로 위치를 교환합니다.
코드는 다음과 같습니다.
코드 사본은 다음과 같습니다.
함수 shuffle_insert (m) // shush // 카드 삽입 방법의 최적화 된 버전은이 셔플이 균일하다는 수학적 유도로 증명할 수 있습니다.
{
// 매번 가장 큰 카드를 생성하고 임의의 카드로 위치를 교환합니다.
var arr = 새로운 배열 (m);
ARR [0] = 0;
for (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
반환 ARR;
}
좋아, 모든 코드는 다음과 같습니다. 관심있는 학생들은 각자의 실행 효율성과 최종 결과가 이론적으로 무작위인지 확인하기 위해 자신의 기계에서 시도해 볼 수 있습니다.
코드 사본은 다음과 같습니다.
<html>
<헤드>
<meta http-equiv = "content-type"content = "text/html; charset = gb2312">
<title> jk : JavaScript Shuffling 알고리즘 </title>
</head>
<body>
<script type = "text/javaScript">
함수 shuffle_pick_1 (m) // shush // 카드 드로잉 메소드
{
// M 카드를 생성합니다
var arr = 새로운 배열 (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// 한 번에 하나의 카드를 그려 다른 파일에 넣습니다. 배열에서 요소를 추출하고 모든 후속 요소를 하나씩 앞으로 가져 가야하므로 시간이 많이 걸립니다.
var arr2 = 새로운 배열 ();
for (var i = m; i> 0; i-) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (Rnd, 1);
}
반환 ARR2;
}
함수 shuffle_pick (m) // 카드 도면 메소드를 닫아 카드 최적화
{
// M 카드를 생성합니다
var arr = 새로운 배열 (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// 한 번에 하나의 카드를 그려 다른 파일에 넣습니다. 마지막으로 자리 잡은 카드를 열린 좌석에 올려 놓으십시오.
var arr2 = 새로운 배열 ();
for (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
반환 ARR2;
}
함수 shuffle_swap (m) // shush // 카드 변경 방법
{
// M 카드를 생성합니다
var arr = 새로운 배열 (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// I-TH 카드는 좌석을 변경하는 데 사용되며 한 라운드로 변경할 수 있습니다.
for (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
온도 = ARR [rnd];
arr [rnd] = arr [i];
arr [i] = 온도;
}
반환 ARR;
}
함수 shuffle_insert_1 (m) // 션트 // 카드 삽입 방법
{
// 매번 가장 큰 카드가 임의의 카드 앞에서 생성되어 삽입됩니다. 배열에 요소를 삽입하고 모든 후속 요소를 하나씩 짜야하므로 시간이 많이 걸립니다.
var arr = [0];
for (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
반환 ARR;
}
함수 shuffle_insert (m) // shush // 카드 삽입 방법의 최적화 된 버전은이 셔플이 균일하다는 수학적 유도로 증명할 수 있습니다.
{
// 매번 가장 큰 카드를 생성하고 임의의 카드로 위치를 교환합니다.
var arr = 새로운 배열 (m);
ARR [0] = 0;
for (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
반환 ARR;
}
// Alert (Shuffle_Pick (10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
funcNames = [ "Draw Card", "Draw Card Optimization", "Card Change", "Card Insert", "Card Insert Optimization"]]]
m = 10000,
시간 = [];
for (var i = 0; i <funcs.length; i ++) {
var d0 = 새 날짜 ();
함수 [i] (m);
funcNames [i] = (new date () -d0) + '/t' + funcNames [i];
}
alert (funcNames.join ( '/n'));
</스크립트>
</body>
</html>