我该如何改进这种随机方法?

你想洗牌,最好的方法是 Fisher-Yates 随机播放:

public static IList<T> Randomise<T>(IList<T> list, int seed) 
{
    Random rng = new Random(seed); 

    List<T> ret = new List<T>(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;
}

我喜欢丹尼斯·帕默斯返回经过洗牌的IEnumerable而不是原地洗牌列表的想法,但是使用removeat方法会使它变慢。这里有一个没有removeat方法的替代方法:

public static IEnumerable<T> Shuffle<T>(IEnumerable<T> list, int seed) {
  Random rnd = new Random(seed);
  List<T> items = new List<T>(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<T> RandomiseList<T>(IList<T> list, int seed)
{
    Random random = new Random(seed);
    List<T> takeFrom = new List<T>(list);

    while (takeFrom.Count > 0)
    {
        int pos = random.Next(0, takeFrom.Count - 1);
        T item = takeFrom[pos];
        takeFrom.RemoveAt(pos);
        yield return item;
    }
}

消除了对临时列表甚至临时交换变量的需要。

如果我要经常使用这个,我会把它重写为一个扩展方法。

我觉得这个不错。请注意,如果初始化 ret 长度为 list ,以便不必重新分配列表:

List<T> ret = new List<T>(list.Count);

你到底在寻找什么样的建议?效率?正确性?你提到了单元测试…我认为那里肯定会有改进。

我实际上帮助开发了一个在线游戏和他们的洗牌机制。我并不怀疑性能是个大问题,因为你发现的大多数算法大体上都是一样的。不过,我建议如下:

a.创建随机接口

public interface IRandom
{
    byte NextRandomByte ();
}

任何现在使用这个接口的东西现在都可以在一个受控的方式或环境中被模拟\单元测试。你真的不想成为真正的单元测试随机算法-你将无法验证你的数据!

至于为什么返回一个字节,一个字节很可能是随机性的最小单位。不仅如此,如果给定一种生成单个随机字节的方法,生成它们的序列并将它们连接在一起,则生成范围更广的随机数据的方法也很简单。

当然,你必须小心向你的数据引入偏见…

b.通过减少任意间隔的偏差来确保数据质量。假设基础数据是一致随机的,任何非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

“可接受范围”可以通过找到可以由值类型表示的间隔的最大倍数来确定。更广义的形式

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;
}

消费!将您的算法或助手放在无状态扩展或静态类中,比如

// 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<T> Shuffle<T>(this IEnumerable<T> items, IRandom random) 
    {
        // shuffle away!
        ...
    }

}

决定是否将这些方法作为接口上的方法或外部方法(如我所做的)实现取决于您——但请记住,使它们成为成员方法会强制实现者重复或复制代码。就个人而言,我喜欢扩展。它们很干净。性感。

int randomNumber = random.UnbiasedInteger (i - 1);
List<int> shuffledNumbers = numbers.Shuffle (random);

显然,所有前面的方法都是可选的,但是有助于单元测试并提高随机数据的整体质量。

一般来说,随机和“公平”骰子是一个非常有趣的话题。如果你有兴趣的话,我强烈建议你找个时间谷歌一下,做些调查。:)

没有统计数据来支持这一点,但是如果返回值以与列表长度相同的数组开始,然后将值直接插入随机生成的索引中,会更好。

要意识到幼稚洗牌算法的风险,那看起来不错,但经得起考验!

检查这个 excellent article 举个例子。