Soru Random.choice'in ağırlıklı bir versiyonu


Random.choice'in ağırlıklı bir versiyonunu yazmam gerekiyordu (listedeki her elemanın seçilme olasılığı farklıdır). Bu benim ortaya çıktığım şey:

def weightedChoice(choices):
    """Like random.choice, but each element can have a different chance of
    being selected.

    choices can be any iterable containing iterables with two items each.
    Technically, they can have more than two items, the rest will just be
    ignored.  The first item is the thing being chosen, the second item is
    its weight.  The weights can be any numeric values, what matters is the
    relative differences between them.
    """
    space = {}
    current = 0
    for choice, weight in choices:
        if weight > 0:
            space[current] = choice
            current += weight
    rand = random.uniform(0, current)
    for key in sorted(space.keys() + [current]):
        if rand < key:
            return choice
        choice = space[key]
    return None

Bu işlev benim için aşırı karmaşık ve çirkin görünüyor. Buradaki herkesin bunu iyileştirmek için ya da bunu yapmanın alternatif yollarını önerebileceğini umuyorum. Verimlilik, kod temizliği ve okunabilirlik olarak benim için önemli değil.


153
2017-09-09 18:59


Menşei


Bu soru farklıdır, çünkü dikte anahtarlarının uzunluğuna dayanmak yerine açık ağırlıklar vardır. - Ned Batchelder
Aslında çözümünüzü seviyorum çünkü oldukça okunabilir ve girişi yalnızca bir kez geçme özelliği var. - liori
2014 itibariyle random.choice  bunu yapabilir çok. - n1000
@ n1000: Bu numpy.random.choice, değil random.choice. - user2357112
fakat random.choices (çoğul dikkat) ağırlıkları geçebilir (doktor) - Ciprian Tomoiagă


Cevaplar:


1.7.0 sürümünden beri, NumPy bir choice olasılık dağılımlarını destekleyen işlev.

from numpy.random import choice
draw = choice(list_of_candidates, number_of_items_to_pick, p=probability_distribution)

Bunu not et probability_distribution aynı sırayla bir dizidir list_of_candidates. Anahtar kelimeyi de kullanabilirsiniz replace=False davranışı değiştirmek için çizilmiş öğelerin değiştirilmemesi için.


182
2017-10-04 18:56



Sevgili Sevgili, 2014 itibariyle bu doğru cevap ... Keşke bu gibi durumlarda soruları güncellemenin resmi bir yolu vardı. - n1000
Bu gerçekten güzel bir cevap ama yine de numpy ile alternatifleri takdir ediyorum. - Josep Valls
Yüklemek biraz sert görünüyor numpy sadece bu fonksiyon için… - Sardathrion
Python 3.6 kullanarak 2017+ doğru cevabı arayın - StefanJCollier
Testlerimden, bu büyüklükten daha yavaş bir emirdir. random.choices bireysel aramalar için. Çok fazla rastgele sonuca ihtiyacınız varsa, bunları ayarlayarak hepsini tek seferde seçmek çok önemlidir. number_of_items_to_pick. Bunu yaparsanız, büyüklük derecesi daha hızlıdır. - jpmc26


def weighted_choice(choices):
   total = sum(w for c, w in choices)
   r = random.uniform(0, total)
   upto = 0
   for c, w in choices:
      if upto + w >= r:
         return c
      upto += w
   assert False, "Shouldn't get here"

127
2017-09-09 19:08



Bir işlemi bırakabilir ve for döngüsündeki ifadeleri ters çevirerek bir zaman şeridini kaydedebilirsiniz: upto +=w; if upto > r - knite
@knite, Lütfen bunu önermeyin. Bunu test ettin mi? Dağıtımı tamamen bozar. Koşu weighted_choice([('a',1.0),('b',2.0),('c',3.0)]) Sizin modifikasyonunuzla birlikte, b asla ... - Cerin
@rsk, Haklısın, bu çok nadir bir olay olmasına rağmen. Değiştirerek > r için >= r bu sorunu benim için giderir. - Cerin
bir silindiri silerek ve her seferinde ağırlıkça r'yi azaltarak kaydedin. Karşılaştırma o zaman if r < 0 - JnBrymn
sen yapabilir misin for ... else yanlış iddianın yerine inşaat - maxbellec


