使用.NET的最佳方法对数组进行随机排序。

14 浏览
0 Comments

使用.NET的最佳方法对数组进行随机排序。

如何在.NET中将字符串数组随机排序是最佳方法？我的数组包含约500个字符串，我想创建一个新的Array，其中包含相同的字符串，但顺序是随机的。\n请在您的回答中包含一个C＃示例。

0

3 答案

0 Comments

在这段内容中，作者讨论了对一个数组进行随机排序的两种方法，而问题是关于在.NET中如何最好地对数组进行随机排序。

第一种方法是“愚蠢的方式”，具体步骤如下：

1. 创建一个原数组的副本，并为每个元素附加一个随机数。

2. 根据随机数对副本数组进行排序。

这种方法的时间复杂度为O(nlogn)，但需要确保随机数生成器不太可能给两个元素附加相同的随机数，因为由于所谓的“生日悖论”，这种情况比你预期的要经常发生。

第二种方法是“聪明的方式”，以递归算法的形式描述如下：

1. 对于一个大小为n的数组（索引范围为[0..n-1]）：

- 如果n=0，则什么也不做。

- 如果n>0，则：

- 递归地对数组的前n-1个元素进行随机排序。

- 在范围[0..n-1]内选择一个随机索引x。

- 将索引为n-1的元素与索引为x的元素交换位置。

这种方法的时间复杂度为O(n)。也可以用迭代的方式实现，通过遍历数组并在遍历过程中与随机元素交换位置，但需要注意的是不能与迭代器指向的元素之后的元素交换，否则会导致偏向性的随机排序。

因此，根据作者的讨论，我们可以得出结论，对于.NET中对数组进行随机排序的最佳方法是使用“聪明的方式”，即通过递归或迭代地对数组进行随机排序。

0
0 Comments

问题的原因是在使用.NET时，需要对数组进行随机化。为了解决这个问题，可以使用LINQ中提供的Shuffle方法。首先，将下面的代码添加到名为"EnumerableExtensions.cs"的文件中：

public static class EnumerableExtensions
{
    public static IList Shuffle(this IEnumerable sequence)
    {
        return sequence.Shuffle(new Random());
    }
    
    public static IList Shuffle(this IEnumerable sequence, Random randomNumberGenerator)
    {
        if (sequence == null)
        {
            throw new ArgumentNullException("sequence");
        }
        if (randomNumberGenerator == null)
        {
            throw new ArgumentNullException("randomNumberGenerator");
        }
        T swapTemp;
        List values = sequence.ToList();
        int currentlySelecting = values.Count;
        while (currentlySelecting > 1)
        {
            int selectedElement = randomNumberGenerator.Next(currentlySelecting);
            --currentlySelecting;
            if (currentlySelecting != selectedElement)
            {
                swapTemp = values[currentlySelecting];
                values[currentlySelecting] = values[selectedElement];
                values[selectedElement] = swapTemp;
            }
        }
        return values;
    }
}

这段代码是对Fisher-Yates算法的一个实现，它可以对数组进行随机化。在使用C# 7.0或更高版本时，可以使用下面的代码：

var rnd = new Random();
var myRandomArray = myArray
    .Select(x => (x, rnd.Next()))
    .OrderBy(tuple => tuple.Item2)
    .Select(tuple => tuple.Item1)
    .ToArray();

这段代码会为每个元素生成一个随机数，然后按照随机数排序。需要注意的是，这种方法在处理大量元素时速度较慢。此外，之前的一种实现方式`.OrderBy(x => random())`是错误的，应该使用Fisher-Yates算法。

在使用Visual Basic或早于C# 7.0的版本时，应该使用Fisher-Yates算法。这种方法比使用LINQ实现更为繁琐，但是可以得到更好的随机化效果。

需要注意的是，System.Random类不是线程安全的，且基于时间。如果在高并发系统中使用此代码，可能会出现两个请求获得相同值的情况。另外，System.Random类应该仅用于小型应用程序。

总之，为了实现对数组的随机化，最好使用Fisher-Yates算法而不是其他不可靠的方法。

0
0 Comments

最佳方法来使用.NET随机化数组的问题的出现原因是为了提供一个高效的随机化算法。解决方法是使用Fisher-Yates算法，该算法在O(n)的时间内原地进行洗牌，因此比“按随机排序”技术具有更好的性能。以下是解决方法的具体实现：

static class RandomExtensions
{
    public static void Shuffle (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); // 不同于第一次调用Shuffle的顺序

对于更长的数组，为了使（极大数量的）排列等概率出现，需要对伪随机数生成器（PRNG）进行多次迭代以产生足够的熵。对于一个500个元素的数组，使用PRNG只有非常小的一部分可能得到500！种排列。尽管如此，Fisher-Yates算法是无偏的，因此洗牌的质量取决于所使用的随机数生成器的质量。

有人提出是否可以改变参数，使用起来像`array.Shuffle(new Random());`。然而，这样做是不好的，原因是`new Random()`是根据当前系统时间生成的种子值，而系统时间只会每16毫秒更新一次。

还有人提出可以使用元组来简化交换操作，例如`(array[n], array[k]) = (array[k], array[n]);`。这个方法在4.0版本的框架中是可行的。

在对比了使用列表的removeAt解决方案后，对999个元素进行了简单的测试。在99999个随机整数的情况下，这种解决方案只需要3毫秒，而另一种解决方案需要1810毫秒。

0