자바스크립트 배열 셔플 무작위 섞는 방법 javascript array shuffle

 

 

안녕하세요?

 

오늘은 자바스크립트에서 가장 많이 쓰이는 배열에 대해 알아볼 건데요.

 

그중에서도 배열의 항목을 무작위로 섞는 방법을 알아보겠습니다.

 

일명 array.shuffle 함수를 만들어 보겠습니다.

 

 

1. Array.sort() 함수 사용

let arr = [1, 2, 3];

일단 arr 배열이 위와 같이 숫자 1,2,3으로 세팅하겠습니다.

 

자바스크립트 Array 객체에는 sort() 함수가 있습니다.

 

기본적인 문구는 아래처럼 compareFunction을 두어 어떻게 순서를 결정할 것인지에 대한 함수를 넣어주는데요.

arr.sort([compareFunction])

compareFunction의 예는 다음과 같습니다.

 

function compare(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

위 코드를 보시면 -1, 1, 0을 리턴하는 함수입니다.

 

즉, Array.sort() 함수는 -1, 1, 0에 따라 두 값을 바꿀지 말지 결정한다고 볼 수 있습니다.

 

만약 Array.sort() 함수에 compareFunction을 비워두면 그냥 ASCII 값의 우선순위에 따라 결정합니다.

 

문자열일 경우에는 괜찮으나 숫자일 경우 정렬이 제대로 안됩니다.

 

그럼, 우리는 배열을 셔플 할 때 즉, 배열을 무작위로 섞을 때 어떻게 Array.sort() 함수를 이용할까요?

 

그건 바로 Math.random() 함수를 이용하는 겁니다.

 

Math.random() 함수는 난수를 0에서 1 미만의 값으로 리턴합니다.

 

그러면 우리가 Array.sort()에 필요한 건 -1, 1, 0인데요. 여기서 사실 0은 필요 없죠. 0이면 정렬 안 한다는 얘기니까요?

 

결론적으로 Array.sort() 함수에서 필요한 compareFunction은 -1, 1 중에 하나만 리턴하면 됩니다.

 

정확하게 말하면 compareFunction 함수는 -1이나 1일 필요 없이 그냥 음수나 양수중에 하나만 리턴하면 되는 겁니다.

 

그럼 Math.random() 이 음수 또는 양수의 값을 가지려면 어떻게 해야 할까요?

 

방법은 다음과 같습니다.

 

Math.random() - 0.5

 

Math.random() 이 0에서 1 사이의 값이기 때문에 0.5를 빼면 무조건 양수이거나 음수가 나오겠죠?

 

그럼 shuffle 코드를 만들어 보겠습니다.

 

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

간단하죠?

 

이제 실행해 볼까요?

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

let arr = [1, 2, 3];

shuffle(arr);
console.log(arr);

 

정렬이 아주 잘 되고 있네요.

 

그러면 Math.random() 함수가 얼마나 일정하게 난수를 뒤죽박죽 만드는지 테스트해볼까요?

 

먼저 위의 arr 배열을 무작위로 섞는다면 그 경우의 수는 몇 가지일까요?

 

3*2*1 = 6가지입니다.

  '123'
  '132'
  '213'
  '231'
  '321'
  '312'

위와 같은 경우의 수가 나오겠죠.

 

그러면 shuffle 함수를 여러 번 실행시켜서 그 분포도를 알아보겠습니다.

 

function shuffle(array) {
    array.sort(() => Math.random() - 0.5);
  }
  
  // 6가지 경우의 수
  let count = {
    '123': 0,
    '132': 0,
    '213': 0,
    '231': 0,
    '321': 0,
    '312': 0
  };
  
  for (let i = 0; i < 1000000; i++) {
    let array = [1, 2, 3];
    shuffle(array);
    count[array.join('')]++;
  }
  
  // 6가지 경우의 수 숫자 출력
  for (let key in count) {
    console.log(`${key}: ${count[key]}`);
  }

위 코드를 보시면 6가지 경우의 수를 count라는 객체로 만들어 놨고,

 

for 문에 의해 1백만 번 루프를 돌려서 셔플을 해볼 예정입니다.

 

그리고, 각각의 경우의 수의 카운트는 array.join('') 함수와 count ["321"]++처럼 그 경우의 수의 숫자를 하나씩 증가하는 로직을 썼습니다.

 

그리고 마지막으로 count 객체에서 각각의 숫자를 출력하는 console.log 함수입니다.

 

실행 결과를 볼까요?

 

위의 스크린숏을 보시면 편차가 아주 심합니다.

 

Math.random() 함수는 정말 난수 발생 함수로는 써먹지 못하는 걸까요?

 

맞습니다. 난수 발생 함수로는 되도록이면 쓰지 않는 게 좋습니다.

 

난수 발생 함수 중에 권장하는 게 뭐가 있냐면 바로 WebCrypto라는 게 있는데 이게 최근에 각광받는 난수 발생 패키지입니다.

 

NodeJS나 Javascript에 기본 포함되어 있어 그냥 다음과 같이 사용하시면 됩니다.

 

// nodejs
const Crypto = require("crypto").webcrypto;

// html
const Crypto = window.crypto;

그리고 Crypto 패키지로 난수를 얻는 함수는 바로 getRandomValues()입니다.

Crypto.getRandomValues(randomNumberArrary);

getRandomValues()에는 난수를 리턴할 Array 배열이 들어가야 되는데요.

 

들어갈 수 있는 배열은 다음과 같습니다.

 

Int8Array, Int16Array, Int32Array, Uint8Array, Uint16Array, Uint32Array 타입입니다.

 

즉, 비트의 자릿수와 음수 양수인지를 구분하는 건데요.

 

우리의 목적은 음수와 양수중 하나만 나오면 되니까, Int8Array를 이용해 보겠습니다.

 

const Crypto = require("crypto").webcrypto;

let arr = new Int8Array(3);

Crypto.getRandomValues(arr);

console.log(arr);

Int8Array(3)이라서 배열 아이템이 3개가 나왔네요.

 

음수 아니면 양수가 아주 잘 나오고 있습니다.

 

그럼 이걸 이용해서 Shuffle 함수를 다시 만들어 볼까요?

 

const Crypto = require("crypto").webcrypto;

let cryptoArr = new Int8Array(1);

function shuffle(array) {
  array.sort(() => Crypto.getRandomValues(cryptoArr));
  //   console.log(cryptoArr);
}

// 6가지 경우의 수
let count = {
  123: 0,
  132: 0,
  213: 0,
  231: 0,
  321: 0,
  312: 0,
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join("")]++;
}

