我怎样才能改进这种C#随机方法?
我认为我已经确定这是用于随机化列表的最简单且可unit testing的方法,但是有兴趣听到任何改进。
public static IList RandomiseList(IList list, int seed) { Random random = new Random(seed); List takeFrom = new List(list); List ret = new List(takeFrom.Count); while (takeFrom.Count > 0) { int pos = random.Next(0, takeFrom.Count - 1); T item = takeFrom[pos]; takeFrom.RemoveAt(pos); ret.Add(item); } return ret; }
你想要一个洗牌,最好的办法是Fisher-Yates shuffle:
public static IList Randomise (IList list, int seed) { Random rng = new Random(seed); List ret = new List (list); int n = ret.Length; while (n > 1) { n--; int k = rng.Next(n + 1); // Simple swap of variables T tmp = list[k]; ret[k] = ret[n]; ret[n] = tmp; } return ret; }
我喜欢Dennis Palmers想要返回一个洗牌的IEnumerable,而不是将列表放到适当位置,但是使用RemoveAt方法会让它变慢。 这是没有RemoveAt方法的替代方法:
public static IEnumerable Shuffle (IEnumerable list, int seed) { Random rnd = new Random(seed); List items = new List (list); for (int i = 0; i < items.Count; i++) { int pos = rnd.Next(i, items.Count); yield return items[pos]; items[pos] = items[i]; } }
我用10000整数来扼杀它,它的速度提高了大约30倍。
不确定这是多少改进,但如果列表很大并且您只需要前几个随机项就会有性能优势。
public static IEnumerable RandomiseList (IList list, int seed) { Random random = new Random(seed); List takeFrom = new List (list); while (takeFrom.Count > 0) { int pos = random.Next(0, takeFrom.Count - 1); T item = takeFrom[pos]; takeFrom.RemoveAt(pos); yield return item; } }
无需临时列表甚至临时交换变量。
如果我将要使用它很多,我会将其重写为扩展方法。
这对我来说很好看。 请注意,如果使用list
的长度初始化ret
,您将获得稍微更好的性能(特别是对于大型列表),因此不必重新分配列表:
List ret = new List (list.Count);
您正在寻找什么样的建议? 效率? 正确性? 你确实提到了unit testing……我认为那里肯定会有改进。
我实际上帮助开发了一个在线游戏和他们的改组机制。 我并不怀疑性能是一个很大的问题,因为你找到的大多数算法基本相同。 不过我建议如下,
一个。 创建一个随机界面
public interface IRandom { byte NextRandomByte (); }
现在,任何现在消耗此接口的东西都可以以受控方式或环境进行模拟或unit testing。 你真的不想真正随机算法进行unit testing – 你将无法validation你的数据!
至于为什么返回一个字节,一个字节很可能是你想要的最小的随机单位。 不仅如此,如果给出生成单个随机字节的方法,生成它们的序列并将它们连接在一起是生成更宽范围的随机数据的简单方法。
当然,您必须警惕对数据引入偏见……
湾 通过减少任意间隔的偏差来确保数据质量。 假设基础数据是均匀随机的,任何不是256的因子间隔都会引入偏差。 想想这个,
// 250 is not a factor of 256! byte a = random.NextRandomByte () % 250; // values 0-5 are biased!
在前面的片段中,值0-5的概率为2/255,而值6-249的概率为1/255。 这是一个重要的偏见。 一种方法是检查来自发电机的数量,如果超过可接受的范围则丢弃它
// continually generate random data until it is satisfactory for (byte r = random.NextRandomByte (); r > 250; r = random.NextRandomByte ()) { } byte a = r % 250; // r is guaranteed to be on [0, 250], no longer bias
“可接受的范围”可以通过找到您的区间的最大倍数来确定,该倍数可以由您的值类型表示。 一种更通用的forms
byte modulo; // specified as parameter byte biasThreshold = (byte.MaxValue / modulo) * modulo; for (; unbiasedValue >= biasThreshold; ) { // generate value unbiasedValue = random.NextRandomByte (); }
如果你想要大于byte的值,只需将值连接在一起,
int modulo; // specified as parameter int biasThreshold = (int.MaxValue / modulo) * modulo; for (; unbiasedValue >= biasThreshold; ) { // generate value byte a = random.NextRandomByte (); byte b = random.NextRandomByte (); ... int unbiasedValue = a << 24 + b << 16 + c << 8 + d; }
C。 消耗! 将算法或助手放在无状态扩展或静态类中,例如
// forgive my syntax, recalling from memory public static class IRandomExtensions { public int GetUnbiasedInteger (this IRandom random, int modulo) { } public int GetUnbiasedUnsignedInteger (this IRandom random, uint modulo) { } public int GetUnbiasedLong (this IRandom random, long modulo) { } public int GetUnbiasedUnsignedLong (this IRandom random, ulong modulo) { } ... } public static class IEnumerableExtensions { public IEnumerable Shuffle (this IEnumerable items, IRandom random) { // shuffle away! ... } }
决定是否在接口上实现这些方法或作为外部方法[就像我已经完成]取决于你 - 但请记住,使它们成为成员方法强制实现者重复或复制代码。 就个人而言,我喜欢扩展。 他们很干净。 而性感。
int randomNumber = random.UnbiasedInteger (i - 1); List shuffledNumbers = numbers.Shuffle (random);
显然,所有前提都是可选的,但有助于unit testing并提高随机数据的整体质量。
随机和“公平”骰子一般是一个非常有趣的话题。 如果你有兴趣,我强烈推荐你谷歌它,并进行一些研究。 🙂
没有统计数据可以支持这一点,但如果您的返回值以与列表相同长度的数组开始,然后将值直接插入随机生成的索引中,那么似乎会更好。
请注意天真洗牌算法的风险,看起来不错,但不耐受测试!
查看这篇优秀文章的示例。