천상의 주크박스에서 셔플 구현

StackOverflow https://stackoverflow.com/questions/860100

문제

"Celestial Jukebox"에 대한 셔플을 어떻게 구현합니까?

보다 정확하게는 각 시간 t에서 0..n(t) 사이의 균일한 난수를 반환하여 전체 시퀀스에 반복이 없도록 하고 n()은 시간이 지남에 따라 증가합니다.

구체적인 예로, 카탈로그에 있는 모든 노래를 0 기반 인덱스 번호로 재생할 수 있는 정액 음악 서비스를 가정해 보겠습니다.종종 색인 번호의 범위를 늘리는 새로운 노래가 추가됩니다.목표는 매번 새로운 노래를 재생하는 것입니다(카탈로그에 중복된 노래가 없다고 가정).

이상적인 솔루션은 기존 하드웨어에서 실행 가능합니다. 8MB DRAM에 600만 곡의 노래 목록을 어떻게 표시할 수 있을까요?마찬가지로, 높은 노래 개수는 O(n)개의 선택 타이밍을 악화시킵니다.

-- LCG 발전기의 경우 0..N에 부분적으로 소진된 LCG가 있는 경우0, 0..N의 다른 LCG로 변환될 수 있습니까?1 (여기서 N1 > N0), 이는 소진된 시퀀스를 반복하지 않습니다.
- 특정 노래가 이미 재생되었는지 확인하는 것이 유일한 방법일 수도 있지만 빠르게 감당할 수 없을 정도로 커져가는 것 같습니다.이에 대한 효율적인 데이터 구조가 있습니까?

도움이 되었습니까?

해결책

내가 그런 종류의 비 반복 무작위 선택을 좋아하는 방식은 목록을 갖는 것입니다. [0-N), 나는 그 목록에서 그것을 제거합니다. 귀하의 경우, 새 항목이 카탈로그에 추가되면, 아직 선택되지 않은 목록에 추가됩니다. 끝에 도착하면 모든 노래를 목록으로 다시로드하십시오.

편집하다:

V3의 제안을 고려하면 기본적으로 수행 할 수 있습니다. O(1) 다음 시간 O(N) 초기화 단계. 비 반복 무작위 선택을 보장합니다.

다음은 요약입니다.

  1. 초기 항목을 목록에 추가하십시오
  2. 인덱스 선택 i 무작위로 (세트에서 [0,N))
  3. 인덱스에서 항목을 제거하십시오 i
  4. 구멍을 교체하십시오 i 이랑 Nth 항목 (또는 널 if i == Nth) 및 감소 N
  5. 새 항목의 경우 목록의 끝까지 간단히 추가하고 증분하십시오. N 필요에 따라
  6. 모든 노래를 연주하게된다면 (6m 곡이 있는지 의심하는 경우) 모든 노래를 목록에 다시 추가하고, 거품, 린스 및 반복하십시오.

다소 큰 세트를 다루려고 노력하기 때문에 DB의 사용을 권장합니다. 기본적으로 두 개의 필드가있는 간단한 테이블 : id 그리고 "pointer" (어디 "pointer"당신이 그것을 원하는 방법에 따라 안내, 파일 이름 등이 될 수있는 노래를 연주 할 노래를 말하는 것입니다. id 그리고 응용 프로그램 실행 사이의 지속성으로 매우 괜찮은 성능을 얻어야합니다.

8MB 제한 편집 :

음, 이것은 조금 더 어려워집니다 ... 8MB에서는 32 비트 키를 사용하여 최대 ~ 2m 항목을 저장할 수 있습니다.

그래서 내가 추천 할 것은 다음 2m 항목을 사전 선택하는 것입니다. 사용자가 평생 2m 곡을 통해 플레이한다면, 젠장! 사전 선택하려면 위의 알고리즘을 사용하여 사전 인센트 단계를 수행하십시오. 내가 할 수있는 한 가지 변화는 새로운 노래를 추가 할 때 주사위를 굴려서 그 노래를 무작위로 믹스에 추가 할 것인지 확인한다는 것입니다. 그렇다면 임의의 색인을 선택하여 새 노래의 색인으로 바꾸십시오.

다른 팁

6 백만 곡의 8MB 제한으로 각 곡마다 32 비트 정수를 저장할 공간이 분명하지 않습니다. 디스크에 목록을 저장할 준비가되어 있지 않으면 (이 경우 아래 참조).

새 항목을 셔플에 즉시 추가해야한다는 요구 사항을 삭제할 준비가되면 현재 노래 세트를 통해 LCG를 생성 할 수 있습니다. 그런 다음 소진되면 새 LCG를 생성하면 추가 된 노래만으로도 새 LCG를 생성합니다. 시작했다. 더 이상 새로운 노래가 없을 때까지 헹구고 반복하십시오. 당신은 또한 사용할 수 있습니다 이 멋진 알고리즘 이는 저장하지 않고 임의의 범위에서 가질 수없는 순열을 생성합니다.

6 백만 곡의 8MB RAM의 요구 사항을 완화하거나 디스크로 이동 (예 : 메모리 매핑으로)을 준비 할 준비가 되었다면 처음에 1..N에서 시퀀스를 생성하여 Fisher-와 섞을 수 있습니다. 예이츠, 새 노래가 추가 될 때마다 소위 미개화 된 섹션에서 임의의 요소를 선택하고 새 ID를 삽입 한 다음 원래 ID를 목록 끝에 추가하십시오.

계산 효율성에 크게 신경 쓰지 않으면 모든 노래의 비트 맵을 저장하고 아직 재생하지 않은 것을 찾을 때까지 무작위로 ID를 반복적으로 선택할 수 있습니다. 이것은 마지막 노래 (평균)를 찾는 데 6 백만 개의 시도가 필요합니다.

Erich의 솔루션은 특정 사용 사례에 대해 더 나을 것입니다. 노래가 이미 재생되었는지 확인하는 것이 매우 빠르십시오 (Amortized O (1)) set 파이썬에서 또는 a hashset<int> C ++에서.

간단히 1부터 n까지의 숫자 시퀀스를 생성한 다음 Fisher-Yates 셔플을 사용하여 셔플할 수 있습니다.이렇게 하면 n에 관계없이 시퀀스가 ​​반복되지 않도록 보장할 수 있습니다.

배열 내부에서 링크 된 목록을 사용할 수 있습니다. 초기 재생 목록을 작성하려면 다음과 같은 기능이 포함 된 배열을 사용하십시오.

 struct playlistNode{
  songLocator* song;
  playlistNode  *next;
};
struct playlistNode arr[N];

또한 '머리'와 '프리리스트'포인터를 유지하십시오.

2 개의 패스로 채우십시오.
1. 카탈로그의 모든 노래를 순서 0..N으로 채우십시오.
2. 모든 지수를 무작위로 반복하여 next 바늘;

재생 된 노래의 삭제는 O (1)입니다.

head=cur->next;
cur->song=NULL;
freelist->next = freelist;
cur->next=freelist;
freelist=cur;

새 노래의 삽입은 O (1)도 마찬가지입니다. 배열 인덱스를 무작위로 선택하고 새 노드를 패치하십시오.

node = freelist;
freelist=freelist->next;
do {
i=rand(N);   
} while (!arr[i].song);  //make sure you didn't hit a played node
node->next = arr[i].next;
arr[i].next=node;
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top