// 6가지 경우의 수 숫자 출력
for (let key in count) {
  console.log(`${key}: ${count[key]}`);
}

 

맨 처음 만든 코드에 Math.random()을 Crypto.getRandomValues()로 바꿨습니다.

 

그럼 실행 결과를 볼까요?

 

실행 결과를 보니까 Math.random()과 별반 차이가 없습니다.

 

그럼 뭐가 문제일까요?

 

바로 Array.sort() 함수를 이용한 Shuffle이 문제라고 추정할 수 있겠네요.

 

그래서 소개해 드릴 셔플 방법이 바로 이쪽 방면에서 유명한 Fisher–Yates shuffle입니다.

 

Fisher-Yates Shuffle은 다음과 같은 로직으로 셔플 하는 겁니다.

 

 

1. 1~n의 숫자를 씁니다.
2. 지워지지 않은 숫자 중 random number k를 고릅니다.
3. 남은 숫자의 개수를 세고, 지워지지 않은 숫자 k를 지우고, 그 숫자를 별도의 list에 씁니다.
4. 모든 숫자가 지워질 때까지 2번을 반복합니다.
5. 3번에서 쓴 별도의 list가 최종 random permutation 결과가 됩니다.

 

뭔가 어려운데요.

 

위키에 보면 펜슬 페이퍼 방법이 나와 있습니다.

 

 

한번 읽어 보면 좋습니다.

 

그리고 Fisher-Yates shuffle을 비주얼적으로 잘 보여주는 블로그가 있는데 아래 링크 눌러서 보시면 그림으로 쉽게 이해할 수 있을 겁니다.

https://bost.ocks.org/mike/shuffle/

Fisher–Yates Shuffle

 

 

Fisher-Yates 셔플로 구현한 자바스크립트 루틴은 다음과 같습니다.

 

function shuffleES5(array) {
    for (var i = array.length - 1; i > 0; i--) {
        // j라고 무작위 인덱스 값을 설정하고
        var j = Math.floor(Math.random() * (i + 1));
        
        // temp를 만들어서 임시로 원본값을 저장합니다.
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

function shuffleES6(array) {
    for (let i = array.length - 1; i > 0; i--) {
      let j = Math.floor(Math.random() * (i + 1));
      [array[i], array[j]] = [array[j], array[i]];
    }
  }

ES5와 ES6 문법에 따라 두 개의 버전을 준비했습니다.

 

최신 버전은 ES6를 쓰시면 됩니다.

 

그럼 셔플 분석을 해볼까요?

 

function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
      let j = Math.floor(Math.random() * (i + 1));
      [array[i], array[j]] = [array[j], array[i]];
    }
  }
  
  // counts of appearances for all possible permutations
  let count = {
    '123': 0,
    '132': 0,
    '213': 0,
    '231': 0,
    '321': 0,
    '312': 0
  };
  
  for (let i = 0; i < 1000000; i++) {
    let array = [1, 2, 3];
    shuffle(array);
    count[array.join('')]++;
  }
  
  // show counts of all possible permutations
  for (let key in count) {
    console.log(`${key}: ${count[key]}`);
  }

실행결과는 다음과 같습니다.

 

 

와우! 기가 막힙니다.

 

Math.random() 함수를 이용해서도 정말 기가 막히게 셔플 했네요.

 

앞으로 이 코드만 써야겠네요.

 

다음 코드는 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(arr)처럼 호출하면 됩니다.

 

일단 이 함수가 퍼포먼스 즉, 아주 빠르다고 합니다.

 

그럼 Fisher-Yates 셔플 코드를 Math.random() 이 아닌 crypto.getRandomNumbers()로 구현한 코드를 짜 볼까요?

 

const Crypto = require("crypto").webcrypto;

function shuffleCrypto(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;
}

실행 결과도 아주 좋습니다.

 

이제 자바스크립트 배열 셔플은 앞으로 완벽하게 사용할 수 있을 거 같네요.