Restituisce oggetti casuali in base al peso, livello avanzato

0

Ci sono molte domande tipiche come Invio casuale dell'elenco "elenco" di il suo "peso"

Immagina un problema più avanzato.

Hai N fonti di coppia (item_id, weight) informazioni. Chiamiamoli Shard . I frammenti contengono elenchi di coppie (item_id, weight) .

E tu hai il nodo centrale, chiamiamolo Centrale .

Il problema è: su Central scegli elementi casuali da The Big List (l'elenco virtualmente unito da tutti gli elenchi su tutti i frammenti) in base al loro peso attraverso tutti i pesi.

Ad esempio, abbiamo due frammenti:

+-------+---------+--------+
| shard | item_id | weight |
+-------+---------+--------+
|   1   |     1   |    7   |
|   1   |     2   |    4   |
|   1   |     3   |    2   |
|   2   |     4   |    5   |
|   2   |     5   |    1   |
+-------+---------+--------+

(Lascia che item_id sia univoco per tutti i frammenti.)

Primo problema :

Come scegliere item_id in modo casuale ma ponderato attraverso tutti i frammenti? Cioè total_weight == 7+4+2+5+1 == 19 , quindi 1 sarà scelto con probabilità di 7/19, 2 - 4/19, 3 - 2/19 e così via.

Secondo problema :

Come variare tutti gli oggetti da tutti i frammenti casualmente, ma ponderati attraverso tutti i frammenti?

vale a dire. l'intervallo ideale sarà: 1, 4, 2, 3, 5 (in base al loro peso),

ma potrebbe esserci un altro intervallo come 1, 2, 4, 3, 5 , ma leggermente meno frequente del precedente,

...

e anche il caso peggiore 5, 3, 2, 4, 1 può apparire, ma con una probabilità molto, molto piccola.

C'è un problema comune in informatica per questo?

    
posta vladon 06.09.2016 - 11:36
fonte

1 risposta

1

Nel problema 1, non si utilizzano le informazioni a cui appartiene un frammento di un determinato elemento. Quindi questo è in realtà solo scegliendo un oggetto a caso con i pesi. Puoi utilizzare il metodo nel post a cui ti sei collegato.

Per il problema 2, penso che potresti applicare ripetutamente il problema 1. Per prima cosa scegli il primo elemento e poi ricalcoli l'elenco e le ponderazioni. Questo può essere fatto in modo intelligente, ad esempio sottraendo il peso dell'articolo scelto per primo dal peso totale. Quindi ripetere per il secondo elemento, ecc ...

Più concreto, supponi di applicare il problema 1 una volta, e sceglie 4 in modo casuale a caso. Quindi applicheresti nuovamente il problema 1 su:

+---------+--------+

| item_id | weight |

+---------+--------+

|     1   |    7   |

|     2   |    4   |

|     3   |    2   |

|     5   |    1   |

+---------+--------+
    
risposta data 06.09.2016 - 19:21
fonte

Leggi altre domande sui tag