a caso Python chiave del dizionario, ponderata per i valori

Question

ho un dizionario in cui ogni tasto ha un elenco di lunghezza variabile, ad esempio:

d = { 
'a': [1, 3, 2], 
'b': [6], 
'c': [0, 0] 
} 

C'è un modo pulito per ottenere una chiave dizionario casuale, ponderata per la lunghezza del suo valore? random.choice(d.keys()) peserà ugualmente i tasti, ma nel caso precedente voglio che venga restituito il valore 'a' circa la metà del tempo.

Answer 1

Questo potrebbe funzionare:

random.choice([k for k in d for x in d[k]]) 

Answer 2

Fai un elenco in cui ogni tasto viene ripetuta un numero di volte pari alla lunghezza del suo valore. Nel tuo esempio: ['a', 'a', 'a', 'b', 'c', 'c']. Quindi utilizzare random.choice().

Modifica: o, in modo meno elegante ma più efficiente, provare questo: prendere la somma delle lunghezze di tutti i valori nel dizionario, S (è possibile memorizzare nella cache e invalidare questo valore o tenerlo aggiornato mentre si modifica il dizionario, a seconda del modello di utilizzo esatto che si prevede). Genera un numero casuale da 0 a S, e fai una ricerca lineare attraverso i tasti del dizionario per trovare l'intervallo in cui cade il tuo numero casuale.

Penso che sia il meglio che puoi fare senza modificare o aggiungere alla rappresentazione dei dati.

Answer 3

Sai sempre il numero totale di valori nel dizionario? Se è così, questo potrebbe essere facile da fare con il seguente algoritmo, che può essere utilizzato ogni volta che si vuole fare una selezione probabilistica di alcuni articoli di un elenco ordinato:

1. iterare l'elenco delle chiavi.
2. Genera un valore casuale distribuito uniformemente tra 0 e 1 (ovvero "lancia i dadi").
3. Supponendo che questa chiave abbia valori N_VALS associati ad esso e ci sono valori totali TOTAL_VALS nell'intero dizionario, accettare questa chiave con una probabilità N_VALS/N_REMAINING, dove N_REMAINING è il numero di elementi rimasti nell'elenco.

Questo algoritmo ha il vantaggio di non dover generare alcun nuovo elenco, che è importante se il dizionario è grande. Il tuo programma paga solo il ciclo sui tasti K per calcolare il totale, un altro ciclo sui tasti che termineranno in media a metà e qualunque sia il costo per generare un numero casuale compreso tra 0 e 1. La generazione di un numero casuale è un'applicazione molto comune nella programmazione, quindi molte lingue hanno un'implementazione rapida di tale funzione. In Python l'random number generator un'implementazione C di Mersenne Twister algorithm, che dovrebbe essere molto veloce. Inoltre, la documentazione afferma che questa implementazione è thread-safe.

Ecco il codice.Sono sicuro che si può pulire in su se si desidera utilizzare le funzionalità più divinatorio:

#!/usr/bin/python 

import random 

def select_weighted(d): 
    # calculate total 
    total = 0 
    for key in d: 
     total = total + len(d[key]) 
    accept_prob = float(1.0/total) 

    # pick a weighted value from d 
    n_seen = 0 
    for key in d: 
     current_key = key 
     for val in d[key]: 
     dice_roll = random.random() 
     accept_prob = float(1.0/(total - n_seen)) 
     n_seen = n_seen + 1 
     if dice_roll <= accept_prob: 
      return current_key 

dict = { 
    'a': [1, 3, 2], 
    'b': [6], 
    'c': [0, 0] 
} 

counts = {} 
for key in dict: 
    counts[key] = 0 

for s in range(1,100000): 
    k = select_weighted(dict) 
    counts[k] = counts[k] + 1 

print counts 

Dopo l'esecuzione di questo 100 volte, ottengo tasti di selezione di questo numero di volte:

{'a': 49801, 'c': 33548, 'b': 16650} 

quelli sono abbastanza vicino ai vostri valori attesi di:

{'a': 0.5, 'c': 0.33333333333333331, 'b': 0.16666666666666666} 

Edit: Miles ha sottolineato un grave errore nella mia implementazione originale, che da allora è stato corretto. Mi dispiace per quello!

Answer 4

