C#&PHP&Java实现Alias Method概率抽奖算法

# C#&PHP&Java实现Alias Method概率抽奖算法

13466发表于2015-10-27

 T 1 2 3 4 PDF 0.1 0.2 0.3 0.4 CDF 0.1 0.3 0.6 1  T 1 2 3 4 PDF 0.1 0.2 0.3 0.4 Alias 3 4 4 NULL

## 一、Alias Method概率抽奖算法的C#实现

```using System;
using System.Collections;
using System.Collections.Generic;
using System.linq;
using System.Text;

namespace Lanhusoft.Core
{
public class AliasMethod
{
/* The probability and alias tables. */
private int[] _alias;
private double[] _probability;

public AliasMethod(List<Double> probabilities)
{

/* Allocate space for the probability and alias tables. */
_probability = new double[probabilities.Count];
_alias = new int[probabilities.Count];

/* Compute the average probability and cache it for later use. */
double average = 1.0 / probabilities.Count;

/* Create two stacks to act as worklists as we populate the tables. */
var small = new Stack<int>();
var large = new Stack<int>();

/* Populate the stacks with the input probabilities. */
for (int i = 0; i < probabilities.Count; ++i)
{
/* If the probability is below the average probability, then we add
* it to the small list; otherwise we add it to the large list.
*/
if (probabilities[i] >= average)
large.Push(i);
else
small.Push(i);
}

/* As a note: in the mathematical specification of the algorithm, we
* will always exhaust the small list before the big list.  However,
* due to floating point inaccuracies, this is not necessarily true.
* Consequently, this inner loop (which tries to pair small and large
* elements) will have to check that both lists aren't empty.
*/
while (small.Count > 0 && large.Count > 0)
{
/* Get the index of the small and the large probabilities. */
int less = small.Pop();
int more = large.Pop();

/* These probabilities have not yet been scaled up to be such that
* 1/n is given weight 1.0.  We do this here instead.
*/
_probability[less] = probabilities[less] * probabilities.Count;
_alias[less] = more;

/* Decrease the probability of the larger one by the appropriate
* amount.
*/
probabilities[more] = (probabilities[more] + probabilities[less] - average);

/* If the new probability is less than the average, add it into the
* small list; otherwise add it to the large list.
*/
if (probabilities[more] >= average)
large.Push(more);
else
small.Push(more);
}

/* At this point, everything is in one list, which means that the
* remaining probabilities should all be 1/n.  Based on this, set them
* appropriately.  Due to numerical issues, we can't be sure which
* stack will hold the entries, so we empty both.
*/
while (small.Count > 0)
_probability[small.Pop()] = 1.0;
while (large.Count > 0)
_probability[large.Pop()] = 1.0;
}

/**
* Samples a value from the underlying distribution.
*
* @return A random value sampled from the underlying distribution.
*/
public int next()
{

long tick = DateTime.Now.Ticks;
var seed = ((int)(tick & 0xffffffffL) | (int)(tick >> 32));
unchecked
{
seed = (seed + Guid.NewGuid().GetHashCode() + new Random().Next(0, 100));
}
var random = new Random(seed);
int column = random.Next(_probability.Length);

/* Generate a biased coin toss to determine which option to pick. */
bool coinToss = random.NextDouble() < _probability[column];

return coinToss ? column : _alias[column];
}
}
}
```

## 二、Alias Method概率抽奖算法的PHP实现

```<?php
class AliasMethod
{
private \$length;
private \$prob_arr;
private \$alias;

public function __construct (\$pdf)
{
\$this->length = 0;
\$this->prob_arr = \$this->alias = array();
\$this->_init(\$pdf);
}
private function _init(\$pdf)
{
\$this->length = count(\$pdf);
if(\$this->length == 0)
die("pdf is empty");
if(array_sum(\$pdf) != 1.0)
die("pdf sum not equal 1, sum:".array_sum(\$pdf));

\$small = \$large = array();
\$average=1.0/\$this->length;
for (\$i=0; \$i < \$this->length; \$i++)
{
\$pdf[\$i] *= \$this->length;
if(\$pdf[\$i] < \$average)
\$small[] = \$i;
else
\$large[] = \$i;
}

while (count(\$small) != 0 && count(\$large) != 0)
{
\$s_index = array_shift(\$small);
\$l_index = array_shift(\$large);
\$this->prob_arr[\$s_index] = \$pdf[\$s_index]*\$this->length;
\$this->alias[\$s_index] = \$l_index;

\$pdf[\$l_index] += \$pdf[\$s_index]-\$average;
if(\$pdf[\$l_index] < \$average)
\$small[] = \$l_index;
else
\$large[] = \$l_index;
}

while(!empty(\$small))
\$this->prob_arr[array_shift(\$small)] = 1.0;
while (!empty(\$large))
\$this->prob_arr[array_shift(\$large)] = 1.0;
}
public function next_rand()
{
\$column = mt_rand(0, \$this->length - 1);
return mt_rand() / mt_getrandmax() < \$this->prob_arr[\$column] ? \$column : \$this->alias[\$column];
}
}
?>  ```

## 三、Alias Method概率抽奖算法的Java实现

