배열 셔플을 코딩하면서 배운 것들

나는 memory game을 만들고 있었다. 답변 배열을 섞을 필요가 있었습니다. 그리고 나는 다음과 같이했습니다.

let arr = ["The Correct Answer", "Wrong Answer", "Wrong Answer"],
    result = [];

// pick random value, check that it's not picked before, push it to the result array
function randomUniqueValue(arr, result) {
  let index = Math.floor(Math.random() * arr.length);

  !result.includes(arr[index]) 
      ? result.push(arr[index])
      : randomUniqueValue(arr, result);
}

for (let i=0; i < arr.length; i++) {
  randomUniqueValue(arr, result);
}
console.log(result);

좋아, 이건 틀렸어! 성능에 관심이 있고 해야 한다면 이 기능은 적합하지 않습니다.

왜요?

먼저 이 기능이 무엇을 하는지 논의해 봅시다. 무작위index를 선언하고 주어진 배열 내부의 값을 확인합니다. 값이 이전에 선택되지 않고 결과 배열로 푸시되지 않은 경우 결과 배열로 푸시합니다. 이전에 선택한 경우 반복합니다.

하지만, 무엇이 잘못되었나요?

성능, 내 친구. 이게 문제 야!
결과 배열이 점점 커지는 동안 선택되지 않은 값이 점점 작아집니다. 따라서 선택되지 않은 값을 점점 더 낮출 가능성이 있습니다. 이는 이미 선택한 값을 반복해서 선택하는 것을 의미합니다. 함수가 계속해서 반복되어야 합니다. 빅오 표기!

해결책

천재 통계학자인 Ronald Fisher와 Frank Yates는 다음과 같은 알고리즘을 고안했습니다.
매번 임의의 인덱스를 선택하고 고유성을 확인하는 데 시간을 낭비하는 이유는 무엇입니까?!
우리는 배열의 각 값에 대해 직접 무작위로 만들어야 합니다!

let arr = [1,2,3,4,5,6,7,8,9];

function shuffle() {
  let m = arr.length, i, t;

  while (m) {
    i = Math.floor(Math.random() * m--);

    t = arr[m];
    arr[m] = arr[i];
    arr[i] = t;
  }

  return arr;
}

이렇게 하면 선택한 인덱스의 고유성에 대해 신경 쓰지 않습니다. 임의 인덱스를 선택하고 배열의 마지막 값으로 바꿉니다. 그런 다음 마지막 이전 값, 이전 값 등으로 동일합니다.

차이를 측정하는 방법

각 함수를 코드 플레이그라운드에 복사하고 console.log 프로그램이 선택한 횟수를 기록합니다index.

이것이 내가 얻은 것입니다.



콘솔을 보면 배열을 완전히 무작위화하는 데 배열 길이인 while 루프를 9번만 반복하면 됩니다.

그러나 나쁜 기능은 나에게 다음을 제공했습니다.



9 길이 배열을 무작위화하기 위해 37번 반복! 어레이 길이가 커지는 동안 숫자의 증가를 상상해보십시오!

결론

귀하의 기능은 버그 없이 실행되고 작업을 수행할 수 있지만 내부 성능은 저하됩니다. 따라서 배열 셔플링과 같은 작업을 수행하기 위해 최상의 알고리즘을 검색하는 것이 항상 좋은 생각입니다.

그러나 이것이 알고리즘을 직접 작성하려고 시도해서는 안 된다는 의미는 아닙니다! 항상 버그를 해결하려고 노력해야 합니다! 이것이 당신이 배우고 성장하는 방법입니다! 그리고 알고리즘을 직접 작성했을 때 최고를 찾아 비교하십시오. 그러면 무엇이 잘못되었고 앞으로 이를 피하는 방법을 알려줄 것입니다.

Read more about Fisher-Yates shuffle