Dato che il tuo dict si adatta alla memoria, il metodo random.choice dovrebbe essere ragionevole. Ma assumendo il contrario, la tecnica successiva è quella di usare una lista di pesi in aumento e usare la bisettrice per trovare un peso scelto a caso.

>>> import random, bisect 
>>> items, total = [], 0 
>>> for key, value in d.items(): 
     total += len(value) 
     items.append((total, key)) 


>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1] 
'a' 
>>> items[bisect.bisect_left(items, (random.randint(1, total),))][1] 
'c' 

Answer 5

Ecco po 'di codice che si basa su una risposta precedente ho dato per probability distribution in python, ma sta usando la lunghezza per impostare il peso. Usa una catena markov iterativa in modo che non abbia bisogno di sapere qual è il totale di tutti i pesi. Attualmente si calcola la lunghezza massima ma se questo è troppo lento basta cambiare

self._maxw = 1 

a

self._maxw = max lenght 

e rimuovere

for k in self._odata: 
    if len(self._odata[k])> self._maxw: 
      self._maxw=len(self._odata[k]) 

ecco il codice.

import random 


class RandomDict: 
    """ 
    The weight is the length of each object in the dict. 
    """ 

    def __init__(self,odict,n=0): 
     self._odata = odict 
     self._keys = list(odict.keys()) 
     self._maxw = 1 # to increase speed set me to max length 
     self._len=len(odict) 
     if n==0: 
      self._n=self._len 
     else: 
      self._n=n 
     # to increase speed set above max value and comment out next 3 lines 
     for k in self._odata: 
      if len(self._odata[k])> self._maxw: 
       self._maxw=len(self._odata[k]) 


    def __iter__(self): 
     return self.next() 

    def next(self): 
     while (self._len > 0) and (self._n>0): 
      self._n -= 1 
      for i in range(100): 
       k=random.choice(self._keys) 
       rx=random.uniform(0,self._maxw) 
       if rx <= len(self._odata[k]): # test to see if that is the value we want 
        break 
      # if you do not find one after 100 tries then just get a random one 
      yield k 

    def GetRdnKey(self): 
     for i in range(100): 
      k=random.choice(self._keys) 
      rx=random.uniform(0,self._maxw) 

      if rx <= len(self._odata[k]): # test to see if that is the value we want 
       break 
     # if you do not find one after 100 tries then just get a random one 
     return k 



#test code 

d = { 
'a': [1, 3, 2], 
'b': [6], 
'c': [0, 0] 
} 


rd=RandomDict(d) 

dc = { 
'a': 0, 
'b': 0, 
'c': 0 
} 
for i in range(100000): 
    k=rd.GetRdnKey() 
    dc[k]+=1 

print("Key count=",dc) 



#iterate over the objects 

dc = { 
'a': 0, 
'b': 0, 
'c': 0 
} 

for k in RandomDict(d,100000): 
    dc[k]+=1 

print("Key count=",dc) 

Risultati del test

Key count= {'a': 50181, 'c': 33363, 'b': 16456} 
Key count= {'a': 50080, 'c': 33411, 'b': 16509} 

Answer 6

direi questo:

random.choice("".join([k * len(d[k]) for k in d])) 

Ciò rende chiaro che ogni k in D ottiene il maggior numero di occasioni come la lunghezza del suo valore. Naturalmente, si basa su chiavi del dizionario di lunghezza 1 che sono personaggi ....

---

Molto più tardi:

table = "".join([key * len(value) for key, value in d.iteritems()]) 
random.choice(table) 

Answer 7

senza costruire un nuovo, possibilmente grande elenco con valori ripetuti:

def select_weighted(d): 
    offset = random.randint(0, sum(d.itervalues())-1) 
    for k, v in d.iteritems(): 
     if offset < v: 
     return k 
     offset -= v 

Answer 8

Ho modificato alcune delle altre risposte per ottenere questo. È un po 'più configurabile. Ci vogliono 2 argomenti, una lista e una funzione lambda per dirgli come generare una chiave.

def select_weighted(lst, weight): 
    """ Usage: select_weighted([0,1,10], weight=lambda x: x) """ 
    thesum = sum([weight(x) for x in lst]) 
    if thesum == 0: 
     return random.choice(lst) 
    offset = random.randint(0, thesum - 1) 

    for k in lst: 
     v = weight(k) 
     if offset < v: 
     return k 
     offset -= v 

Grazie a sth per il codice di base per questo.