scelta ponderata con filtri [chiusa]

Question

Ho una lista di elementi con pesi:

{ id1, weight1 },
{ id2, weight2 },
...
{ idN, weightN }

I pesi sono piccoli numeri interi (diciamo, meno di 1000, spesso meno di 50). Numero totale di ID nella lista è inferiore a 1000 pure. (Ogni id viene elencato una sola volta.)

Per ogni query devo restituire un elemento di "abbastanza casuale" dalla lista. Se lo faccio domande E, dove E è proporzionale alla somma di tutti i pesi, lo stesso numero di volte in cui ogni elemento elemento deve essere esattamente proporzionale per il suo valore weight. Si noti che questo dovrebbe funzionare per i valori minori di E (ad esempio, fino al 50 somma dei pesi *). Vedere anche la nota alla fine della questione.

Fin qui tutto bene, mi piacerebbe risolvere questo compito mettendo id degli elementi in una lista circolare, duplicando loro i tempi di peso, poi mischiare la lista. Ogni restituisce la query capo della lista, e quindi incrementa la posizione della testa.

Ma in questo caso ho una ulteriore condizione:

Ho ulteriore parametro alla query: un filtro. Un filtro è una mappa di id => is_enabled. Se is_enabled è falso per una data id, che id dovrebbe essere esclusa dai risultati. Il valore E nella restrizione sopra è calcolato solo elementi abilitati. Cioè, disabili elemento pesi devono essere esclusi dalla query.

I filtri sono "uniche" per ogni query e comprendono voci per ogni id nella lista. (Si noti che questo implica 2 ^ 1.000 potenziali valori di filtro.)

C'è un modo per risolvere questo in modo efficiente? Ho bisogno l'algoritmo di essere efficace su un cluster multi-server.

Nota 1: voglio sottolineare che, come credo, la selezione di elementi del tutto a caso (come suggerito in una delle risposte), senza memorizzare qualsiasi stato, non funzionerà. Darà il numero esattamente proporzionale di elementi solo in numero infinito di domande. Generatore di numeri casuali ha pieno diritto di restituire i valori sleali per un lungo periodo di tempo.

Nota 2: Questo compito impone restrizioni sulla qualità della casualità. Vieni a pensarci, non è nemmeno necessario mischiare la lista nella soluzione semplice caso di cui sopra. Buona casualità è meglio, ma non è necessario a tutti.

Nota 3: prega di notare che 2 ^ 1.000 potenziali valori di filtro vuol dire che non riesco a memorizzare qualsiasi cosa, associata al valore del filtro - richiederà troppa memoria. Posso conservare qualcosa per il più recente (o spesso utilizzate) i filtri, ma non riesco a memorizzare le cose come elenco delle voci di offset, come io non posso permettermi di perdere i dati.

Nota 4: Non possiamo tornare metainformazione con la query e lasciare ai clienti di memorizzare lo stato per noi (buona idea in ogni caso, grazie, Diacleticus ). Non possiamo perché due client possono utilizzare accidentalmente lo stesso filtro (alcuni filtri sono più popolari di altri). In questo caso si deve usare lo stesso stato per entrambe le query. In realtà, cliente facendo più di una query è un evento relativamente raro.

Answer 1

Forse ho trovato una soluzione:

1. Conservare id->number_of_queries_left, dove valore iniziale per number_of_queries_left è, diciamo, weight * 10 (quindi la lista non viene aggiornata troppo spesso - esattamente proporzionale requisito sarebbe stata mantenuta, penso ).
2. Su ogni query:
   1. Scegli un id caso da filtro, in cui è is_enabled true.
   2. decremento number_of_queries_left per quella id.
   3. Se il risultato è inferiore o uguale a zero, segno che id usati e scegliere un altro.
   4. Se si usano tutti i valori e nessuno trovati, id->number_of_queries_left reinizializzare per tutti gli ID abilitati nel filtro ( "ricarica").

sembra che dovrebbe funzionare. Cosa ne pensi?

Aggiornamento 1:

Sono preoccupato che sembra che devo continuare a valore id->number_of_queries_left separato per ogni valore di filtro. Non posso permettermi che a causa di limitazioni di memoria (ci sono 2 ^ 1.000 potenziali valori di filtro). Ho ragione?

Qualcuno può aiutarmi a capire meglio le conseguenze del contatore number_of_queries_left condiviso, per favore?

Aggiornamento 2:

Crediti per l'idea Vai a Diacleticus (vedi commenti a questa risposta).

