Shuffling algorithm

Posted at 2008/04/04 20:19 // in Programming // by Daniel

Shuffling에 관한 글을 찾아보았다.

http://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Shuffling 알고리즘이란 1~n까지의 숫자가 있을 때 이를 섞어서 임의의 순서로 만드는 것이다.

MP3 플레이어의 shuffle과 같은 것을 구현할 때 쓴다.

가장 간단하게는 배열을 두고

i가 i~n까지 돌 동안

1. 1~n까지의 랜덤한 숫자를 얻은 다음,

2. 이전에 선택됐던 번호인가를 알아보고 그렇다면 다시 아니면 다시 1번 반복

3. 중복되지 않은 값을 찾으면 i번째에 해당 값을 넣는다

이러면 어떤 경우엔 무한반복하게 된다. 1,2번에서 계속 걸릴 수 있기 때문에


이 때문에 나온 알고리즘이 몇가지 있다는데 두가지 방법이 유명하다고 한다.

하나는 O(N*logN)의 시간이 들고 하나는 O(N)이 든다.

첫번째는 일련번호가 있는 카드들을 두고 랜덤 숫자를 붙이고 나서 그걸 숫자로 정렬하면 카드번호가 섞이게 되는 것을 이용한다. 정렬하는 알고리즘의 효율성에 따라 효율이 정해지는데 가장 빠른 정렬방식이 O(N*logN)이다.

둘째는 Fisher-Yates shuffle 이라고 불리는데

1. 일단 배열(카드들)에 1~N까지 숫자를 순서대로 넣는다. (A[i] = i)

2. 1~N 사이의 랜덤 숫자를 뽑고 이를 k라 하면 k번째 숫자와 N번째 숫자를 바꿔치기한다. ( swap(A[k],A[n]) )

3. N을 하나 빼서 N-1로 만든다.

4. N이 2보다 작아질때까지 2와 3을 반복한다.


이걸 보면서 생각한건데,

예전에  MP3 플레이어를 만들 때 shuffle 기능 구현에 고민했던 게 생각난다.

그때는 단순히 어떤 수열을 만들면 1~N까지 반복되지 않는 랜덤 숫자를 만들 수 있지 않나 했었지만 찾지를 못했다.

위의 두 방법을 쓰면 쉽게 구현이 가능한데..

그러나 문제가 있다. 메모리를 N에 비례해서 쓴다는 것. 그리고 N이 많이 크면 초기에 배열을 만드는 데 시간이 많이 들 것이다.

실제 MP3 플레이어는 분명히 램 크기가 엄청 작을 것이다. 이를 어떻게 해결할까?

어쩌면 그냥 호스트(PC)가 만들어주는 플레이리스트만 쓸 지도 모르겠다.

아니면 shuffle로 하지 말고 단순히 random 만 쓰는 수도 있겠다(이러면 예전에 들었던 곡이 또 나올 때도 있을 것이다)

시간문제는, 만일 이런 방법을 쓸 경우 N이 크다면 초기 리스트 만드는 데 딜레이가 생길텐데 처음 10곡 정도는 임의로 생성한 리스트를 사용해서 초기 셋업이 일단 된 것처럼 시작시키고 내부적으로 나머지 리스트를 완성하면 어떨까한다.

그러면 사용자 입장에선 기다리는 시간이 없을 것이다.

크리에이티브 커먼즈 라이센스
Creative Commons License