JavaScript 연구 노트: arrays_javascript 기술의 무작위 정렬

추천 도서: JavaScript 학습 노트 배열 합계 방법

JavaScript 학습 노트 배열 추가, 삭제, 수정 및 확인

JavaScript는 배열 항목을 재정렬하는 sort() 및 reverse() 메서드를 제공합니다. 그러나 이 두 가지 방법은 포커 게임의 무작위 셔플링과 같은 실제 비즈니스 요구 사항을 충족하지 못하는 경우가 많습니다.

이번 글에서는 위 예제의 효과를 얻는 방법과 함께 배열의 무작위 정렬에 대한 몇 가지 관련 지식을 배워보겠습니다.

인터넷에서 배열의 무작위 정렬 관련 정보를 보다가 Math.random()을 보게 되었습니다. 브라우저 컨트롤러를 열고 다음을 입력하세요:

Math.random()

그림에서 볼 수 있듯이 Math.random()은 0과 1 사이의 난수를 얻습니다. 우리 모두 알고 있듯이 sort()는 함수를 매개변수로 호출할 수 있습니다. 함수가 -1 값을 반환하면 배열의 항목 a가 항목 b보다 먼저 순위가 매겨진다는 의미입니다. 이런 방식으로 Math.random()에 의해 무작위로 생성된 숫자를 0.5와 비교하는 무작위 함수를 작성할 수 있습니다. .5보다 크면 -1(a가 b보다 순위가 높음)을 반환하고, 그렇지 않으면 1을 반환합니다(b가 a보다 앞에 위치함):

function randomSort(a, b) {
return Math.random() > 0.5 ? -1 : 1;
}

예제 보기:

var arr = [1,2,3,4,5,6,7,8,9];
arr.sort(randomSort);

이런 방법으로 기사 시작 부분의 예시 효과를 얻을 수 있습니다.

이전 방법은 배열의 무작위 정렬을 달성했지만 항상 새 배열로 전송되는 각 요소의 위치가 무작위가 아닌 것처럼 느껴집니다. 이전 예제와 마찬가지로 배열 arr에서 값 1을 갖는 요소는 원래 키 값 0을 갖습니다. 무작위 정렬 후 키 값 1이 0-8일 확률은 동일합니다. 그런 다음 sort() 메서드가 순차적으로 비교하기 때문에 여기서는 감소합니다.

이 현상을 해결하기 위해 다음 재귀적 방법을 사용하여 처리할 수 있습니다.

function randomSort(arr, newArr) {
// 如果原数组arr的length值等于1时，原数组只有一个值，其键值为0
// 同时将这个值push到新数组newArr中
if(arr.length == 1) {
newArr.push(arr[0]);
return newArr; // 相当于递归退出
}
// 在原数组length基础上取出一个随机数
var random = Math.ceil(Math.random() * arr.length) - 1;
// 将原数组中的随机一个值push到新数组newArr中
newArr.push(arr[random]);
// 对应删除原数组arr的对应数组项
arr.splice(random,1);
return randomSort(arr, newArr);
}

이 경우 다음과 같이 사용할 수 있습니다.

for (var i = 0; i < 10; i++) {
var arr=[1,2,3,4,5,6,7,8,9];
var newArr=[];
randomSort(arr,newArr);
console.log(newArr);
}

출력 결과:

randomSort(arr, newArr) 함수를 실행한 후 원래 배열 arr이 지워집니다.

이 방법을 사용하여 기사 시작 부분의 셔플링 예제를 수행하는 경우 ResetPic() 함수에서 pukePic 배열을 재설정해야 합니다.

위의 두 가지 방법 외에도 @Traveller는 DIV.IO에서 "배열 요소에 대한 무작위 정렬 알고리즘 구현"이라는 기사를 공유했습니다. 이 기사에서는 배열 항목의 무작위 정렬을 위한 세 가지 구현 방법을 제공합니다.

배열 정렬 방법을 사용하여 배열 요소를 무작위로 정렬

Array.prototype.shuffle = function(n) {
var len = this.length ,
num = n ? Math.min(n,len) : len,
arr = this.slice(0);
arr.sort(function(a,b){
return Math.random()-0.5;
});
return arr.slice(0,num-1);
}

배열의 요소를 무작위로 교체

lib = {}
lib.range = function(min,max) {
return min + Math.floor(Math.random()*(max-min+1));
}

Array.prototype.shuffle = function(n) {
var len = this.length,
num = n ? Math.min(n,len) : len,
arr = this.slice(0),
temp,
index;
for (var i=0;i<len;i++){
index = lib.range(i,len-1);
temp = arr[i];
arr[i] = arr[index];
arr[index]=temp;
}
return arr.slice(0,num);
}

원본 배열에서 요소를 무작위로 추출하여 새 배열에 추가

lib = {}
lib.range = function(min,max) {
return min+Math.floor(Math.random()*(max-min+1));
}
Array.prototype.shuffle = function(n) {
var len = this.length, 
num = n ? Math.min(n,len) : len,
arr = this.slice(0),
result=[],
index;
for (var i=0;i<num;i++){
index = lib.range(0,len-1-i);
// 或者 result.concat(arr.splice(index,1))
result.push(arr.splice(index,1)[0]);
}
return result
}

셔플링 알고리즘

배열의 무작위 정렬의 기본 원리는 셔플링 알고리즘(Fisher-Yates shuffle)입니다.

은 유한집합의 순서를 교란하는 알고리즘입니다

원칙

배열(셔플)을 정의합니다. 길이(length)는 원래 배열의 길이(arr)입니다.
0을 인덱스로 가져옴(초기 0) 임의 값 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr[index]
index++ ; index = length -1이 될 때까지 2단계를 반복하세요
0부터 length-1까지 shuffled하는 할당과정이고, 새로 추가된 값은 arr[index]가 된다. shuffled[index]의 값은 할당된 요소들 중 랜덤한 값 shuffled[rand]이다. 값이 중복되므로 shuffled[rand]는 새로 추가된 값 arr[index]

와 같습니다.

underscore.js의 셔플 메서드

function random(min, max) {
if (max == null) {
max = min;
min = 0;
}
return min + Math.floor(Math.random() * (max - min + 1));
};
function shuffle(arr) {
var length = arr.length,
shuffled = Array(length);
for (var index = 0, rand; index < length; index++) {
rand = random(0, index);
if (rand !== index) shuffled[index] = shuffled[rand];
shuffled[rand] = arr[index];
}
return shuffled;
}

실용적 적용:

var arr = [1,2,3,4,5,6,7,8,9];
for (var i = 0; i < 10; i++){
console.log(shuffle(arr));
}

Chrome에서 출력되는 결과는 다음과 같습니다.

마찬가지로 셔플링 알고리즘을 사용하여 기사 시작 부분의 예를 완성하세요.

더 간단하고 이해하기 쉬운 작성 방법도 있습니다.

function shuffle(arr) {
var i, 
j,
temp;
for (i = arr.length - 1; i > 0; i--) {
j = Math.floor(Math.random() * (i + 1));
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
};

요약

이 글은 주로 배열의 무작위 정렬에 대한 관련 정보를 요약하고 수집합니다. 물론, 시장에는 유사한 기능을 달성할 수 있는 방법이 많이 있습니다. 여기에는 더 좋은 방법이 있으면 댓글로 공유해 주세요.

위 내용은 편집자가 소개한 자바스크립트 학습 노트의 배열 무작위 정렬에 대한 소개입니다. 도움이 되셨으면 좋겠습니다!