Herhangi bir ağırlık (eşit olasılık) güzel bir tarif olmadan seçilmesi here.

Eğer bir ağırlıklı bir yaklaşımı dönüştürmek için bir yol olup olmadığını merak ediyordum.

Ayrıca diğer yaklaşımlar ile ilgileniyorum.

Güncelleme: Örneklemeolmadanyedek

Eğer örnekleme değiştirme ilebu algoritma (burada Python uygulanan) kullanabilirsiniz

import random

items = [(10, "low"),
         (100, "mid"),
         (890, "large")]

def weighted_sample(items, n):
    total = float(sum(w for w, v in items))
    i = 0
    w, v = items[0]
    while n:
        x = total * (1 - random.random() ** (1.0 / n))
        total -= x
        while x > w:
            x -= w
            i  = 1
            w, v = items[i]
        w -= x
        yield v
        n -= 1

Bu "O" (nmneredemöğelerin sayısı.

Neden bu işe yarıyor mu?Aşağıdaki algoritma dayanmaktadır:

def n_random_numbers_decreasing(v, n):
    """Like reversed(sorted(v * random() for i in range(n))),
    but faster because we avoid sorting."""
    while n:
        v *= random.random() ** (1.0 / n)
        yield v
        n -= 1

weighted_sample sadece bu algoritma fonksiyonu items listenin bir yürüyüş öğeleri bu rasgele sayılar tarafından seçilen almak için erimiş.

Bu da bir olasılık, çünkü bu çalışırnrasgele sayı 0..vdaha ne olacak ^em>zP( . = ^em>z/v)ⁿ. İçin çözmekzve olsunz=vP^1/n. Rastgele bir sayı için kullanılacakPdoğru dağıtım ile en büyük sayıyı alır; ve sadece süreci diğer tüm sayıları seçmek için tekrar edebiliriz.

Eğer örnekleme yedek almadanher düğüm bu subheap tüm maddelerin ağırlıkları toplamı önbelleğe burada ikili bir yığın içine tüm öğeleri koyabilirsiniz. Öbek yapı Om). Yığınından rastgele bir öğe seçerek, ağırlıkları saygı, O(logm). Bu maddenin kaldırılması ve önbelleğe alınan toplamları güncelleme de(logm). AlabilirsiniznO öğeleri(mngünlükm) zaman.

İşte böyle bir uygulama, bol yorumladı:

import random

class Node:
    # Each node in the heap has a weight, value, and total weight.
    # The total weight, self.tw, is self.w plus the weight of any children.
    __slots__ = ['w', 'v', 'tw']
    def __init__(self, w, v, tw):
        self.w, self.v, self.tw = w, v, tw

def rws_heap(items):
    # h is the heap. It's like a binary tree that lives in an array.
    # It has a Node for each pair in `items`. h[1] is the root. Each
    # other Node h[i] has a parent at h[i>>1]. Each node has up to 2
    # children, h[i<<1] and h[(i<<1) 1].  To get this nice simple
    # arithmetic, we have to leave h[0] vacant.
    h = [None]                          # leave h[0] vacant
    for w, v in items:
        h.append(Node(w, v, w))
    for i in range(len(h) - 1, 1, -1):  # total up the tws
        h[i>>1].tw  = h[i].tw           # add h[i]'s total to its parent
    return h

def rws_heap_pop(h):
    gas = h[1].tw * random.random()     # start with a random amount of gas

    i = 1                     # start driving at the root
    while gas > h[i].w:       # while we have enough gas to get past node i:
        gas -= h[i].w         #   drive past node i
        i <<= 1               #   move to first child
        if gas > h[i].tw:     #   if we have enough gas:
            gas -= h[i].tw    #     drive past first child and descendants
            i  = 1            #     move to second child
    w = h[i].w                # out of gas! h[i] is the selected node.
    v = h[i].v

    h[i].w = 0                # make sure this node isn't chosen again
    while i:                  # fix up total weights
        h[i].tw -= w
        i >>= 1
    return v

def random_weighted_sample_no_replacement(items, n):
    heap = rws_heap(items)              # just make a heap...
    for i in range(n):
        yield rws_heap_pop(heap)        # and pop n items off it.