알고리즘 - shuffleDeck

배열 무작위 섞기

1.배열 요소를 섞기 위한 임의의 난수를 생성한다.
2.임의의 난수를 기준으로 정렬을 실행한다.
3.정렬된 요소만 뽑아서 새로운 배열로 나타낸다.

const shuffleDeck = function (deck) {
  // 랜덤한 숫자, 요소의 배열 제작
  return deck.map(ele => ([Math.random(),ele]))
  .sort((a,b) => a[0]-b[0]) // 정렬(매번 같은 위치X)
  .map(result => result[1]) // 최종 정렬된 요소만 가져오기
}
//  → shuffleDeck EXTRA CREDIT: not PASS

　위에서 만든 알고리즘은 Math.random 함수를 이용해 '난수'를 만들게 되는데, 이때 만들어진 난수는 의사난수(Pseudo-Random, 유사난수)일 수 있다. 난수 / 유사난수

---

Math.random
이 함수는 현재 시간 millisecond를 이용해서 난수를 생성하기 때문에 컴퓨터 시간을 난수를 생성했던 시간으로 되돌릴 경우 이전과 똑같은 난수를 생성하게 된다.

　선형적인 시간복잡도를 갖고있다. 배열이 N만큼 늘어났을 때 "비편향"을 유지해야한다면 어떤 알고리즘을 활용해야하는가?

객체에 넣어서 하는 방법으로도 해결할 수 있다.(underscore의 shuffle 방식)

const shuffleDeck = function (deck) {
  return deck.map(ele=> ({ sort : Math.random(), value:ele}))
  .sort((a,b)=> a.sort - b.sort)
  .map(result => result.value)
}

[javascript] 배열(array)보다 객체(object)를 써야하는 경우, 배열을 객체로 바꾸는 방법

시간복잡도 O(N)을 가지는 Fisher-Yates(Knuth) 셔플을 이용하면 더 단축시킬 수 있다.

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

---

성능테스트를 위한 performance.now()과 console.time()

함수 초반 t0, 함수 끝 t1 를 넣어서 total time을 구하면 된다.

console.time 을 이용해도 직관적으로 볼 수 있다. 참조

performance.now() - MDN
performance.now()와 Data.now()의 차이점
모던자바스크립트
참조