Attuazione shuffle celesti jukebox

Question

Come si potrebbero implementare la riproduzione casuale per la "Celeste Jukebox"?

Più precisamente, ad ogni tempo t, la restituzione di un'uniforme di numeri casuali tra 0..n(t), tale che non vi siano ripete in tutta la sequenza, con n() aumentando con il passare del tempo.

Per un esempio concreto, supponiamo che una tariffa flat con il servizio di musica che consente di riprodurre qualsiasi brano in catalogo da 0 a base di numero di indice.Ogni tanto, le nuove canzoni sono aggiunti per aumentare la gamma di numeri indice.L'obiettivo è quello di giocare una nuova canzone ogni volta che (supponendo che non duplicati nel catalogo).

la soluzione ideale sarebbe fattibile su hardware esistente - come faccio a calzascarpe un elenco di sei milioni di brani 8MB DRAM?Allo stesso modo, la canzone alta conte aggrava O(n) selezione tempi.

-- Per un LCG, generatore, dato che una parte esaurito la LCG a 0..N₀, che può essere tradotta in un diverso LCG a 0..N₁ (dove N1 > N0), capace di non ripetere l'esausto sequenza.
-- Controllo se una canzone in particolare è già stata giocata sembra crescere rapidamente di mano, anche se questo potrebbe essere l'unico modo ?C'è un'efficiente struttura di dati per questo?

Answer 1

Il modo in cui mi piace fare questo tipo di non-ripetizione di selezione casuale è una lista, e ogni volta che seleziono un elemento casuale tra [0-N), Ho rimuoverlo dalla lista.Nel tuo caso, come nuovi elementi vengono aggiunti al catalogo, potrebbe anche essere aggiunti al non-ancora-elenco selezionato.Una volta che si arriva alla fine, semplicemente ricaricare tutte le canzoni torna all'elenco.

EDIT:

Se si prende v3 suggerimento in considerazione, questo può essere fatto praticamente O(1) il tempo dopo la O(N) inizializzazione passo.Garantisce di non ripetere la selezione casuale.

Ecco il riassunto:

1. Aggiungono i primi elementi di una lista
2. Pick indice i a random (dal set di [0,N))
3. Rimuovere l'elemento di indice i
4. Sostituire il buco i con il Nth voce (o null se i == Nth) e decremento N
5. Per i nuovi elementi, è sufficiente aggiungere alla fine dell'elenco e di incremento N come necessario
6. Se avete mai avuto a giocare attraverso tutti i brani (di cui ho il dubbio se si dispone di 6M canzoni), quindi aggiungere tutte le canzoni che torna alla lista, schiuma, risciacquare e ripetere.

Dal momento che si sta cercando di affrontare, piuttosto grande, set, mi sento di raccomandare l'uso di un DB.Una semplice tabella con fondamentalmente due campi: id e "pointer"(dove "pointer"è quello che ti dice la canzone di giocare che potrebbe essere un GUID, Nome, ecc, a seconda di come si desidera farlo).Hanno un indice id e si dovrebbe ottenere molto discrete prestazioni con persistenza tra applicazione è in esecuzione.

EDIT per 8MB limite:

Umm, questo fa un po ' più difficile...In 8 MB, è possibile memorizzare un massimo di ~2M voci utilizzando le chiavi a 32 bit.

Quindi quello che mi sento di raccomandare è quello di pre-selezionare il prossimo 2M voci.Se l'utente gioca attraverso 2M canzoni di una vita, accidenti!Per pre-selezionare, fare una pre-init passo utilizzando l'algoritmo precedente.Una modifica che vorrei fare è che quando si aggiungono nuovi brani, lancia i dadi e vedere se si desidera in modo casuale aggiungere un brano per il mix.Se sì, allora scegli un casuale indice e sostituirlo con il nuovo brano di indice.

Answer 2

Con un limite di 8 MB per 6 milioni di canzoni, non c'è chiaramente spazio per memorizzare anche un singolo numero intero a 32 bit per ogni canzone. A meno che non siete pronti a memorizzare l'elenco su disco (in questo caso, vedi sotto).

Se siete pronti a cadere il requisito che i nuovi elementi sono immediatamente aggiunti al riordino, è possibile generare una LCG sopra l'attuale serie di canzoni, poi, quando che è esaurita, generare una nuova LCG sopra solo le canzoni che erano aggiunto da quando hai iniziato. Sciacquare e ripetere fino a quando non hai più eventuali nuove canzoni. È inoltre possibile utilizzare questo algoritmo piuttosto freddo che genera una permutazione unguessable in una gamma arbitraria senza memorizzarlo.

Se siete disposti a rilassare il requisito di 8 MB di RAM per 6 milioni di canzoni, o di andare a disco (ad esempio, la mappatura della memoria), si potrebbe generare la sequenza dal 1..n all'inizio, rimescolalo con Fisher-Yates, e ogni volta che viene aggiunto un nuovo brano, selezionare un elemento casuale dalla sezione so-far-unplayed, inserire il nuovo ID lì, e aggiungere l'ID originale alla fine della lista.

Se non si cura molto di efficienza computazionale, è possibile memorizzare una bitmap di tutti i brani, e ripetutamente raccogliere gli ID in modo uniforme a caso fino a trovare quello che non hai ancora giocato. Questo sarebbe prendere 6 milioni di tentativi per trovare l'ultima canzone (in media), che è ancora dannatamente veloce su una CPU moderna.

Answer 3

Mentre la soluzione di Erich è probabilmente meglio per il vostro caso specifico uso, controllare se una canzone è già stato svolto è molto veloce (O ammortizzato (1)) con una struttura hash-based, come ad esempio un set in Python o un hashset<int> in C ++.

Answer 4

Si potrebbe semplicemente generare la sequenza di numeri da 1 a n e poi shuffle utilizzando uno shuffle Fisher-Yates. In questo modo si può garantire che la sequenza non si ripeterà, a prescindere dal n.

Answer 5

Si potrebbe utilizzare una lista collegata all'interno di un array: Per costruire la playlist iniziale, utilizzare un array contenente un qualcosa di simile a questo:

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

Anche tenere una 'testa' e puntatore 'freelist';

popolarlo in 2 passaggi:
    1. compilare arr con tutte le canzoni nel catalogo, al fine 0..n.
    2. iterare casuale attraverso tutti gli indici, compilando il next puntatore;

Soppressione di brani suonati è O (1):

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

L'inserimento di nuovi brani è O (1) anche:. Scegliere un indice di array a caso, e patch un nuovo nodo

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;