Algoritmo per scegliere l'utente

5

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.

    
posta maxpolk 22.08.2013 - 07:26
fonte

3 risposte

4
  1. Metti ogni utente rank volte in una struttura dati adatta (borsa, multiset, elenco, array). Tale struttura dati dovrebbe già essere disponibile per la tua lingua, probabilmente non è necessario implementarla tu stesso.
  2. Esempio di un elemento casuale da quella struttura dati. Tale operazione dovrebbe già essere disponibile, probabilmente non è necessario implementarla da soli.

Ad esempio in Ruby:

users = %i[A B C D]
ranks = [1, 1, 5, 2]

user_pool = users.map.with_index {|u, i| [u] * ranks[i] }.flatten
# => [:A, :B, :C, :C, :C, :C, :C, :D, :D]

user_pool.sample
# => :C

Nessun loop, nessun conteggio, nessun totale di calcolo. Solo due righe che fanno uso del framework delle collezioni.

    
risposta data 22.08.2013 - 10:58
fonte
6

Non devi precalcolare gli intervalli se conosci la classifica.

  1. Aggiungi il totale nei ranghi
  2. crea il tuo numero casuale compreso tra 1 e quella somma
  3. Per selezionare l'utente, inizia un conteggio a zero, passa in rassegna gli utenti per creare un totale parziale di ranghi e quando quel totale è uguale o superiore al tuo numero casuale, questo è il tuo utente.
risposta data 22.08.2013 - 08:23
fonte
2

Se inverti il tuo valore di RANK in modo che i valori più bassi siano più probabili di quanto sia molto più semplice, oppure puoi definire un valore di RANK di cap di dire 10 e poi andare (10-RANK).

Per implementarlo in SQL è facile.

SELECT *,((10-rank) * RAND()) AS odds
    FROM users
    ORDER BY odds
    LIMIT 1;

Questo genererà un valore casuale per utente da 0 al loro rango. Gli utenti con un rango più elevato hanno maggiori probabilità di ordinare sopra gli altri, quindi cercano solo il primo.

    
risposta data 22.08.2013 - 11:32
fonte

Leggi altre domande sui tag