Jak wdrożyć losowe ważenie

Niedawno napisałem kod, który uważałem za bardzo nieefektywny, ale ponieważ zawierał tylko kilka wartości, zaakceptowałem go. Nadal jednak interesuje mnie lepszy algorytm dla następujących elementów:

1. Lista X obiektów, z których każdy ma przypisaną „wagę”
2. Zsumuj wagi
3. Wygeneruj losową liczbę od 0 do sumy
4. Iteruj przez obiekty, odejmując ich wagę od sumy, aż suma będzie dodatnia
5. Usuń obiekt z listy, a następnie dodaj go na końcu nowej listy

Pozycje 2,4 i 5 zajmują nczas, więc jest to O(n^2)algorytm.

Czy można to poprawić?

Jako przykład tasowania ważonego element ma większą szansę na bycie z przodu o większej masie.

Przykład (wygeneruję liczby losowe, aby były prawdziwe):

6 obiektów o wadze 6,5,4,3,2,1; Suma wynosi 21

Wybrałem 19: 19-6-5-4-3-2 = -1więc 2 idzie na pierwszą pozycję, wagi są teraz 6,5,4,3,1; Suma wynosi 19

Wybrałem 16: 16-6-5-4-3 = -2więc 3 idzie na drugą pozycję, ciężary są teraz 6,5,4,1; Suma wynosi 16

Wybrałem 3: 3-6 = -3w ten sposób 6 idzie na trzecią pozycję, wagi są teraz 5,4,1; Suma wynosi 10

Wybrałem 8: 8-5-4 = -1w ten sposób 4 idzie na czwartą pozycję, wagi są teraz 5,1; Suma wynosi 6

Wybrałem 5: 5-5=0tak więc 5 idzie na piątej pozycji, ciężary są teraz 1; Suma wynosi 1

Wybrałem 1: 1-1=0w ten sposób 1 idzie na ostatnią pozycję, nie mam już ciężarów, kończę

Można to zaimplementować O(n log(n))za pomocą drzewa.

Najpierw utwórz drzewo, przechowując w każdym węźle skumulowaną sumę wszystkich potomnych węzłów po prawej i lewej stronie każdego węzła.

Aby pobrać próbkę elementu, rekurencyjnie próbkuj z węzła głównego, używając sum skumulowanych, aby zdecydować, czy zwrócisz bieżący węzeł, węzeł z lewej czy węzeł z prawej. Za każdym razem, gdy próbkujesz węzeł, ustaw jego wagę na zero, a także aktualizuj węzły nadrzędne.

Oto moja implementacja w Pythonie:

import random

def weigthed_shuffle(items, weights):
    if len(items) != len(weights):
        raise ValueError("Unequal lengths")

    n = len(items)
    nodes = [None for _ in range(n)]

    def left_index(i):
        return 2 * i + 1

    def right_index(i):
        return 2 * i + 2

    def total_weight(i=0):
        if i >= n:
            return 0
        this_weigth = weights[i]
        if this_weigth <= 0:
            raise ValueError("Weigth can't be zero or negative")
        left_weigth = total_weight(left_index(i))
        right_weigth = total_weight(right_index(i))
        nodes[i] = [this_weigth, left_weigth, right_weigth]
        return this_weigth + left_weigth + right_weigth

    def sample(i=0):
        this_w, left_w, right_w = nodes[i]
        total = this_w + left_w + right_w
        r = total * random.random()
        if r < this_w:
            nodes[i][0] = 0
            return i
        elif r < this_w + left_w:
            chosen = sample(left_index(i))
            nodes[i][1] -= weights[chosen]
            return chosen
        else:
            chosen = sample(right_index(i))
            nodes[i][2] -= weights[chosen]
            return chosen

    total_weight() # build nodes tree

    return (items[sample()] for _ in range(n - 1))

Stosowanie:

In [2]: items = list(range(10))
   ...: weights = list(range(10, 0, -1))
   ...:

In [3]: for _ in range(10):
   ...:     print(list(weigthed_shuffle(items, weights)))
   ...:
[5, 0, 8, 6, 7, 2, 3, 1, 4]
[1, 2, 5, 7, 3, 6, 9, 0, 4]
[1, 0, 2, 6, 8, 3, 7, 5, 4]
[4, 6, 8, 1, 2, 0, 3, 9, 7]
[3, 5, 1, 0, 4, 7, 2, 6, 8]
[3, 7, 1, 2, 0, 5, 6, 4, 8]
[1, 4, 8, 2, 6, 3, 0, 9, 5]
[3, 5, 0, 4, 2, 6, 1, 8, 9]
[6, 3, 5, 0, 1, 2, 4, 8, 7]
[4, 1, 2, 0, 3, 8, 6, 5, 7]

weigthed_shufflejest generatorem, dzięki czemu możesz kefektywnie próbkować najlepsze produkty. Jeśli chcesz przetasować całą tablicę, po prostu iteruj nad generatorem, aż do wyczerpania (używając listfunkcji).

AKTUALIZACJA:

Ważone losowe próbkowanie (2005; Efraimidis, Spirakis) zapewnia do tego bardzo elegancki algorytm. Wdrożenie jest bardzo proste, a także działa w O(n log(n)):

def weigthed_shuffle(items, weights):
    order = sorted(range(len(items)), key=lambda i: -random.random() ** (1.0 / weights[i]))
    return [items[i] for i in order]

EDYCJA: Ta odpowiedź nie interpretuje wag w sposób, którego można by się spodziewać. Tj. Przedmiot o wadze 2 nie jest dwa razy bardziej prawdopodobne niż pierwszy o wadze 1.

