从一次面试旁观说起--Weighted Random Sampling算法

//Prize and Probablity (真黑心啊这几率。。。)
var prizeMap = map[string]float64{
  "gold": 0.02,
  "silver": 0.03,
  "bronze": 0.05,
  "nothing" : 0.9,
}

func luckyDraw(prizeMap map[string]float64) string{
  rand.Seed(time.Now().UnixNano())
  random := rand.Float64()
  for k, v := range prizeMap {
    if random < v {
      return k
    }
    random -= v
  }
  return "nothing"
}

//DataSet with weighted collection
var weightedPrizes = map[int][]string{
  1: []string{"Dyson", "iPhone"},
  2: []string{"XBox", "Switch"},
  3: []string{"Speaker", "AirPods"},
  50: []string{"nothing"},
}
//User Closure to create the function
func getLuckyDrawFunc(prizeMap map[int][]string) func()string {
  //Prepare a linear arrangement of all probabilities
  current := 0
  //Linear prizes markers
  prizeRange := make([]int, 0)
  //Actual Prizes
  actualPrizes := make([]string, 0)
  //Make prize markers
  for weight, prizes  := range prizeMap {
    for _, prize := range prizes {
      current += weight
      prizeRange = append(prizeRange, current)
      actualPrizes = append(actualPrizes, prize)
    }
  }
  rand.Seed(time.Now().UnixNano())
  //return the func that used to do lucky draw
  return func() string {
    random := rand.Intn(current)
    //Binary Search the prizeRange
    low := 0
    high := len(prizeRange) - 1
    for high >= low {
      mid := (low + high) / 2
      if random < prizeRange[mid] {
        high = mid - 1
      } else {
        low = mid + 1
      }
    }
    return actualPrizes[low]
  }
}

//interface{} has the format of prize name and weight
type PrizeCollection [][]interface{}

var a = PrizeCollection{
  {"Dyson",1},
  {"iPhone",1},
  {"XBox", 2},
}

func getHopScotchFunc(collection PrizeCollection) func() string {
  //Reverse Sort the Weights
  sort.Slice(collection, func(i, j int) bool {
    return collection[j][1].(int) < collection[i][1].(int)
  })
  sum := 0
  collectionWeightSum := make([]int, len(collection))
  for i := 0; i < len(collection); i++ {
    sum += collection[i][1].(int)
    collectionWeightSum[i] = sum
  }

  rand.Seed(time.Now().UnixNano())
  //return the func that used to do lucky draw
  return func() string {
    target := rand.Intn(collectionWeightSum[len(collectionWeightSum)-1])
    guessIndex := 0
    for true {
      if collectionWeightSum[guessIndex] > target {
        break
      }
      //Retrieve the actual weight of that index
      currentWeight := collection[guessIndex][1].(int)
      //Calculate the difference between the current sum and the target
      hopDistance := target - collectionWeightSum[guessIndex]
      //Calculate the safe distance (indice) to jump
      hopIndex := 1 + hopDistance/currentWeight
      //Jump
      guessIndex += hopIndex
    }
    return collection[guessIndex][0].(string)
  }
}

func getAliasFunc(collection PrizeCollection) func()string {
  totalPrizeNum := len(collection)
  sum := 0
  for i := 0; i < len(collection); i++ {
    sum += collection[i][1].(int)
  }
  //Get Average
  average	:= float64(sum) / float64(totalPrizeNum)
  //Aliases is a array of [float, int] so we use interface{}
  aliases := make([][]interface{}, totalPrizeNum)
  //Initialisaition
  for i := 0; i < totalPrizeNum; i++ {
    aliases[i] = []interface{}{1.0, 0.0}
  }
  //U can check the explanation first before coming back~
  bigWeights := make([][]interface{},0)
  smallWeights := make([][]interface{},0)
  for index, prizeItem := range collection {
    if float64(prizeItem[1].(int)) < average {
      smallWeights = append(smallWeights, []interface{}{index, float64(prizeItem[1].(int)) / average })
    } else {
      bigWeights = append(bigWeights, []interface{}{index, float64(prizeItem[1].(int)) / average })
    }
  }
  bigWeightsPosition := 0
  for i := 0; i < len(smallWeights); i++ {
    aliases[smallWeights[i][0].(int)] = []interface{}{smallWeights[i][1].(float64), bigWeights[bigWeightsPosition][0].(int)}
    bigWeights[bigWeightsPosition][1] = bigWeights[bigWeightsPosition][1].(float64) - (1 - smallWeights[i][1].(float64))
    if bigWeights[bigWeightsPosition][1].(float64) <= 1 {
      smallWeights = append(smallWeights, bigWeights[bigWeightsPosition])
      bigWeightsPosition++
      if bigWeightsPosition >= len(bigWeights) {
        break
      }
    }
  }
  //---------------------------return the func that used to do lucky draw
  rand.Seed(time.Now().UnixNano())
  return func() string {
    target := rand.Float64()*float64(len(collection))
    targetAlias := int(target)
    targetWeight := target - float64(targetAlias)
    if targetWeight < aliases[targetAlias][0].(float64) {
      return collection[targetAlias][0].(string)
    } else {
      return collection[aliases[targetAlias][1].(int)][0].(string)
    }
  }
}

def prepare_aliased_randomizer(weights):
    N = len(weights)
    avg = sum(weights)/N
    aliases = [(1, None)]*N
    smalls = ((i, w/avg) for i,w in enumerate(weights) if w < avg)
    bigs = ((i, w/avg) for i,w in enumerate(weights) if w >= avg)
    small, big = next(smalls, None), next(bigs, None)
    while big and small:
        aliases[small[0]] = (small[1], big[0])
        big = (big[0], big[1] - (1-small[1]))
        if big[1] < 1:
            small = big
            big = next(bigs, None)
        else:
            small = next(smalls, None)

    def weighted_random():
        r = random()*N
        i = int(r)
        odds, alias = aliases[i]
        return alias if (r-i) > odds else i

    return weighted_random

var a = PrizeCollection{
  {"Dyson",1},   //20%几率
  {"iPhone",1},  //20%几率
  {"Nothing",3}, //60%几率
}
//创造n个候选Bucket,n = len(PrizeCollection)
aliases: [{候选Bucket0}, {候选Bucket1}, {候选Bucket2}]

//所以这三种奖品的平均值为
avg := 1+1+3/3 = 5/3

small = [
  {"Dyson","候选Bucket0","weight/avg => 3/5"}, 
  {"iPhone","候选Bucket1","weight/avg => 3/5"}，
]
big = [
  {"Nothing","候选Bucket2","weight/avg => 9/5"}
]

//我们率先用候选bucket2填平候选bucket0所在的Dyson
aliases: [{3/5, "填平部分来自候选Bucket2"}, {候选Bucket1}, {候选Bucket2}]
//then 现在的候选Bucket2对应的 {"Nothing","候选Bucket2","9/5 - 2/5 => 7/5"},他任然大于1
//then 继续配平
aliases: [{3/5, "填平部分来自候选Bucket2"}, {3/5, "填平部分来自候选Bucket2"}, {5/5，没有填平}]