Che cosa succede se facciamo id->number_of_queries_left non di ripristino per tutte le voci abilitati nel filtro, ma invece li incrementiamo dei loro rispettivi pesi? Penso che questo dovrebbe risolvere le proporzioni. (O dovrebbe?)

L'unico problema è che con questo algoritmo ogni contatore number_of_queries_left può andare molto negativo. (Vedi sopra, ci farlo diminuire ogni volta che vogliamo guardare al suo valore.)

Così, in un caso pessimistico, anche incrementando tutti i contatori, che non porterà nessuno di loro sopra lo zero. Questo probabilmente va bene, dal momento che faremo in modo efficace solo corre il ciclo di incremento fino a qualsiasi valore diventerà positivo.

Aggiornamento 3:

No, non possiamo semplicemente eseguire il ciclo di incremento fino a qualsiasi valore diventerà positivo.

Questo spiedo i pesi:. Che parte negativa non ha "senso fisico" - non rappresenta i valori, restituiti dalla query

In questo modo, un approccio ibrido:

Quando si fa "ricarica", incrementa ogni contatore da weight + -min(0, current_counter_value). Questo dovrebbe essere fatto in modo atomico, ma che sembra fattibile.

Ancora, io non sono sicuro che la gestione di peso sarà giusto in questo caso.

Commenti?

Answer 2

Mi sembra che si deve tenere una traccia per ogni filtro diverso. Ciò significa che è necessario costruire una nuova lista già mescolato ogni volta che viene introdotto un nuovo filtro o quando tutti gli elementi sono spesi per il vecchio filtro.

EDIT: Ora che lavoriamo con valori proporzionali possiamo rimuovere l'elenco mischiato tutto, e lasciare che le statistiche mescolano per noi. Per ogni query impostare un contatore casuale (0..sum_of_all_enabled_weights_for_the_query). Vai dall'inizio della lista, e sottrarre da questo contatore tutti i pesi che si arriva lungo, se l'elemento è abilitato per la query, e basta ignorarlo se è disattivato. Se il contatore diventa negativo, allora vi siete trovati un elemento.

Answer 3

vedi Let se ho capito la tua domanda.

io pubblicare il codice di Mathematica, passo dopo passo, e l'uscita commentata da seguire facilmente.

Questa risposta fornisce un'uscita deterministico e ordinata (cioè non-shuffling). Se davvero bisogno di una permutazione casuale, si genera una sequenza filtrata intero in anticipo con questo stesso algoritmo, rimescolalo, e consumare i valori uno per uno.

Il programma

Fist definiamo due costanti:

n = 10; (* nbr of ids *)
m = 3;  (* max weight - 1 *) 

I mantenere i numeri piccoli in modo da poter controllare il passo di uscita per passo.

Ora definiamo un {id, peso} tavolo casuale con cui lavorare. Usiamo numeri primi come ID:

weights = Table[{Prime@k, RandomInteger[m] + 1}, {k, n}]

Output:

{{2, 3}, {3, 2}, {5, 3}, {7, 1}, {11, 1}, 
{13, 3}, {17, 1}, {19,4}, {23, 1}, {29, 2}}  

Avanti accumuliamo i valori pesi

accumulator = Accumulate[Table[k[[2]], {k, weights}]]

Output:

{3, 5, 8, 9, 10, 13, 14, 18, 19, 21}  

E noi fondiamo entrambe le tabelle per ottenere gli accumulatori nella tabella ID:

weightsAcc = MapThread[Append, {weights, accumulator}]

Output:

{{2, 3, 3}, {3, 2, 5}, {5, 3, 8}, {7, 1, 9}, {11, 1, 10}, 
 {13, 3, 13}, {17, 1, 14}, {19, 4, 18}, {23, 1, 19}, {29, 2, 21}}

Ora si inizializza il filtro, con i propri valori di default (vero o falso). Ho usato Vero:

filter = Table[{k[[1]], True}, {k, weights}]

Output:

{{2, True}, {3, True}, {5, True}, {7, True}, {11, True}, {13, True}, 
 {17, True}, {19, True}, {23, True}, {29, True}}  

Il trucco è quello di mantenere il filtro sincronizzata con il vettore ids, quindi si definisce una funzione per aggiornare il filtro in questo modo:

updateFilter[filter_, newValuePair_] :=Return@
         ReplaceAll[filter, {newValuePair[[1]], x_} -> newValuePair];  

E utilizzarlo per modificare due valori:

