Alias随机算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Alias随机算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4414字,纯文字阅读大概需要7分钟。
内容图文
![Alias随机算法](/upload/InfoBanner/zyjiaocheng/649/81460edd9b734f94803d21eb3de96427.jpg)
1 /// <summary> 2 /// Alias别名算法 3 /// </summary> 4 public class AliasMethod 5 { 6 /* The probability and alias tables. */ 7 private int[] _alias; 8 private double[] _probability; 9 10 public AliasMethod(List<Double> probabilities) 11 { 12 13 /* Allocate space for the probability and alias tables. */ 14 _probability = new double[probabilities.Count]; 15 _alias = new int[probabilities.Count]; 16 17 /* Compute the average probability and cache it for later use. */ 18 double average = 1.0 / probabilities.Count; 19 20 /* Create two stacks to act as worklists as we populate the tables. */ 21 var small = new Stack<int>(); 22 var large = new Stack<int>(); 23 24 /* Populate the stacks with the input probabilities. */ 25 for (int i = 0; i < probabilities.Count; ++i) 26 { 27 /* If the probability is below the average probability, then we add 28 * it to the small list; otherwise we add it to the large list. 29 */ 30 if (probabilities[i] >= average) 31 large.Push(i); 32 else 33 small.Push(i); 34 } 35 36 /* As a note: in the mathematical specification of the algorithm, we 37 * will always exhaust the small list before the big list. However, 38 * due to floating point inaccuracies, this is not necessarily true. 39 * Consequently, this inner loop (which tries to pair small and large 40 * elements) will have to check that both lists aren't empty. 41 */ 42 while (small.Count > 0 && large.Count > 0) 43 { 44 /* Get the index of the small and the large probabilities. */ 45 int less = small.Pop(); 46 int more = large.Pop(); 47 48 /* These probabilities have not yet been scaled up to be such that 49 * 1/n is given weight 1.0. We do this here instead. 50 */ 51 _probability[less] = probabilities[less] * probabilities.Count; 52 _alias[less] = more; 53 54 /* Decrease the probability of the larger one by the appropriate 55 * amount. 56 */ 57 probabilities[more] = (probabilities[more] + probabilities[less] - average); 58 59 /* If the new probability is less than the average, add it into the 60 * small list; otherwise add it to the large list. 61 */ 62 if (probabilities[more] >= average) 63 large.Push(more); 64 else 65 small.Push(more); 66 } 67 68 /* At this point, everything is in one list, which means that the 69 * remaining probabilities should all be 1/n. Based on this, set them 70 * appropriately. Due to numerical issues, we can't be sure which 71 * stack will hold the entries, so we empty both. 72 */ 73 while (small.Count > 0) 74 _probability[small.Pop()] = 1.0; 75 while (large.Count > 0) 76 _probability[large.Pop()] = 1.0; 77 } 78 79 /** 80 * Samples a value from the underlying distribution. 81 * 82 * @return A random value sampled from the underlying distribution. 83 */ 84 public int next() 85 { 86 87 long tick = DateTime.Now.Ticks; 88 var seed = ((int)(tick & 0xffffffffL) | (int)(tick >> 32)); 89 unchecked 90 { 91 seed = (seed + Guid.NewGuid().GetHashCode() + new Random().Next(0, 100)); 92 } 93 var random = new Random(seed); 94 int column = random.Next(_probability.Length); 95 96 /* Generate a biased coin toss to determine which option to pick. */ 97 bool coinToss = random.NextDouble() < _probability[column]; 98 99 return coinToss ? column : _alias[column]; 100 } 101 }
初始化:
var alias = new AliasMethod(nList.Select(o => (double)o.probability).ToList());//初始化aliasMethod实例,传入概率List
使用:
var column = alias.next();//随机抽取,返回构造器传入概率List的索引
内容总结
以上是互联网集市为您收集整理的Alias随机算法全部内容,希望文章能够帮你解决Alias随机算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。