Mam na przykład ten stół
+ ----------------- + | owoce | waga | + ----------------- + | jabłko | 4 | | pomarańczowy | 2 | | cytryna | 1 | + ----------------- +
Muszę zwrócić losowy owoc. Ale jabłko powinno być zbierane 4 razy częściej niż cytryna i 2 razy częściej niż pomarańcza .
W bardziej ogólnym przypadku powinno to być f(weight)
często razy.
Jaki jest dobry ogólny algorytm do wdrożenia tego zachowania?
A może na Ruby są gotowe klejnoty? :)
PS
Zaimplementowałem obecny algorytm w Ruby https://github.com/fl00r/pickup
algorithms
ruby
math
random
fl00r
źródło
źródło
Odpowiedzi:
Najprostszym koncepcyjnie rozwiązaniem byłoby utworzenie listy, w której każdy element występuje tyle razy, ile jego waga, więc
Następnie użyj dowolnych funkcji, które masz do dyspozycji, aby wybrać losowy element z tej listy (np. Wygeneruj losowy indeks w odpowiednim zakresie). Jest to oczywiście mało wydajne pod względem pamięci i wymaga wag całkowitych.
Kolejne, nieco bardziej skomplikowane podejście wyglądałoby tak:
Oblicz skumulowane sumy wag:
Gdy wskaźnik poniżej 4 oznacza jabłko , 4 do poniżej 6 pomarańczy, a 6 do poniżej 7 cytryny .
Wygeneruj liczbę losową
n
z zakresu od0
dosum(weights)
.n
. Odpowiedni owoc to twój wynik.To podejście wymaga bardziej skomplikowanego kodu niż pierwszy, ale mniej pamięci i obliczeń oraz obsługuje wagi zmiennoprzecinkowe.
W przypadku każdego algorytmu krok konfiguracji można wykonać raz dla dowolnej liczby losowych wyborów.
źródło
Oto algorytm (w języku C #), który może wybierać losowo ważony element z dowolnej sekwencji, iterując go tylko raz:
Jest to oparte na następującym rozumowaniu: wybierzmy pierwszy element naszej sekwencji jako „bieżący wynik”; następnie przy każdej iteracji zachowaj ją lub odrzuć i wybierz nowy element jako bieżący. Możemy obliczyć prawdopodobieństwo, że dany element zostanie wybrany na końcu jako iloczyn wszystkich prawdopodobieństw, że nie zostanie odrzucony w kolejnych krokach, razy razy prawdopodobieństwo, że zostanie on wybrany. Jeśli wykonasz matematykę, zobaczysz, że ten produkt upraszcza (ciężar elementu) / (suma wszystkich ciężarów), a dokładnie tego potrzebujemy!
Ponieważ ta metoda iteruje tylko raz sekwencję wejściową, działa nawet z nieprzyzwoicie dużymi sekwencjami, pod warunkiem, że suma wag pasuje do
int
(lub możesz wybrać większy typ dla tego licznika)źródło
Już obecne odpowiedzi są dobre i rozwinę je nieco.
Jak zasugerował Benjamin, w tego rodzaju problemach zwykle wykorzystuje się skumulowane kwoty:
Aby znaleźć element w tej strukturze, możesz użyć czegoś takiego jak fragment kodu Neverminda. Ten fragment kodu C #, którego zwykle używam:
Teraz interesująca część. Jak skuteczne jest to podejście i jakie jest najbardziej wydajne rozwiązanie? Mój fragment kodu wymaga pamięci O (n) i działa w czasie O (n) . Nie sądzę, że można tego dokonać w przestrzeni mniejszej niż O (n), ale złożoność czasu może być znacznie niższa, w rzeczywistości O (log n) . Sztuką jest użycie wyszukiwania binarnego zamiast zwykłej pętli for.
Jest też historia o aktualizacji wag. W najgorszym przypadku aktualizacja wagi dla jednego elementu powoduje aktualizację sumarycznych sum dla wszystkich elementów, zwiększając złożoność aktualizacji do O (n) . To też można zmniejszyć do O (log n) za pomocą binarnego drzewa indeksowanego .
źródło
Jest to prosta implementacja w języku Python:
i
W algorytmach genetycznych ta procedura wyboru nazywa się selekcją proporcjonalną do sprawności lub selekcją koła ruletki, ponieważ:
Typowe algorytmy mają złożoność O (N) lub O (log N), ale możesz także wykonać O (1) (np. Wybór koła ruletki poprzez akceptację stochastyczną ).
źródło
Ta istota robi dokładnie to, o co prosisz.
możesz użyć tego w ten sposób:
Powyższy kod najprawdopodobniej (% 98) zwróci wartość 0, która jest indeksem „jabłka” dla danej tablicy.
Ponadto ten kod testuje metodę podaną powyżej:
Daje to wynik podobny do tego:
źródło