다음과 같은 배열이 있습니다.
var arr1 = ["a", "b", "c", "d"];
어떻게 랜덤화/셔플할 수 있나요?
질문자 :Ali
다음과 같은 배열이 있습니다.
var arr1 = ["a", "b", "c", "d"];
어떻게 랜덤화/셔플할 수 있나요?
사실상의 편향되지 않은 셔플 알고리즘은 Fisher-Yates(일명 Knuth) 셔플입니다.
https://github.com/coolaj86/knuth-shuffle 참조
여기에서 훌륭한 시각화를 볼 수 있습니다(및 여기에 링크된 원본 게시물).
function shuffle(array) { let currentIndex = array.length, randomIndex; // While there remain elements to shuffle... while (currentIndex != 0) { // Pick a remaining element... randomIndex = Math.floor(Math.random() * currentIndex); currentIndex--; // And swap it with the current element. [array[currentIndex], array[randomIndex]] = [ array[randomIndex], array[currentIndex]]; } return array; } // Used like so var arr = [2, 11, 37, 42]; shuffle(arr); console.log(arr);
사용된 알고리즘에 대한 추가 정보입니다.
다음은 Fisher-Yates의 최적화된 버전인 Durstenfeld shuffle 의 JavaScript 구현입니다.
/* Randomize array in-place using Durstenfeld shuffle algorithm */ function shuffleArray(array) { for (var i = array.length - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var temp = array[i]; array[i] = array[j]; array[j] = temp; } }
각 원래 배열 요소에 대해 임의의 요소를 선택하고 카드 더미에서 무작위로 선택하는 것과 같이 다음 뽑기에서 제외합니다.
이 영리한 제외는 선택한 요소를 현재 요소와 교환한 다음 나머지에서 다음 임의 요소를 선택하여 최적의 효율성을 위해 역방향으로 반복하여 임의 선택을 단순화하고(항상 0에서 시작할 수 있음) 최종 요소를 건너뜁니다.
알고리즘 런타임은 O(n)
입니다. 먼저, 원래의 배열은 수정과의 복사본을 만들고 싶어하지 않는, 그래서 만약 셔플이 자리에서 이루어집니다 참고 .slice(0)
.
새로운 ES6에서는 한 번에 두 개의 변수를 할당할 수 있습니다. 이것은 한 줄의 코드로 할 수 있기 때문에 두 변수의 값을 바꾸고 싶을 때 특히 편리합니다. 다음은 이 기능을 사용하는 동일한 기능의 더 짧은 형태입니다.
function shuffleArray(array) { for (let i = array.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [array[i], array[j]] = [array[j], array[i]]; } }
경고!
이 알고리즘 은 비효율적 이고 편향 이 강하기 때문에 사용 하지 않는 것이 좋습니다 . 의견을 참조하십시오. 아이디어는 그리 드물지 않기 때문에 향후 참조를 위해 여기에 남겨둡니다.
[1,2,3,4,5,6].sort( () => .5 - Math.random() );
이 https://javascript.info/array-methods#shuffle-an-array 튜토리얼은 차이점을 간단하게 설명합니다.
map과 sort로 쉽게 할 수 있습니다.
let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}] let shuffled = unshuffled .map((value) => ({ value, sort: Math.random() })) .sort((a, b) => a.sort - b.sort) .map(({ value }) => value)
다형성 배열을 섞을 수 있으며 정렬은 Math.random만큼 무작위로 대부분의 목적에 충분합니다.
요소는 각 반복마다 다시 생성되지 않는 일관된 키에 대해 정렬되고 각 비교는 동일한 분포에서 가져오기 때문에 Math.random 분포에서 임의성이 아닌 것은 모두 취소됩니다.
속도
시간 복잡도는 퀵 정렬과 동일하게 O(N log N)입니다. 공간 복잡도는 O(N)입니다. 이것은 Fischer Yates 셔플만큼 효율적이지는 않지만 제 생각에는 코드가 훨씬 더 짧고 기능적입니다. 어레이가 큰 경우 Fischer Yates를 사용해야 합니다. 수백 개의 항목이 있는 작은 배열이 있는 경우 이 작업을 수행할 수 있습니다.
Array의 프로토타입으로 사용할 수 있습니다(또는 사용해야 합니다):
크리스토프에서:
Array.prototype.shuffle = function() { var i = this.length, j, temp; if ( i == 0 ) return this; while ( --i ) { j = Math.floor( Math.random() * ( i + 1 ) ); temp = this[i]; this[i] = this[j]; this[j] = temp; } return this; }
underscore.js 라이브러리를 사용합니다. _.shuffle()
메서드가 좋습니다. 다음은 메서드의 예입니다.
var _ = require("underscore"); var arr = [1,2,3,4,5,6]; // Testing _.shuffle var testShuffle = function () { var indexOne = 0; var stObj = { '0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5 }; for (var i = 0; i < 1000; i++) { arr = _.shuffle(arr); indexOne = _.indexOf(arr, 1); stObj[indexOne] ++; } console.log(stObj); }; testShuffle();
새로운!
더 짧고 아마도 *더 빠른 Fisher-Yates 셔플 알고리즘
function fy(a,b,c,d){//array,placeholder,placeholder,placeholder c=a.length;while(c)b=Math.random()*(--c+1)|0,d=a[c],a[c]=a[b],a[b]=d }
스크립트 크기(함수 이름으로 fy 포함): 90bytes
데모 http://jsfiddle.net/vvpoma8w/
*크롬을 제외한 모든 브라우저에서 더 빠를 것입니다.
질문이 있으면 질문하십시오.
편집하다
네 더 빠릅니다
성능: http://jsperf.com/fyshuffle
가장 많이 투표된 기능을 사용합니다.
편집 초과 계산이 있었고(-c+1 필요 없음) 아무도 눈치채지 못했습니다.
더 짧고(4bytes) & 더 빠릅니다(테스트해 보세요!).
function fy(a,b,c,d){//array,placeholder,placeholder,placeholder c=a.length;while(c)b=Math.random()*c--|0,d=a[c],a[c]=a[b],a[b]=d }
다른 곳에서 캐싱 var rnd=Math.random
한 다음 rnd()
를 사용하면 큰 배열에서 성능이 약간 향상됩니다.
http://jsfiddle.net/vvpoma8w/2/
읽을 수 있는 버전 (원본 버전을 사용하십시오. 이것은 더 느리고 vars는 클로저 & ";"처럼 쓸모가 없습니다. 코드 자체도 더 짧습니다... 아마도 이것을 읽으십시오 Javascript 코드를 '축소'하는 방법 , btw 당신은 할 수 없습니다 위와 같은 자바스크립트 축소기에서 다음 코드를 압축합니다.)
function fisherYates( array ){ var count = array.length, randomnumber, temp; while( count ){ randomnumber = Math.random() * count-- | 0; temp = array[count]; array[count] = array[randomnumber]; array[randomnumber] = temp } }
제자리에 배열 섞기
function shuffleArr (array){ for (var i = array.length - 1; i > 0; i--) { var rand = Math.floor(Math.random() * (i + 1)); [array[i], array[rand]] = [array[rand], array[i]] } }
ES6 순수, 반복
const getShuffledArr = arr => { const newArr = arr.slice() for (let i = newArr.length - 1; i > 0; i--) { const rand = Math.floor(Math.random() * (i + 1)); [newArr[i], newArr[rand]] = [newArr[rand], newArr[i]]; } return newArr };
신뢰성 및 성능 테스트
이 페이지의 일부 솔루션은 신뢰할 수 없습니다(배열을 부분적으로만 무작위화함). 다른 솔루션은 훨씬 덜 효율적입니다. testShuffleArrayFun
(아래 참조)을 사용하여 안정성과 성능에 대해 배열 셔플링 기능을 테스트할 수 있습니다.
function testShuffleArrayFun(getShuffledArrayFun){ const arr = [0,1,2,3,4,5,6,7,8,9] var countArr = arr.map(el=>{ return arr.map( el=> 0 ) }) // For each possible position in the shuffledArr and for // each possible value, we'll create a counter. const t0 = performance.now() const n = 1000000 for (var i=0 ; i<n ; i++){ // We'll call getShuffledArrayFun n times. // And for each iteration, we'll increment the counter. var shuffledArr = getShuffledArrayFun(arr) shuffledArr.forEach( (value,key)=>{countArr[key][value]++} ) } const t1 = performance.now() console.log(`Count Values in position`) console.table(countArr) const frequencyArr = countArr.map( positionArr => ( positionArr.map( count => count/n ) )) console.log("Frequency of value in position") console.table(frequencyArr) console.log(`total time: ${t1-t0}`) }
재미를 위한 다른 솔루션.
ES6 순수, 재귀
const getShuffledArr = arr => { if (arr.length === 1) {return arr}; const rand = Math.floor(Math.random() * arr.length); return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))]; };
array.map을 사용하는 ES6 Pure
function getShuffledArr (arr){ return [...arr].map( (_, i, arrCopy) => { var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) ); [arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]] return arrCopy[i] }) }
array.reduce를 사용하는 ES6 Pure
function getShuffledArr (arr){ return arr.reduce( (newArr, _, i) => { var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) ); [newArr[rand], newArr[i]] = [newArr[i], newArr[rand]] return newArr }, [...arr] ) }
편집: 이 답변은 올바르지 않습니다.
의견 및 https://stackoverflow.com/a/18650169/28234를 참조하십시오 . 아이디어가 드물지 않기 때문에 참조용으로 여기에 남겨둡니다.
작은 배열에 대한 매우 간단한 방법은 다음과 같습니다.
const someArray = [1, 2, 3, 4, 5]; someArray.sort(() => Math.random() - 0.5);
그다지 효율적이지 않을 수 있지만 작은 배열의 경우 잘 작동합니다. 이것이 얼마나 무작위적인지(또는 그렇지 않은지), 사용 사례에 맞는지 여부를 확인할 수 있는 예입니다.
const resultsEl = document.querySelector('#results'); const buttonEl = document.querySelector('#trigger'); const generateArrayAndRandomize = () => { const someArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; someArray.sort(() => Math.random() - 0.5); return someArray; }; const renderResultsToDom = (results, el) => { el.innerHTML = results.join(' '); }; buttonEl.addEventListener('click', () => renderResultsToDom(generateArrayAndRandomize(), resultsEl));
<h1>Randomize!</h1> <button id="trigger">Generate</button> <p id="results">0 1 2 3 4 5 6 7 8 9</p>
@Laurens Holsts 답변에 추가. 50% 압축된 것입니다.
function shuffleArray(d) { for (var c = d.length - 1; c > 0; c--) { var b = Math.floor(Math.random() * (c + 1)); var a = d[c]; d[c] = d[b]; d[b] = a; } return d };
ES2015에서는 다음을 사용할 수 있습니다.
Array.prototype.shuffle = function() { let m = this.length, i; while (m) { i = (Math.random() * m--) >>> 0; [this[m], this[i]] = [this[i], this[m]] } return this; }
용법:
[1, 2, 3, 4, 5, 6, 7].shuffle();
이 질문의 복제본에 대한 "저자가 삭제함" 답변에 이 변형이 있는 것을 발견했습니다. 이미 많은 찬성표가있는 다른 답변과 달리 이것은 다음과 같습니다.
shuffle
아닌 shuffled
이름)다음은 사용 중인 jsfiddle 입니다.
Array.prototype.shuffled = function() { return this.map(function(n){ return [Math.random(), n] }) .sort().map(function(n){ return n[1] }); }
//one line solution shuffle = (array) => array.sort(() => Math.random() - 0.5); //Demo let arr = [1, 2, 3]; shuffle(arr); alert(arr);
https://javascript.info/task/shuffle
Math.random() - 0.5
는 양수 또는 음수일 수 있는 난수이므로 정렬 기능은 요소를 무작위로 재정렬합니다.
var shuffle = function(array) { temp = []; originalLength = array.length; for (var i = 0; i < originalLength; i++) { temp.push(array.splice(Math.floor(Math.random()*array.length),1)); } return temp; };
재귀 솔루션:
function shuffle(a,b){ return a.length==0?b:function(c){ return shuffle(a,(b||[]).concat(c)); }(a.splice(Math.floor(Math.random()*a.length),1)); };
JavaScript에서 Fisher-Yates 셔플. 두 가지 유틸리티 함수(swap 및 randInt)를 사용하면 여기의 다른 답변과 비교하여 알고리즘이 명확해지기 때문에 여기에 게시합니다.
function swap(arr, i, j) { // swaps two elements of an array in place var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function randInt(max) { // returns random integer between 0 and max-1 inclusive. return Math.floor(Math.random()*max); } function shuffle(arr) { // For each slot in the array (starting at the end), // pick an element randomly from the unplaced elements and // place it in the slot, exchanging places with the // element in the slot. for(var slot = arr.length - 1; slot > 0; slot--){ var element = randInt(slot+1); swap(arr, element, slot); } }
가장 쉬운 방법 은 다음과 같습니다.
function shuffle(array) { return array.sort(() => Math.random() - 0.5); }
추가 예를 들어 여기에서 확인할 수 있습니다.
ES6 기능을 사용하는 최신 짧은 인라인 솔루션:
['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);
(교육 목적으로)
벤치마크
먼저 결과를 확인한 다음 아래 shuffle
접속이 느리다
splice
또는 shift
를 사용하는 솔루션은 매우 느릴 것입니다. 이는 배열의 크기를 늘릴 때 특히 두드러집니다. 순진한 알고리즘에서 우리는 -
t
rand
위치 i
가져옵니다.t[i]
t
splice
위치 i
느린 효과를 과장하기 위해 백만 개의 요소로 구성된 배열에 대해 설명합니다. 다음 스크립트는 거의 30초 -
const shuffle = t => Array.from(sample(t, t.length)) function* sample(t, n) { let r = Array.from(t) while (n > 0 && r.length) { const i = rand(r.length) // 1 yield r[i] // 2 r.splice(i, 1) // 3 n = n - 1 } } const rand = n => Math.floor(Math.random() * n) function swap (t, i, j) { let q = t[i] t[i] = t[j] t[j] = q return t } const size = 1e6 const bigarray = Array.from(Array(size), (_,i) => i) console.time("shuffle via splice") const result = shuffle(bigarray) console.timeEnd("shuffle via splice") document.body.textContent = JSON.stringify(result, null, 2)
body::before { content: "1 million elements via splice"; font-weight: bold; display: block; }
팝은 빠르다
트릭은하지 않는 것입니다 splice
대신 슈퍼 효율적으로 사용하는 pop
. 이렇게 하려면 일반적인 splice
호출 대신 -
i
t[i]
를 마지막 요소인 t[t.length - 1]
t.pop()
이제 100밀리초 이내에 백만 개의 요소를 shuffle
수 있습니다.
const shuffle = t => Array.from(sample(t, t.length)) function* sample(t, n) { let r = Array.from(t) while (n > 0 && r.length) { const i = rand(r.length) // 1 swap(r, i, r.length - 1) // 2 yield r.pop() // 3 n = n - 1 } } const rand = n => Math.floor(Math.random() * n) function swap (t, i, j) { let q = t[i] t[i] = t[j] t[j] = q return t } const size = 1e6 const bigarray = Array.from(Array(size), (_,i) => i) console.time("shuffle via pop") const result = shuffle(bigarray) console.timeEnd("shuffle via pop") document.body.textContent = JSON.stringify(result, null, 2)
body::before { content: "1 million elements via pop"; font-weight: bold; display: block; }
더 빠르게
위의 두 가지 shuffle
구현은 새로운 출력 배열을 생성합니다. 입력 배열은 수정되지 않습니다. 이것은 내가 선호하는 작업 방식이지만 제자리에서 섞으면 속도를 훨씬 더 높일 수 있습니다.
다음은 shuffle
10 밀리 초 미만의 백만 요소를 -
function shuffle (t) { let last = t.length let n while (last > 0) { n = rand(last) swap(t, n, --last) } } const rand = n => Math.floor(Math.random() * n) function swap (t, i, j) { let q = t[i] t[i] = t[j] t[j] = q return t } const size = 1e6 const bigarray = Array.from(Array(size), (_,i) => i) console.time("shuffle in place") shuffle(bigarray) console.timeEnd("shuffle in place") document.body.textContent = JSON.stringify(bigarray, null, 2)
body::before { content: "1 million elements in place"; font-weight: bold; display: block; }
우선, 여기 에서 자바스크립트의 다양한 정렬 방법을 시각적으로 비교해보세요.
두 번째로, 위의 링크를 빠르게 살펴보면 random order
정렬이 다른 방법에 비해 상대적으로 잘 수행되는 것처럼 보이지만 아래와 같이 구현하기가 매우 쉽고 빠릅니다.
function shuffle(array) { var random = array.map(Math.random); array.sort(function(a, b) { return random[array.indexOf(a)] - random[array.indexOf(b)]; }); }
편집 : @gregers가 지적한 것처럼 비교 함수는 인덱스가 아닌 값으로 호출되므로 indexOf
를 사용해야 합니다. indexOf
가 O(n) 시간에 실행되므로 코드가 더 큰 배열에 덜 적합하다는 점에 유의하십시오.
다른 모든 답변은 빠르지만 암호화 수준 무작위화에 적합하지 않은 Math.random()을 기반으로 합니다.
아래 코드는 잘 알려진 Fisher-Yates
알고리즘을 사용하는 동시에 암호화 수준의 무작위화를 위해 Web Cryptography API
를 사용합니다.
var d = [1,2,3,4,5,6,7,8,9,10]; function shuffle(a) { var x, t, r = new Uint32Array(1); for (var i = 0, c = a.length - 1, m = a.length; i < c; i++, m--) { crypto.getRandomValues(r); x = Math.floor(r / 65536 / 65536 * m) + i; t = a [i], a [i] = a [x], a [x] = t; } return a; } console.log(shuffle(d));
업데이트 : 여기에서는 작은 크기의 배열에서 잘 작동 하는 비교적 간단하고 ( 복잡한 관점 에서가 아니라) 짧은 알고리즘을 제안하고 있지만, 거대한 배열을 처리할 때 고전적인 Durstenfeld 알고리즘보다 확실히 더 많은 비용이 들 것입니다. 이 질문에 대한 최고의 답변 중 하나인 Durstenfeld 를 찾을 수 있습니다.
원래 답변:
셔플 기능이 소스 배열 을 변경하는 것을 원하지 않으면 이를 로컬 변수에 복사한 다음 간단한 셔플 논리로 나머지를 수행할 수 있습니다.
function shuffle(array) { var result = [], source = array.concat([]); while (source.length) { let index = Math.floor(Math.random() * source.length); result.push(source[index]); source.splice(index, 1); } return result; }
셔플링 논리 : 임의의 인덱스를 선택한 다음 해당 요소를 결과 배열에 추가하고 원본 배열 복사본 에서 삭제합니다. 소스 배열이 비어 있을 때까지 이 작업을 반복합니다.
그리고 당신이 정말로 그것을 짧게 원한다면, 여기까지 내가 얻을 수 있는 것이 있습니다:
function shuffle(array) { var result = [], source = array.concat([]); while (source.length) { let index = Math.floor(Math.random() * source.length); result.push(source.splice(index, 1)[0]); } return result; }
다음을 사용하여 쉽게 할 수 있습니다.
// array var fruits = ["Banana", "Orange", "Apple", "Mango"]; // random fruits.sort(function(a, b){return 0.5 - Math.random()}); // out console.log(fruits);
JavaScript Sorting Arrays 에서 참조하십시오.
Fisher-Yates 셔플 알고리즘 및 ES6 사용:
// Original array let array = ['a', 'b', 'c', 'd']; // Create a copy of the original array to be randomized let shuffle = [...array]; // Defining function returning random value from i to N const getRandomValue = (i, N) => Math.floor(Math.random() * (N - i) + i); // Shuffle a pair of two elements at random position j shuffle.forEach( (elem, i, arr, j = getRandomValue(i, arr.length)) => [arr[i], arr[j]] = [arr[j], arr[i]] ); console.log(shuffle); // ['d', 'a', 'b', 'c']
우리는 2019년에도 여전히 배열을 섞고 있습니다. 그래서 여기에 제 접근 방식이 적용됩니다. 이는 제가 보기에 깔끔하고 빠른 것 같습니다.
const src = [...'abcdefg']; const shuffle = arr => [...arr].reduceRight((res,_,__,s) => (res.push(s.splice(0|Math.random()*s.length,1)[0]), res),[]); console.log(shuffle(src));
.as-console-wrapper {min-height: 100%}
엄격 모드를 사용하는 Fisher-Yates의 또 다른 구현:
function shuffleArray(a) { "use strict"; var i, t, j; for (i = a.length - 1; i > 0; i -= 1) { t = a[i]; j = Math.floor(Math.random() * (i + 1)); a[i] = a[j]; a[j] = t; } return a; }
원래 어레이를 수정하지 않는 CoolAJ86의 답변 을 간단하게 수정:
/** * Returns a new array whose contents are a shuffled copy of the original array. * @param {Array} The items to shuffle. * https://stackoverflow.com/a/2450976/1673761 * https://stackoverflow.com/a/44071316/1673761 */ const shuffle = (array) => { let currentIndex = array.length; let temporaryValue; let randomIndex; const newArray = array.slice(); // While there remains elements to shuffle... while (currentIndex) { randomIndex = Math.floor(Math.random() * currentIndex); currentIndex -= 1; // Swap it with the current element. temporaryValue = newArray[currentIndex]; newArray[currentIndex] = newArray[randomIndex]; newArray[randomIndex] = temporaryValue; } return newArray; };
배열 무작위화
var arr = ['apple','cat','Adam','123','Zorro','petunia']; var n = arr.length; var tempArr = []; for ( var i = 0; i < n-1; i++ ) { // The following line removes one random element from arr // and pushes it onto tempArr tempArr.push(arr.splice(Math.floor(Math.random()*arr.length),1)[0]); } // Push the remaining item onto tempArr tempArr.push(arr[0]); arr=tempArr;
가장 짧은 arrayShuffle
함수
function arrayShuffle(o) { for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x); return o; }
이미 조언된 구현이 많이 있지만 forEach 루프를 사용하여 더 짧고 쉽게 만들 수 있으므로 배열 길이 계산에 대해 걱정할 필요가 없으며 임시 변수 사용을 안전하게 피할 수 있습니다.
var myArr = ["a", "b", "c", "d"]; myArr.forEach((val, key) => { randomIndex = Math.ceil(Math.random()*(key + 1)); myArr[key] = myArr[randomIndex]; myArr[randomIndex] = val; }); // see the values console.log('Shuffled Array: ', myArr)
출처 : http:www.stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array
로컬에서 일부 파일을 무시하도록 git을 구성하려면 어떻게 해야 합니까? (0) | 2022.02.17 |
---|---|
jQuery에서 div 요소 만들기 [중복] (0) | 2022.02.17 |
JavaScript에서 setInterval 호출 중지 (0) | 2022.02.17 |
특정 라인에 대한 eslint 규칙 끄기 (0) | 2022.02.17 |
"이전 형제" 선택자가 있습니까? (0) | 2022.02.15 |