Ho bisogno di un algoritmo per il prelievo di un utente.
Gli utenti sono identificati dalla lettera {A, B, C, ...} e sono classificati in base al numero {1, 2, 3, ...}. Il grado è il grado di probabilità da scegliere, quindi un utente di livello 2 ha il doppio di probabilità di essere scelto su un utente di livello 1, e il grado 4 è quattro volte più probabile, ecc.
Quindi diciamo che quattro utenti sono {A, B, C, D}, con rank {1, 1, 5, 2} rispettivamente. Una tabella utente potrebbe memorizzare il rango:
USER RANK
A 1
B 1
C 5
D 2
Come faccio a scegliere un utente in base al grado?
La mia prima idea per un algoritmo è quella di sommare tutti i ranghi 1 + 1 + 5 + 2 per ottenere una somma di 9. Quindi assegnare i subrange da 1 a 9 a ciascun utente, dove subrange size è user rank. Quindi A ha range [1, 1], B ha range [2, 2], C ha range [3, 7] (5 possibilità a causa del rank 5), e D ha range [8, 9]. La tabella diventa questa:
USER RANK RANGE
A 1 [1, 1]
B 1 [2, 2]
C 5 [3, 7]
D 2 [8, 9]
Quindi calcola un valore casuale da 1 a 9 e trova l'utente il cui intervallo contiene quel valore. Quindi se il valore casuale è 4, l'utente C viene scelto perché 4 rientra nell'intervallo [3, 7].
Ciò raggiunge l'equità in base al grado. Se ripeti il prelievo a caso in questo modo, in media, gli utenti verranno scelti in modo equo e nessun utente sarà affamato.
Tuttavia, sembra sciatto, perché per aggiungere o rimuovere utenti, devo ricalcolare tutti gli intervalli. Qui viene rimosso l'utente C (ricalcolo intervallo di utente D):
USER RANK RANGE
A 1 [1, 1]
B 1 [2, 2]
D 2 [3, 4]
E qui sta cambiando l'utente A per avere il grado 2 (ricalcolare l'intervallo di B e D):
USER RANK RANGE
A 2 [1, 2]
B 1 [3, 3]
D 2 [4, 5]
Qual è il miglior algoritmo per scegliere un utente? Sicuramente il ricalcolo degli intervalli per ogni utente aggiunto, eliminato o aggiornato è subottimale. Esiste una funzione o un algoritmo ben noto che può aiutare?
AGGIORNAMENTO: @rwong mi ha fatto pensare a raggruppare le persone in base al grado, quindi a selezionare il rango invece di selezionare l'utente. Con una persona in ogni livello, trasformi gli intervalli a forma casuale in intervalli di crescita molto lineari (un punto è una possibilità da scegliere):
Rank 1: *
Rank 2: * *
Rank 3: * * *
Rank 4: * * * *
Rank 5: * * * * *
Funziona alla perfezione per una sola persona per grado, ma cade a pezzi quando ci sono molte persone al primo posto, dove le loro possibilità dovrebbero aumentare del numero di persone all'interno di quel grado, possibilmente superando le possibilità di ranghi più alti.
Ora siamo tornati a una forma irregolare e dobbiamo sceglierne. Un amico mi ha indirizzato a Campione di rifiuto . Questa sembra essere un'ottima soluzione in cui si sceglie una coordinata xey casuale, vediamo se rientra nella forma e, in caso affermativo, ora selezioniamo il rank. Quindi scegli una persona a caso all'interno di quel grado.
Per mostrare questa soluzione, ecco la forma con più persone all'interno di ogni classifica. Per il grado 2, ci sono 5 persone, quindi questo è 2 x 5 = 10 possibilità:
User count Rank Chances(graph) Chances(number)
5 1 * * * * * 5
5 2 * * * * * * * * * * 10
1 3 * * * 3
0 4 0
1 5 * * * * * 5
L'algoritmo consiste nel selezionare una riga casuale (come selezionare una coordinata x) e scegliere un valore casuale da 1 a massimo (probabilità) (come selezionare una coordinata y). Vedi se è inferiore o uguale al numero di possibilità in quel grado. Se non si ripete fino a quando non si dispone di un grado valido e possibilità. Questo si occupa della probabilità di distribuzione. Ora che hai scelto un grado valido, a quel punto devi semplicemente scegliere una persona a caso all'interno di quel grado. Fatto!
Il bello è, per aggiungere o rimuovere qualcuno, incrementare o decrementare la colonna del conteggio degli utenti e assegnare una nuova modifica (numero). Due piccoli aggiornamenti molto semplici. La complessità della memoria e la complessità del tempo di aggiungere / rimuovere / aggiornare l'utente e anche la complessità di scegliere un utente non è nulla, come O (1).
Abbiamo raggruppato l'utente in base al grado e il conteggio degli utenti catturati in ogni livello, quindi calcolato le probabilità per quel grado e utilizzato un semplice algoritmo di loop per selezionare le righe casuali e i valori casuali fino a ottenere un hit e infine selezionare una persona a caso quel grado.