简介

最近在项目中遇到了加密权重算法,记录下使用心得

问题描述

  • Given a list of items where each item has a weight (integer value), select a random item from the list based on that weight.
  • The key requirement — items with a higher weight value are more likely to be returned. So even the lowest weighted value will still sometimes be returned from the function.

解决思路

1.Add up all the weights for all the items in the list 2.Pick a number at random between 1 and the sum of the weights 3.Iterate over the items 4.For the current item, subtract the item’s weight from the random number that was originally picked 5.Compare the result to zero. If less than or equal to zero then break otherwise keep iterating. The key is that the larger the weight the more likely to be less than zero when compared to the random selection between zero and the sum of weights. 6.If not less than zero, continue iterating over the list, all the while subtracting more and more weights off the random number chosen from the sum of the weights.

伪码 

randomWeight = rand(1, sumOfWeights)
for each item in array
     randomWeight = randomWeight - item.Weight
     if randomWeight <= 0
          break // done, we select this item

例子(golang) 

package main

import (
    "errors"
     "fmt"
     "math/rand"
     "time"
)

type Game struct {
    Name   string
    Weight int
}

func main() {
    games := []Game{
        Game{Name: "Mario", Weight: 1},
        Game{Name: "Sonic", Weight: 2},
        Game{Name: "CoD", Weight: 4},
        Game{Name: "Link", Weight: 8},
        Game{Name: "Fantasy", Weight: 10},
        Game{Name: "Destiny", Weight: 7},
    }

    var totalWeight int
        for _, g := range games {
        totalWeight += g.Weight
    }

    results := map[string]int{}
    for i := 0; i < 10000; i++ {
        g, err := RandomWeightedSelect(games, totalWeight)
        if err != nil {
            panic(err)
        }
        if _, ok := results[g.Name]; ok {
            results[g.Name]++
        } else {
            results[g.Name] = 1
        }
    }
    fmt.Println(results)
}

func RandomWeightedSelect(games []Game, totalWeight int) (Game, error) {
    rand.Seed(time.Now().UnixNano())
    r := rand.Intn(totalWeight)
    for _, g := range games {
        r -= g.Weight
        if r <= 0 {
            return g, nil
        }
    }
    return Game{}, errors.New("No game selected")
}