셔플 링에 JavaScript Array.sort () 메소드를 사용하는 것이 맞습니까?
나는 그의 JavaScript로 누군가를 돕고 코드 내 눈은 다음과 같은 섹션에 매료되었습니다.
function randOrd(){
return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);
내 첫 번째는 : 이봐, 아마도 작동하지 않을 수 있습니다! 나는 몇 가지 무작위로 결과를 제공하는 무작위로 결과를 제공합니다.
그런 다음 웹 검색을 수행하고 거의 맨 위에이 코드가 가장 정교하게 복사 된 기사 를 찾았 습니다 . 꽤 존경받는 사이트와 저자처럼 보였습니다 ...
그러나 내 직감은 잘못되지 않았다. 특히 정렬 알고리즘이 ECMA 표준에 의해 지정되지 않았기 때문에. 다른 정렬 알고리즘으로 인해 다른 생각하지 않은 셔플이 발생한다고 생각합니다. 일부 정렬 알고리즘은 아마도 무한 반복 될 수도 있습니다 ...
하지만 어떻게 생각하세요?
그리고 또 다른 질문으로 ... 이제 어떻게이 셔플 링의 결과가 무작위인지 측정 할 수 있습니까?
업데이트 : 몇 가지 측정을 수행하고 아래 결과를 답변 중 하나로 게시했습니다.
그것은 부분적으로 있기 때문에, 셔플의 내가 가장 좋아하는 방법은 본 적이 없네 입니다 당신이 말한대로 구현 고유의. 특히, Java 또는 .NET에서 정렬하는 표준 라이브러리 (어떤 것이 확실하지 않은지)는 일부 요소 사이에 일관성이없는 비교가 발생하는 경우 종종 감지 할 수 있음을 기억합니다 (예 : 먼저 청구 A < B및 B < C, 그러나 C < A).
또한 실제로 필요한 것보다 더 복잡한 (실행 시간 끝에서) 셔플로납니다.
컬렉션을 "셔플 링"(컬렉션 시작시 처음에는 비어 있음)과 "셔플되지 않은 것"(컬렉션 나머지)으로 분할하는 셔플 알고리즘을 선호합니다. 알고리즘의 각 단계에서 무작위 셔플되지 않은 요소 (첫 번째 요소 일 수 있음)를 선택하고 첫 번째 셔플되지 않은 정신 요소와 교체 한 다음 셔플되지 않은 정신 요소를 처리합니다 (즉, 파티션을 포함해야 함).
이것은 O (n)이며 난수 생성기에 대한 n-1 호출만이 필요합니다. 또한 진정한 셔플을 생성합니다-모든 요소는 원래 위치에 관계없이 1 / n의 확률로 끝납니다 (적당한 RNG 가정). (이 임의의 생성 배를 돌려 준다면 난 수기는 매우 가능성이있는, 두 번 같은 값을 선택하지 않는 가정) 더 있습니다 :) 셔플 버전은 근사 하지만 셔플 버전에 대한 이유를 쉽게 사용할 수 있습니다.
이 땅을 Fisher-Yates shuffle 이라고합니다 .
이 셔플을 한 번 코딩하고 항목을 셔플하는 데 필요한 모든 곳에서 보충하는 것이 가장 좋습니다. 안정성이나 안정성이 필요하지 않습니다. 그것은 단지 몇 줄의 코드입니다 (JavaScript에서는 시도하지 않을 것입니다!)
셔플 링 (셔플 알고리즘 섹션) 에 대한 Wikipedia 기사에서는 랜덤 프로젝션을 정렬하는 방법에 대해 설명합니다. 일반적으로 셔플 링의 잘못된 구현에 대한 섹션을 발견면 가치가 있습니다.
Jon이 이미 이론을 다루고 곧 구현은 다음과 가변합니다.
function shuffle(array) {
var tmp, current, top = array.length;
if(top) while(--top) {
current = Math.floor(Math.random() * (top + 1));
tmp = array[current];
array[current] = array[top];
array[top] = tmp;
}
return array;
}
알고리즘은 O(n)이지만 정렬은 필수 O(n log n)입니다. 원시 sort()함수 와 비교하여 JS 코드 실행의 오버 헤드에 따라 ,이 어레이 크기에 따라 증가해야하는 성능의 현저한 차이 로 이어질 수 있습니다 .
bobobobo 의 답변에 대한 의견 에서 문제의 알고리즘이 (의 구현에 따라) 균등하게 분산 된 확률을 생성하지 않을 확률이 sort()있습니다.
나의 주장은 다음과 c같은 내용 c = n(n-1)/2을 따른다 : 정렬 알고리즘은 수 의 비교 가 필요하다 ( 예 : Bubblesort). 우리의 무작위 비교 함수는 각 비교의 결과를 똑같이 가능하게 만듭니다. 즉 2^c 똑같이 가능한 결과가 있습니다. 이제 각 결과는 n!배열 항목 의 순열 중 하나와 일치하는 경우 일반적인 경우 고른해야 할 수 없습니다. (필요한 실제 비교 수는 입력 배열에 따라 다르지만 어설 션은 여전히 유지되어야 단순화 단순화 된 것입니다.)
Jon이 지적했듯이, sort()난수 생성기가 유한 수의 의사 랜덤 값을 n!순열에 매핑하기 때문에 이것만으로 Fisher-Yates를 선호하는 이유는 없습니다 . 그러나 Fisher-Yates의 결과는 여전히 더 좋습니다.
Math.random()범위 내에서 의사 난수를 생성합니다 [0;1[. JS가 배정 부동 소수점 값을 사용하기 때문에 2^x가능한 52 ≤ x ≤ 63실제 값에 해당합니다 (실제 숫자를 찾기에는 너무 게으르다). 를 사용하여 생성 된 확률은 Math.random()원자 사건의 수가 동일한 크기의 순서이면 제대로 작동하지 않습니다.
Fisher-Yates를 사용할 때 연관 변수는 배열의 크기이며 2^52실제 제한으로 인해 접근 가능 합니다.
임의의 비교 함수를 사용하여 정렬 할 때이 함수는 기본적으로 반환 값이 양수인지 음수인지 만 신경 쓰이는 문제가 없습니다. 그러나 착색 기능이 있습니다. 비교 기능이 작동하기 때문에 2^c가능한 결과는 작동 합니다. 만약 c ~ n log n다음 2^c ~ n^(a·n)여기서 a = const, 아니면 가능성을 만드는 2^c것이 크기로서 (또는 경우) n!, 즉 불균일 한 경우에 발생하는 알고리즘은 여기서 균등 한 순열에 매핑하는 것입니다. 이것이 그것이 영향을 미친다면 저를 넘어선 것입니다.
실제 문제는 정렬 알고리즘이 순열에 균등하게 매핑되는 것이 보장되지 않습니다. Mergesort가 대칭 적 인 것처럼 보이지만 Bubblesort 또는 Quicksort와 같은 것에 대한 추론은 의미합니다.
결론 : sort()머지 소트 를 사용하는 한 코너 케이스 (적어도 코너 케이스 인 경우) 제외하고는를 합리적으로 안전 해야 우리 합니다 2^c ≤ n!.
이 무작위 정렬 결과가 얼마나 무작위인지 측정했습니다.
내 기술은 작은 배열 [1,2,3,4]을 취하고 그것의 모든 (4! = 24) 순열을 만드는 것입니다. 그런 다음 셔플 링 함수를 배열에 여러 번 적용하고 각 순열이 몇 번 생성 계산합니다. 좋은 셔플 링 생성 알고리즘은 모든 순열에 대해 결과를 균등하게 분배하는 반면, 나쁜 셔플은 @ 한 결과를 생성하지 않습니다.
아래 코드를 사용하여 Firefox, Opera, Chrome, IE6 / 7 / 8에서 테스트했습니다.
놀랍게도, 무작위 정렬과 실제 똑같이 셔플은 모두 똑같이 셔플을 만들었습니다. 그래서 (많은 사람들이 제안했듯이) 주요 브라우저는 병합 정렬을 사용하고있는 것입니다. 사용하는 것은 물론 사용 가능합니다.
편집 : 이 테스트는 실제로 또는 그 부족을 측정하지. 내가 게시 한 다른 답변을 참조하십시오.
그러나 성능은 크리스토프가 제공하는 셔플 기능은 확실한 승자였습니다. 작은 4 개 요소 어레이의 경우에도 실제 셔플은 임의 정렬보다 약 2 배 빠 사용!
// Cristoph가 게시 한 셔플 기능.
var shuffle = 함수 (배열) {
var tmp, current, top = array.length;
if (top) while (-top) {
전류 = Math.floor (Math.random () * (상단 + 1));
tmp = 배열 [현재];
배열 [현재] = 배열 [위];
배열 [상단] = tmp;
}
배열 반환;
};
// 랜덤 정렬 함수
var rnd = function () {
반환 Math.round (Math.random ())-0.5;
};
var randSort = 함수 (A) {
return A.sort (rnd);
};
var 순열 = function (A) {
if (A.length == 1) {
반환 [A];
}
다른 {
var perms = [];
(var i = 0; i <A.length; i ++) {
var x = A.slice (i, i + 1);
var xs = A.slice (0, i) .concat (A.slice (i + 1));
var subperms = 순열 (xs);
for (var j = 0; j <subperms.length; j ++) {
perms.push (x.concat (서브 펌 [j]));
}
}
반환 파마;
}
};
var test = 함수 (A, 반복, 기능) {
// 초기화 순열
var 통계 = {};
var perms = 순열 (A);
for (var i in perms) {
통계 [ ""+ perms [i]] = 0;
}
// 여러 번 섞어 통계를 수집
var start = 새 날짜 ();
for (var i = 0; i <반복; i ++) {
var shuffled = func (A);
통계 [ ""+ shuffled] ++;
}
var end = 새 날짜 ();
// 결과 형식
var arr = [];
for (통계의 var i) {
arr.push (i + ""+ 통계 [i]);
}
반환 arr.join ( "\ n") + "\ n \ n하고 시간 :"+ ((끝-시작) / 1000) + "초.";
};
alert ( "무작위 정렬 :"+ 테스트 ([1,2,3,4], 100000, randSort));
alert ( "셔플 :"+ 테스트 ([1,2,3,4], 100000, 셔플));
흥미롭게도 Microsoft 는 pick-random-browser-page에서 동일한 기술 을 사용했습니다 .
그들은 약간의 다른 비교 기능을 사용했습니다.
function RandomSort(a,b) {
return (0.5 - Math.random());
}
나에게 거의 똑같아 보이지만 그렇게 무작위가 아닌 판명인데 ...
그래서 나는 링크 된 기사에서 사용 된 것과 동일한 방법으로 몇 가지 테스트 실행을 다시 수행 한 무작위 정렬 방법으로 결함이있는 결과를 얻었습니다. 새로운 테스트 코드는 다음과 가변적입니다.
function shuffle(arr) {
arr.sort(function(a,b) {
return (0.5 - Math.random());
});
}
function shuffle2(arr) {
arr.sort(function(a,b) {
return (Math.round(Math.random())-0.5);
});
}
function shuffle3(array) {
var tmp, current, top = array.length;
if(top) while(--top) {
current = Math.floor(Math.random() * (top + 1));
tmp = array[current];
array[current] = array[top];
array[top] = tmp;
}
return array;
}
var counts = [
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]
];
var arr;
for (var i=0; i<100000; i++) {
arr = [0,1,2,3,4];
shuffle3(arr);
arr.forEach(function(x, i){ counts[x][i]++;});
}
alert(counts.map(function(a){return a.join(", ");}).join("\n"));
다른 방법으로 셔플을 사용하여 현재 브라우저와 다른 인기있는 브라우저의 편향을 보여주는 간단한 테스트 페이지 를 내 웹 사이트에 배치 했습니다 . 그냥 사용하는 끔찍한 Math.random()-0.5편향, 편향되지 않은 또 다른 '무작위'셔플, 위에서 언급 한 Fisher-Yates 방법을 보여줍니다.
일부 브라우저에서는 '셔플'중에 특정 요소의 위치가 전혀 변경되지 않을 확률이 50 % 정도임을 알 수 있습니다!
참고 : 코드를 다음과 같이 변경하여 Safari에서 @Christoph의 Fisher-Yates 셔플 구현을 약간 더 빠르게 만들 수 있습니다.
function shuffle(array) {
for (var tmp, cur, top=array.length; top--;){
cur = (Math.random() * (top + 1)) << 0;
tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
}
return array;
}
테스트 결과 : http://jsperf.com/optimized-fisher-yates
배포에 대해 까다 롭지 않고 소스 코드가 작기를 원하는 경우에는 괜찮다고 생각합니다.
자바 스크립트 (소스가 지속적으로 전송되는 곳)에서 작은 것은 대역폭 비용에 차이를 만듭니다.
확실히 해킹입니다. 실제로 무한 루프 알고리즘은 가능성이 없습니다. 객체를 정렬하는 경우 coords 배열을 반복하고 다음과 같은 작업을 수행 할 수 있습니다.
for (var i = 0; i < coords.length; i++)
coords[i].sortValue = Math.random();
coords.sort(useSortValue)
function useSortValue(a, b)
{
return a.sortValue - b.sortValue;
}
(그런 다음 다시 반복하여 sortValue를 제거하십시오)
그래도 여전히 해킹입니다. 멋지게하고 싶다면 힘들게해야 해요 :)
4 년이 지났지 만 어떤 정렬 알고리즘을 사용하든 무작위 비교기 방법이 올바르게 배포되지 않는다는 점을 지적하고 싶습니다.
증명:
n요소 배열의 경우 정확히n!순열이 있습니다 (예 : 가능한 셔플).- 셔플 중 모든 비교는 두 세트의 순열 중에서 선택합니다. 무작위 비교기의 경우 각 세트를 선택할 확률이 1/2입니다.
- 따라서 각 순열 p에 대해 순열 p로 끝날 확률은 분모가 2 ^ k 인 분수 (일부 k의 경우)입니다. 이는 이러한 분수의 합이기 때문입니다 (예 : 1/8 + 1/16 = 3/16). ).
- n = 3 인 경우 6 개의 동일 순열이 있습니다. 따라서 각 순열의 확률은 1/6입니다. 1/6은 분모가 2의 거듭 제곱 인 분수로 표현할 수 없습니다.
- 따라서 동전 던지기 정렬은 셔플을 공정하게 분배하지 않습니다.
올바르게 배포 될 수있는 유일한 크기는 n = 0,1,2입니다.
연습으로 n = 3에 대한 다양한 정렬 알고리즘의 결정 트리를 그려보십시오.
증명에 차이가 있습니다. 정렬 알고리즘이 비교기의 일관성에 의존하고 일관성이없는 비교기로 제한되지 않은 런타임이있는 경우 무한한 확률 합계를 가질 수 있으며, 이는 다음과 같은 경우에도 1/6까지 더할 수 있습니다. 합계의 모든 분모는 2의 거듭 제곱입니다. 하나를 찾으십시오.
또한 비교기가 어느 하나의 답을 줄 수있는 고정 된 기회를 가지고 있다면 (예 : (Math.random() < P)*2 - 1상수에 대해 P) 위의 증명이 유지됩니다. 대신 비교기가 이전 답변을 기반으로 확률을 변경하면 공정한 결과를 생성 할 수 있습니다. 주어진 분류 알고리즘에 대해 그러한 비교기를 찾는 것은 연구 논문이 될 수 있습니다.
D3를 사용하는 경우 내장 셔플 기능이 있습니다 (Fisher-Yates 사용).
var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);
마이크가 이에 대해 자세히 설명합니다.
http://bost.ocks.org/mike/shuffle/
다음은 단일 배열을 사용하는 접근 방식입니다.
기본 논리는 다음과 같습니다.
암호:
for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);
Array.sort()함수를 사용하여 배열을 섞을 수 있습니까 – 예.
결과가 충분히 무작위입니까 – 아니오.
다음 코드 스 니펫을 고려하십시오.
var array = ["a", "b", "c", "d", "e"];
var stats = {};
array.forEach(function(v) {
stats[v] = Array(array.length).fill(0);
});
//stats = {
// a: [0, 0, 0, ...]
// b: [0, 0, 0, ...]
// c: [0, 0, 0, ...]
// ...
// ...
//}
var i, clone;
for (i = 0; i < 100; i++) {
clone = array.slice(0);
clone.sort(function() {
return Math.random() - 0.5;
});
clone.forEach(function(v, i) {
stats[v][i]++;
});
}
Object.keys(stats).forEach(function(v, i) {
console.log(v + ": [" + stats[v].join(", ") + "]");
})샘플 출력 :
a [29, 38, 20, 6, 7]
b [29, 33, 22, 11, 5]
c [17, 14, 32, 17, 20]
d [16, 9, 17, 35, 23]
e [ 9, 6, 9, 31, 45]
이상적으로는 개수가 균등하게 분산되어야합니다 (위의 예에서는 모든 개수가 약 20 개 여야 함). 하지만 그렇지 않습니다. 분명히 분포는 브라우저에 의해 구현되는 정렬 알고리즘과 정렬을 위해 배열 항목을 반복하는 방법에 따라 다릅니다.
이 기사에서 더 많은 통찰력을 제공 합니다 .
Array.sort ()를 사용하여 배열을 섞으면 안됩니다.
그것은 잘못된 것이 아닙니다.
.sort ()에 전달하는 함수 는 일반적으로 다음과 같습니다.
함수 sortingFunc (first, second)
{
// 예:
첫 번째-두 번째 반환;
}
sortingFunc의 작업은 다음을 반환하는 것입니다.
- 첫 번째가 두 번째 이전이면 음수
- 첫 번째가 두 번째 다음이어야하는 경우 양수
- 완전히 같으면 0
위의 정렬 기능은 항목을 정렬합니다.
-'s와 + 's를 당신이 가지고있는 것과 같이 무작위로 반환하면, 당신은 무작위 순서를 얻습니다.
MySQL에서와 같이 :
SELECT * from table ORDER BY rand ()
'IT' 카테고리의 다른 글
| 명명 된 파이프는 무엇입니까? (0) | 2020.07.09 |
|---|---|
| 기본 Vim 색상 구성표를 설정하는 방법 (0) | 2020.07.09 |
| C #은 JavaScript의 encodeURIComponent ()와 동등합니까? (0) | 2020.07.08 |
| 각도 양식 필드를 유효하지 않은 수동으로 설정해야합니까? (0) | 2020.07.08 |
| Spring 3 RequestMapping : 경로 값 제공 (0) | 2020.07.08 |