Jednym ze sposobów przetasowania listy jest przypisanie losowych liczb do każdego elementu na liście i sortowanie według tych liczb. Możemy rozszerzyć ten pomysł, musimy tylko wybrać ważone liczby losowe. Na przykład możesz użyć random() * weight. Różne wybory spowodują różne rozkłady.

W czymś takim jak Python powinno to być tak proste, jak:

items.sort(key = lambda item: random.random() * item.weight)

Uważaj, aby nie oceniać kluczy więcej niż jeden raz, ponieważ będą miały różne wartości.

Po pierwsze, zacznijmy od tego, że waga danego elementu na liście do sortowania jest stała. Nie będzie się zmieniać między iteracjami. Jeśli tak, to ... cóż, to większy problem.

Dla ilustracji użyjmy talii kart, w której chcemy obciążyć karty twarzy do przodu. weight(card) = card.rank. Podsumowując, jeśli nie wiemy, rozkład wag jest rzeczywiście O (n) jeden raz.

Te elementy są przechowywane w uporządkowanej strukturze, takiej jak modyfikacja na indeksowanej liście pominięć, dzięki czemu można uzyskać dostęp do wszystkich indeksów poziomów z danego węzła:

   1 10
 o ---> o -------------------------------------------- -------------> o Najwyższy poziom
   1 3 2 5
 o ---> o ---------------> o ---------> o ---------------- -----------> o Poziom 3
   1 2 1 2 5
 o ---> o ---------> o ---> o ---------> o ----------------- ----------> o Poziom 2
   1 1 1 1 1 1 1 1 1 1 1 
 o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o ---> o Poziom dolny

Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL
      Węzeł Węzeł Węzeł Węzeł Węzeł Węzeł Węzeł Węzeł Węzeł Węzeł

Jednak w tym przypadku każdy węzeł „zajmuje” tyle miejsca, ile jego waga.

Teraz, patrząc na kartę z tej listy, można uzyskać dostęp do jej pozycji na liście w czasie O (log n) i usunąć ją z powiązanych list w czasie O (1). Ok, to może nie być O (1), może to być czas O (log log n) (musiałbym pomyśleć o tym więcej). Usunięcie szóstego węzła w powyższym przykładzie wymagałoby aktualizacji wszystkich czterech poziomów - a te cztery poziomy są niezależne od liczby elementów na liście (w zależności od sposobu implementacji poziomów).

Ponieważ ciężar elementu jest stały, można po prostu zrobić to sum -= weight(removed)bez konieczności ponownego przechodzenia przez strukturę.

I tak, masz jednorazowy koszt O (n) i wartość wyszukiwania O (log n) oraz koszt usunięcia z listy O (1). Staje się to O (n) + n * O (log n) + n * O (1), co daje ogólną wydajność O (n log n).

Spójrzmy na to z kartami, bo tego właśnie użyłem powyżej.

      10
do góry 3 -----------------------> 4d
                                .
       3 7.
    2 ---------> 2d ---------> 4d
                  . .
       1 2. 3 4.
bot 1 -> Reklama -> 2d -> 3d -> 4d

To naprawdę niewielka talia z tylko 4 kartami. Łatwo będzie zobaczyć, jak można to rozszerzyć. W przypadku 52 kart idealna struktura miałaby 6 poziomów (log ₂ (52) ~ = 6), chociaż jeśli zagłębisz się w listy pominięć, nawet to można by zmniejszyć do mniejszej liczby.

Suma wszystkich wag wynosi 10. Otrzymujesz więc losową liczbę z [1 .. 10) i jej 4 Przechodzisz przez listę pominięć, aby znaleźć przedmiot znajdujący się na suficie (4). Ponieważ 4 to mniej niż 10, przenosisz się z najwyższego poziomu na drugi poziom. Cztery to więcej niż 3, więc teraz mamy 2 diamenty. 4 to mniej niż 3 + 7, więc schodzimy na najniższy poziom, a 4 to mniej niż 3 + 3, więc mamy 3 diamenty.

Po usunięciu 3 diamentów ze struktury, struktura wygląda teraz następująco:

       7
do góry 3 ----------------> 4d
                         .
       3 4.
    2 ---------> 2d -> 4d
                  . .
       1 2. 4
bot 1 -> Reklama -> 2d -> 4d

Zauważ, że węzły zajmują pewną „przestrzeń” proporcjonalną do ich ciężaru w strukturze. Pozwala to na wybór ważony.

Ponieważ jest to w przybliżeniu zrównoważone drzewo binarne, wyszukiwanie w tym obszarze nie musi przechodzić przez dolną warstwę (która byłaby O (n)), a zamiast tego przechodzenie od góry pozwala na szybkie przeskakiwanie w dół struktury w celu znalezienia tego, czego szukasz dla.

Wiele z tego można by zrobić za pomocą pewnego rodzaju zrównoważonego drzewa. Problem polega na ponownym zrównoważeniu struktury po usunięciu węzła staje się mylące, ponieważ nie jest to klasyczna struktura drzewa, a sprzątanie pamięta, że ​​4 diamenty są teraz przenoszone z pozycji [6 7 8 9] na [3 4 5 6] może kosztować więcej niż korzyści wynikające ze struktury drzewa.

Jednakże, chociaż lista pominięć jest zbliżona do drzewa binarnego pod względem zdolności do opuszczania listy w czasie O (log n), ma ona prostotę pracy z listą połączoną.

Nie oznacza to, że łatwo to wszystko zrobić (nadal musisz mieć na oku wszystkie linki, które musisz zmodyfikować po usunięciu elementu), ale oznacza to tylko aktualizację, ile masz poziomów i ich łączy niż wszystko po prawej stronie na właściwej strukturze drzewa.