Uneori poate fi necesar pentru a selecta un element aleatoriu din listă, ținând cont de faptul că unele elemente au o șansă mai mare de selecție decât altele (au mai mult „greutate“). De exemplu, puteți lua o listă de aplicații și numărul de descărcări, și aleatoriu selectați o „aplicații populare“, în funcție de numărul de download-uri.
În acest articol vă voi arăta două moduri de a selecție aleatorie „echilibrat“ - unul potrivite pentru liste mici și cealaltă optimizat pentru un număr mai mare de elemente.
Un algoritm bazat simplu de greutate eșantion aleatoriu
In termeni generali, acest algoritm poate fi descris după cum urmează:
- Alegeți un număr aleatoriu între unu și suma „greutăților“ ale tuturor elementelor
- În jos lista elementelor adăugând greutate la elementul curent contra
- Verificați dacă contorul (un pas №2) mai mare sau egală cu un număr aleatoriu (etapa №1), apoi finalizați ciclul și a reveni la elementul curent. În caz contrar, mergeți la pasul №2.
Acest algoritm este ușor de implementat și rapid atunci când numărul de elemente nu este mare, sau atunci când aveți nevoie pentru a face o alegere o dată. Mai jos este o funcție care are o serie de elemente de selecție, precum și o serie de greutăți corespunzătoare și returnează un element selectat aleatoriu din prima matrice. Puteți folosi orice număr întreg pozitiv, ca greutate.
Aici este un exemplu de script-ul care va conduce fie A, B, C, sau cu o probabilitate de 15%, 35% și 50%, respectiv:
Algoritmul aleatoriu din mii de elemente
Algoritmul descris mai sus poate rula foarte încet atunci când o listă de elemente este mare, și aveți nevoie pentru a face câteva mostre. Acest lucru se datorează faptului că trebuie să treacă prin întreaga rețea, de fiecare dată la funcția.
Cu toate acestea, algoritmul poate fi extins pentru a face mult mai rapid. În loc de a calcula greutatea totală a (un pas №1) și contorul (un pas №2) de fiecare dată, o puteți face o dată și de a salva valorile contra în matrice. Apoi, putem folosi o căutare binar pentru a selecta rapid elementul corect. Următoarele este o versiune modificată a funcției:
Script-ul de mai sus conține, de asemenea, două caracteristici noi - calc_lookups care calculează o matrice pentru a fi utilizat într-o căutare binară, și direct funcția binary_search care pune în aplicare binar de căutare. Exemplu de script:
în concluzie
Pentru a vă da o idee despre ceea ce este viteza acestor algoritmi: Pentru fiecare dintre ele am folosit o matrice care cuprinde 10.000 de articole, de 10.000 de ori la rând. Primul algoritm a lucrat timp de 13 secunde, iar a doua doar 0.09 secunde.