Egy egyszerű algoritmus véletlenszerűen adott tömegű, dotzero

Néha előfordulhat, hogy ki kell választania egy véletlen elemet a listából, figyelembe véve azt a tényt, hogy egyes elemei nagyobb esélye van a szelekció, mint mások (több „tömeg”). Például, akkor megteszi alkalmazások listáját, és a letöltések száma, és véletlenszerűen választja ki a „népszerű alkalmazások”, attól függően, hogy a letöltések száma.

Ebben a cikkben megmutatom, két módon, hogy „kiegyensúlyozott” véletlenszerű kiválasztás - egy alkalmas kis listák és a többi optimalizált nagyobb számú elemet.

Egy egyszerű algoritmus alapú véletlen minta tömege

Általánosságban elmondható, hogy ez az algoritmus a következőképpen írható le:

1. Válassz egy véletlen számot egytől az összeg a „tömegek” az összes elem
2. A listán szereplő elemek hozzáadásával súlyt a számláló aktuális elem
3. Ellenőrizzük, hogy a számláló (a lépés №2) nagyobb vagy egyenlő, mint egy véletlen számot (lépésben №1), majd a ciklus befejezéséhez, és visszatér az aktuális elem. Ellenkező esetben folytassa a №2.

Ez az algoritmus könnyen alkalmazható, és gyorsan, amikor az elemek száma nem nagy, vagy ha szükséges, hogy a választás egyszerre. Az alábbiakban egy olyan funkció, hogy vesz egy sor tételek kiválasztási, valamint egy sor megfelelő súlyokat, és visszatér egy véletlenszerűen kiválasztott elem az első tömb. Használhatja bármilyen pozitív egész szám, mint a tömeg.

Itt látható egy példa a forgatókönyvet, hogy vezet vagy A, B, C, vagy egy valószínűsége 15%, 35% és 50%, sorrendben:

Az algoritmus véletlenszerűen ezer elemek

A fent leírt algoritmus fut nagyon lassan, ha az elemek egy listáját nagy, és meg kell, hogy néhány mintát. Ez azért van, mert át kell esniük a teljes tömb minden egyes alkalommal a funkciót.

Azonban az algoritmus lehet terjeszteni, hogy sokkal gyorsabb. Ahelyett, hogy kiszámításakor a teljes súlya (egy lépés №1) és a számláló (a lépés №2) minden egyes alkalommal, akkor csinálni egyszer, és mentse a számláló értéke a tömbben. Akkor tudjuk használni a bináris keresés gyorsan kiválaszthatja a megfelelő elemet. Az alábbiakban egy módosított változata a funkció:

A fenti szkript is tartalmaz két új funkciók - calc_lookups, amely kiszámítja egy tömbben való alkalmazásra bináris kereső, és közvetlenül binary_search funkció, amely megvalósítja a bináris keresés. Példa a script:

Összefoglalva

Hogy van egy ötlet, hogy mi az a sebesség, ezen algoritmusok: mindegyikről használtam egy tömb, amely 10.000 tétel, 10.000-szer egymás után. Az első algoritmust dolgozott 13 másodpercig, és a második mindössze 0,09 másodperc alatt.