filter = updateFilter[filter, {2, False}];
filter = updateFilter[filter, {5, False}];
Print@filter

Output:

{{2,False},{3,True},{5,False},{7,True},{11,True},{13,True},
 {17,True},{19,True},{23,True},{29,True}}  

Ora definiamo la nostra query. Useremo due vars globali (agrhhhh!) E due funzioni per ottenere la cosa sincronizzato:

i = 1; j = 0; (* GLOBAL state variables *)

Adjustij[w_] := (                      (* parm w is weightsAcc *)
   j++;                                (* increment accumulator comparator*)
   If[j == w[[i, 3]], i++];            (* if current id exhausted, get next*)
   If[i == Length@w, i = 1; j = 0];    (* wraparound table when exhausted*)
);   

query[w_, filter_] :=                  (* parm w is weightsAcc *)
 (
  Adjustij[w];
  While[Not@filter[[i, 2]], Adjustij[w]];       (* get non filtered ids only *)
  Return[w[[i, 1]]];
  )

Naturalmente il ciclo while potrebbe essere accelerato solo saltare gli ID con filtro False, ma penso che l'intenzione è chiara in questo modo.

Ora eseguiamo la query 30 volte:

 Table[query[weightsAcc, filter], {30}]

e get:

{3, 3, 7, 11, 13, 13, 13, 17, 19, 19, 19, 19, 23, 3, 3, 7, 11, 13, \
 13, 13, 17, 19, 19, 19, 19, 23, 3, 3, 7, 11}  

che è la nostra lista (ciclicamente) con i pesi propri, ad eccezione di quei valori con il filtro in FALSE.

HTH!

Modifica: Server e codice del client, a spacco per rispondere a commenti

Può procedere querys simultanee con diversi filtri

Lo stato del filtro viene memorizzato sul client.

funzioni e codice server-Implemented:

Clear["Global`*"];

(*Server Implemented  Functions follows*)

AdjustFilterState[fs_] := Module[{i, j}, (    (*fs = filterstate, i,j localvars*)
     i = fs[[1]]; (*local vars*)              (*w  = weights with accs*)
     j = fs[[2]];
     j++;                                     (* increment accumulator comparator*)
     If[j == weightsAcc[[i, 3]], i++];        (* if current id exhausted, get next*)
     If[i == Length@weightsAcc, i = 1; j = 0];(* wraparound table when exhausted*)
     Return[{i, j}];);
   ];


query[filter_, fs_] := Module[{fsTemp},       (*fs = filterstate*)
   (
    fsTemp = AdjustFilterState[fs];           (* local var *)

    While[Not@filter[[fsTemp[[1]], 2]],       (* get non filtered ids only *)
       fsTemp = AdjustFilterState[fsTemp]
    ];

    Return[{weightsAcc[[fsTemp[[1]], 1]], fsTemp}]; (*return[value,{filterState}]*)
   )
   ];

initFilter[] := masterFilter; (*Init filters to your defult vallue*)

(*The trick is to get the filter coordinated with the list value*)
updateFilter[f_, newValuePair_] :=
 Return@ReplaceAll[f, {newValuePair[[1]], x_} -> newValuePair];

(*Server Code - Just initialize the whole thing
   The SERVER stores ONLY the weights vectors and a master filter initialized*)

n = 10; (* nbr of ids *)                                (*init vars*)
m = 3;  (*max weight - 1 *)

weights = Table[{Prime@k, RandomInteger[m] + 1}, {k, n}]; (*random weights to test*)
accumulator = Accumulate[Table[k[[2]], {k, weights}]];    
weightsAcc = MapThread[Append, {weights, accumulator}];   (*add acummulator to list*)
masterFilter= Table[{k[[1]],True}, {k,weights}]; (* only ONE virgin filter in server*)

Codice cliente:

(* Client Code 
   The CLIENT stores only the filter and the filterState*)
(* Set up filter and filterstate *)

filter = initFilter[];
filter = updateFilter[filter, {2, False}];  (*specify particular values*)
filter = updateFilter[filter, {5, False}];

filterState = {1,0}; (* these replace the previous GLOBAL state variables *)

ValuesList = {};  (*for storing results *)

Do[
 q1 = query[filter, filterState]; (* do the query *)
 AppendTo[ValuesList, q1[[1]]];   (* first element of return is the value *)
 filterState = q1[[2]];           (* second element is updated filter state *)
 , {30}  (*do 30 times*)
 ];
Print@ValuesList                 (* print results vector *)