```package com.lanhusoft.rsaapp;

import android.util.Log;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public final class AliasMethod {
/* The random number generator used to sample from the distribution. */
private final Random random;

/* The probability and alias tables. */
private final int[] alias;
private final double[] probability;

/**
* Constructs a new AliasMethod to sample from a discrete distribution and
* hand back outcomes based on the probability distribution.
* <p/>
* Given as input a list of probabilities corresponding to outcomes 0, 1,
* ..., n - 1, this constructor creates the probability and alias tables
* needed to efficiently sample from this distribution.
*
* @param probabilities The list of probabilities.
*/
public AliasMethod(List<Double> probabilities) {
this(probabilities, new Random());
}

/**
* Constructs a new AliasMethod to sample from a discrete distribution and
* hand back outcomes based on the probability distribution.
* <p/>
* Given as input a list of probabilities corresponding to outcomes 0, 1,
* ..., n - 1, along with the random number generator that should be used
* as the underlying generator, this constructor creates the probability
* and alias tables needed to efficiently sample from this distribution.
*
* @param probabilities The list of probabilities.
* @param random        The random number generator
*/
public AliasMethod(List<Double> probabilities, Random random) {
/* Begin by doing basic structural checks on the inputs. */
if (probabilities == null || random == null)
throw new NullPointerException();
if (probabilities.size() == 0)
throw new IllegalArgumentException("Probability vector must be nonempty.");

/* Allocate space for the probability and alias tables. */
probability = new double[probabilities.size()];
alias = new int[probabilities.size()];

/* Store the underlying generator. */
this.random = random;

/* Compute the average probability and cache it for later use. */
final double average = 1.0 / probabilities.size();

/* Make a copy of the probabilities list, since we will be making
* changes to it.
*/
probabilities = new ArrayList<Double>(probabilities);

/* Create two stacks to act as worklists as we populate the tables. */
Deque<Integer> small = new ArrayDeque<Integer>();
Deque<Integer> large = new ArrayDeque<Integer>();

/* Populate the stacks with the input probabilities. */
for (int i = 0; i < probabilities.size(); ++i) {
/* If the probability is below the average probability, then we add
* it to the small list; otherwise we add it to the large list.
*/
if (probabilities.get(i) >= average)
else
}

/* As a note: in the mathematical specification of the algorithm, we
* will always exhaust the small list before the big list.  However,
* due to floating point inaccuracies, this is not necessarily true.
* Consequently, this inner loop (which tries to pair small and large
* elements) will have to check that both lists aren't empty.
*/
while (!small.isEmpty() && !large.isEmpty()) {
/* Get the index of the small and the large probabilities. */
int less = small.removeLast();
int more = large.removeLast();

/* These probabilities have not yet been scaled up to be such that
* 1/n is given weight 1.0.  We do this here instead.
*/
probability[less] = probabilities.get(less) * probabilities.size();
alias[less] = more;

/* Decrease the probability of the larger one by the appropriate
* amount.
*/
probabilities.set(more,
(probabilities.get(more) + probabilities.get(less)) - average);

/* If the new probability is less than the average, add it into the
* small list; otherwise add it to the large list.
*/
if (probabilities.get(more) >= 1.0 / probabilities.size())
else
}

/* At this point, everything is in one list, which means that the
* remaining probabilities should all be 1/n.  Based on this, set them
* appropriately.  Due to numerical issues, we can't be sure which
* stack will hold the entries, so we empty both.
*/
while (!small.isEmpty())
probability[small.removeLast()] = 1.0;
while (!large.isEmpty())
probability[large.removeLast()] = 1.0;
}

/**
* Samples a value from the underlying distribution.
*
* @return A random value sampled from the underlying distribution.
*/
public int next() {
/* Generate a fair die roll to determine which column to inspect. */
int column = random.nextInt(probability.length);

/* Generate a biased coin toss to determine which option to pick. */
boolean coinToss = random.nextDouble() < probability[column];

/* Based on the outcome, return either the column or its alias. */
/* Log.i("1234","column="+column);
Log.i("1234","coinToss="+coinToss);
Log.i("1234","alias[column]="+coinToss);*/
return coinToss ? column : alias[column];
}

public static void main(String[] args) {
TreeMap<String, Double> map = new TreeMap<String, Double>();
map.put("1金币", 0.2);
map.put("2金币", 0.15);
map.put("3金币", 0.1);
map.put("4金币", 0.05);
map.put("未中奖", 0.5);

List<Double> list = new ArrayList<Double>(map.values());
List<String> gifts = new ArrayList<String>(map.keySet());

AliasMethod method = new AliasMethod(list);

Map<String, AtomicInteger> resultMap = new HashMap<String, AtomicInteger>();

for (int i = 0; i < 100000; i++) {
int index = method.next();
String key = gifts.get(index);
if (!resultMap.containsKey(key)) {
resultMap.put(key, new AtomicInteger());
}
resultMap.get(key).incrementAndGet();
}
for (String key : resultMap.keySet()) {
System.out.println(key + "==" + resultMap.get(key));
}

}
}```

http://blog.csdn.net/sky_zhe/article/details/10051967 