使用.NET随机化数组的最佳方法

Question

使用.NET随机化字符串数组的最佳方法是什么？我的数组包含大约500个字符串,我想Array用随机顺序创建一个具有相同字符串的新字符串.

请在答案中加入C#示例.

Answer 1

以下实现使用Fisher-Yates算法.它在O(n)时间内运行并随机播放,因此比"随机排序"技术表现更好,尽管它是更多的代码行.请参阅此处了解一些比较性能测量.我使用过System.Random,非常适用于非加密目的.*

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

用法:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

*对于较长的数组,为了使(极大)数量的排列同样可能,有必要通过多次迭代为每个交换运行伪随机数生成器(PRNG)以产生足够的熵.对于500个元素的阵列,只有500个元素的一小部分!使用PRNG可以获得排列.然而,Fisher-Yates算法是无偏的,因此随机播放将与您使用的RNG一样好.

Answer 2

如果您使用的是.NET 3.5,则可以使用以下IEnumerable coolness(VB.NET,而不是C#,但这个想法应该很明确......):

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();    

编辑:好的,这是相应的VB.NET代码:

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()

第二次编辑,以响应由于返回基于时间的序列而使System.Random"不是线程安全"和"仅适用于玩具应用程序"的评论:如我的示例中所使用的,Random()完全是线程安全的,除非您允许重新输入数组随机化的例程,在这种情况下,您将需要类似的东西lock (MyRandomArray),以免损坏您的数据,这也将保护您的数据rnd.

此外,应该很好地理解System.Random作为熵源不是很强.如MSDN文档中所述,System.Security.Cryptography.RandomNumberGenerator如果您正在执行与安全性相关的任何操作,则应使用从中派生的内容.例如:

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

Answer 3

你正在寻找一种改组算法,对吧？

好吧,有两种方法可以做到这一点:聪明 - 但人 - 总是似乎误解 - 它 - 并且 - 它错了 - 所以 - 也许 - 它不是那么聪明 - 毕竟方式,和愚蠢的岩石,但谁关心,因为它的工作方式.

愚蠢的方式

• 创建第一个数组的副本,但标记每个字符串应该是一个随机数.
• 根据随机数对重复数组进行排序.

此算法运行良好,但请确保您的随机数生成器不太可能标记具有相同数字的两个字符串.由于所谓的生日悖论,这种情况比你想象的更频繁.其时间复杂度为O(n log n).

聪明的方式

我将其描述为递归算法:

要改组大小为n的数组(索引在[0 .. n -1] 范围内):

如果n = 0

• 没做什么

如果n > 0

• (递归步骤)混洗数组的前n -1个元素
• 选择[0 .. n -1] 范围内的随机索引x
• 将索引为n -1的元素与索引x处的元素交换

迭代等价物是通过数组遍历迭代器,随机交换随机元素,但请注意,在迭代器指向的元素之后,您不能与元素交换.这是一个非常常见的错误,并导致有偏见的洗牌.

时间复杂度为O(n).

Answer 4

该算法简单但效率不高,O(N ²).所有"order by"算法通常为O(N log N).它可能在数十万个元素下面没有区别,但它适用于大型列表.

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

它的O(N ²)之所以微妙:List.RemoveAt()是一个O(N)操作,除非你从结尾顺序删除.