Dan beri Python3.6 bir yöntem var choices itibaren random modülü.

Python 3.6.1 (v3.6.1:69c0db5050, Mar 21 2017, 01:21:04)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.0.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import random

In [2]: random.choices(
...:     population=[['a','b'], ['b','a'], ['c','b']],
...:     weights=[0.2, 0.2, 0.6],
...:     k=10
...: )

Out[2]:
[['c', 'b'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['b', 'a'],
 ['c', 'b'],
 ['c', 'b']]

Ve insanlar da var olduğunu belirtti numpy.random.choice hangi destek ağırlıkları FAKAT desteklemiyor 2d dizileri, ve bunun gibi.

Yani, temelde ne istersen alabilirsiniz (görmek güncelleştirme) yerleşik random.choices eğer varsa 3.6.x Python.

GÜNCELLEŞTİRME: Gibi @Rogan Josh nazikçe belirtilmiş, random.choices belirtilen değere göre değiştirmeden değerleri geri dönemez docs:

Bir dönüş k Popülasyondan seçilen elemanların büyüklüğü değiştirme ile.

Ve @ Ronan-Paixãoparlak cevap şöyle belirtiyor numpy.choice vardır replace argüman, bu davranışı kontrol eder.


89
2017-10-11 12:11



Bu çok güncel bir cevaptır, python 3.6 aslında ağırlıklı choices işlevi. Mükemmel. - EmlynC
Cevap kabul edilmeli, bence. - Ilya V. Schurov
Mükemmel seçim (amaçlanmıştır). - jpmc26
Bu ağırlıklarla seçilebilir, ancak değiştirme işlemini durduramaz. np.random.choice yapabilir. - roganjosh
@roganjosh true, teşekkür ederim, güncellenmiş cevapta bahsedeceğim. - vishes_shell


  1. Ağırlıkları bir kümülatif dağılım.
  2. kullanım random.random () rastgele seçmek şamandıra 0.0 <= x < total.
  3. Ara kullanarak dağıtım bisect.bisect gibi örnekte gösterilen http://docs.python.org/dev/library/bisect.html#other-examples.
from random import random
from bisect import bisect

def weighted_choice(choices):
    values, weights = zip(*choices)
    total = 0
    cum_weights = []
    for w in weights:
        total += w
        cum_weights.append(total)
    x = random() * total
    i = bisect(cum_weights, x)
    return values[i]

>>> weighted_choice([("WHITE",90), ("RED",8), ("GREEN",2)])
'WHITE'

Birden fazla seçim yapmanız gerekiyorsa, bunu iki fonksiyona ayırın, biri kümülatif ağırlıkları ve diğerini rastgele bir noktaya bölmek için.


67
2017-12-01 09:37



Bu Ned'in cevabından daha etkili. Temel olarak, seçimler üzerinden doğrusal (O (n)) bir arama yapmak yerine, ikili bir arama yapar (O (log n)). 1! - NHDaly
rastgele () 1.0 döndürmek için ise aralık dışında tuple endeksi - Jon Vaughan
Bu hala devam ediyor O(n) kümülatif dağılım hesaplaması nedeniyle. - Lev Levitsky
Bu çözümü daha çok seviyorum. Temiz ve anlaşılması kolay kod. - Homunculus Reticulli
Bu çözüm, aynı seçenek için birden fazla ağırlıklı çağrıya ihtiyaç duyulduğunda daha iyidir. Bu durumda, birikimli toplamı bir kez oluşturabilir ve her bir çağrı için bir ikili arama yapabilirsiniz. - Amos


Eğer numpy kullanarak düşünmüyorsanız, kullanabilirsiniz numpy.random.choice.

Örneğin:

import numpy

items  = [["item1", 0.2], ["item2", 0.3], ["item3", 0.45], ["item4", 0.05]
elems = [i[0] for i in items]
probs = [i[1] for i in items]

trials = 1000
results = [0] * len(items)
for i in range(trials):
    res = numpy.random.choice(items, p=probs)  #This is where the item is selected!
    results[items.index(res)] += 1
results = [r / float(trials) for r in results]
print "item\texpected\tactual"
for i in range(len(probs)):
    print "%s\t%0.4f\t%0.4f" % (items[i], probs[i], results[i])

Şimdiye kadar kaç seçim yapmanız gerektiğini biliyorsanız, bunun gibi bir döngü olmadan yapabilirsiniz:

numpy.random.choice(items, trials, p=probs)

18
2018-03-21 15:14





Bir liste yerine ağırlıklı bir sözlük varsa bunu yazabilirsiniz

items = { "a": 10, "b": 5, "c": 1 } 
random.choice([k for k in items for dummy in range(items[k])])

Bunu not et [k for k in items for dummy in range(items[k])] bu listeyi üretiyor ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b', 'b']


15
2018-05-18 15:49



Bu, küçük toplam nüfus değerleri için çalışır, ancak büyük veri kümeleri için geçerli değildir (örneğin, ABD'nin ABD nüfusu, içinde 300 milyon maddeyle çalışan bir liste oluşturacaktır). - Ryan
İş yapar mı, Kudos - nehemiah


Ham, ancak yeterli olabilir:

import random
weighted_choice = lambda s : random.choice(sum(([v]*wt for v,wt in s),[]))

Çalışıyor mu?

# define choices and relative weights
choices = [("WHITE",90), ("RED",8), ("GREEN",2)]

# initialize tally dict
tally = dict.fromkeys(choices, 0)

# tally up 1000 weighted choices
for i in xrange(1000):
    tally[weighted_choice(choices)] += 1

print tally.items()

Baskılar:

[('WHITE', 904), ('GREEN', 22), ('RED', 74)]

Tüm ağırlıkların tam sayı olduğunu varsayar. 100'e kadar eklemek zorunda değiller, bunu test sonuçlarını daha kolay yorumlamak için yaptım. (Ağırlıklar kayan noktalı sayı ise, tüm ağırlıklar> 1'e kadar 10 defa tekrarlayın.)

weights = [.6, .2, .001, .199]
while any(w < 1.0 for w in weights):
    weights = [w*10 for w in weights]
weights = map(int, weights)

15
2017-09-09 19:13



Güzel, tüm ağırlıkların tamsayı olduğunu varsayabilirim. - Colin
Bu örnekte nesnelerin çoğaltılacağı gibi görünüyor. Bu verimsiz olur (ve ağırlıkların tamsayılara dönüştürülmesi işlevi de öyle). Bununla birlikte, tamsayı ağırlıkları küçükse, bu çözüm iyi bir tek katlıdır. - wei2912
Primitifler çoğaltılacak, ancak nesneler sadece nesnelerin değil, çoğaltılan referanslara sahip olacaktır. (bu yüzden, bir liste listesi oluşturamazsınız. [[]]*10- Dış listedeki tüm öğeler aynı listeye işaret eder. - PaulMcG


İşte Python 3.6 için standart kütüphaneye dahil edilen versiyon:

import itertools as _itertools
import bisect as _bisect

class Random36(random.Random):
    "Show the code included in the Python 3.6 version of the Random class"

    def choices(self, population, weights=None, *, cum_weights=None, k=1):
        """Return a k sized list of population elements chosen with replacement.

        If the relative weights or cumulative weights are not specified,
        the selections are made with equal probability.

        """
        random = self.random
        if cum_weights is None:
            if weights is None:
                _int = int
                total = len(population)
                return [population[_int(random() * total)] for i in range(k)]
            cum_weights = list(_itertools.accumulate(weights))
        elif weights is not None:
            raise TypeError('Cannot specify both weights and cumulative weights')
        if len(cum_weights) != len(population):
            raise ValueError('The number of weights does not match the population')
        bisect = _bisect.bisect
        total = cum_weights[-1]
        return [population[bisect(cum_weights, random() * total)] for i in range(k)]

Kaynak: https://hg.python.org/cpython/file/tip/Lib/random.py#l340


8
2017-10-11 12:25