使用.NET随机化数组的最佳方法
用.NET随机化string数组的最佳方法是什么? 我的数组包含大约500个string,我想用相同的string,但随机顺序创build一个新的Array
。
请在答案中包含C#示例。
如果你使用.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)
第二次编辑,作为对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]); }
以下实现使用Fisher-Yatesalgorithm 。 它运行在O(n)的时间和洗牌,所以比“随机sorting”技术更好的performance,尽pipe它是更多的代码行。 看到这里的一些比较性能测量。 我已经使用System.Random,这是非encryption的目的。
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}; new Random().Shuffle(array);
*对于较长的数组,为了使(极大)数量的置换具有相同的可能性,有必要通过多次迭代运行伪随机数生成器(PRNG)来产生足够的熵。 对于一个500个元素的数组,只有可能的500个很小的一部分! 排列将有可能使用PRNG获得。 不过,Fisher-Yatesalgorithm是没有偏见的,因此洗牌将与您使用的RNG一样好。
你正在寻找一个洗牌algorithm,对吧?
好的,有两种方法可以做到这一点:聪明但是人们总是看起来似乎误会了它是错误的所以可能它不那么聪明方式,和愚蠢作为岩石,但谁关心,因为它的工作方式。
愚蠢的方式
- 创build你的第一个数组的副本,但标记每个string应该随机数字。
- 根据随机数对重复数组进行sorting。
这个algorithm效果很好,但要确保你的随机数发生器不太可能用相同的数字来标记两个string。 由于所谓的生日悖论 ,这种情况比你想像的要多得多。 它的时间复杂度是O( n log n )。
聪明的方法
我将这个描述为recursionalgorithm:
要对大小为n的数组(范围[0 .. n -1]中的索引)进行混洗:
如果n = 0
- 没做什么
如果n > 0
- (recursion步骤)将数组的前n -1个元素进行混洗
- select一个随机索引x ,范围[0 .. n -1]
- 将索引n -1处的元素与索引x处的元素交换
迭代的等价物是在数组中遍历一个迭代器,随意交换随机元素,但是请注意,在迭代器指向的元素之后不能交换元素。 这是一个非常普遍的错误,并导致了一个有偏见的洗牌。
时间复杂度是O( n )。
该algorithm简单但效率不高,O(N 2 )。 所有的“order by”algorithm通常是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 2 )之所以微妙,是因为List.RemoveAt()是一个O(N)操作,除非从末尾开始顺序移除。
你也可以从马特·霍威尔斯(Matt Howells)中提出一个扩展方法。 例。
namespace System { public static class MSSystemExtenstions { private static Random rng = new Random(); public static void Shuffle<T>(this T[] array) { rng = new Random(); int n = array.Length; while (n > 1) { int k = rng.Next(n); n--; T temp = array[n]; array[n] = array[k]; array[k] = temp; } } } }
那么你可以像这样使用它:
string[] names = new string[] { "Aaron Moline1", "Aaron Moline2", "Aaron Moline3", "Aaron Moline4", "Aaron Moline5", "Aaron Moline6", "Aaron Moline7", "Aaron Moline8", "Aaron Moline9", }; names.Shuffle<string>();
随机数组是密集的,因为你必须转移一堆string。 为什么不从数组中随机读取? 在最坏的情况下,你甚至可以使用getNextString()创build一个包装类。 如果你确实需要创build一个随机数组,那么你可以做类似的事情
for i = 0 -> i= array.length * 5 swap two strings in random places
* 5是任意的。
只要想想我的头顶,你可以这样做:
public string[] Randomize(string[] input) { List<string> inputList = input.ToList(); string[] output = new string[input.Length]; Random randomizer = new Random(); int i = 0; while (inputList.Count > 0) { int index = r.Next(inputList.Count); output[i++] = inputList[index]; inputList.RemoveAt(index); } return (output); }
这篇文章已经被很好的回答了 – 使用Durstenfeld的Fisher-Yates shuffle实现一个快速和不偏不倚的结果。 甚至有一些实现发布,但我注意到有些实际上是不正确的。
我写了几篇文章,回顾一下使用这种技术实现全面和部分洗牌 ,以及(第二个链接是我希望增加价值的地方),还有关于如何检查您的实现是否无偏见的后续文章 ,它可以用来检查任何混洗algorithm。 你可以在第二篇文章末尾看到随机数select中的一个简单错误的效果。
生成相同长度的随机浮点数或整数数组。 对该数组进行sorting,然后在目标数组上进行相应的交换。
这产生了一个真正独立的sorting。
Random r = new Random(); List<string> list = new List(originalArray); List<string> randomStrings = new List(); while(list.Count > 0) { int i = r.Random(list.Count); randomStrings.Add(list[i]); list.RemoveAt(i); }
Jacco,你的解决scheme是一个自定义的IComparer是不安全的。 Sort例程要求比较器符合几个要求才能正常工作。 首先是一致性。 如果在同一对对象上调用比较器,则必须始终返回相同的结果。 (比较也必须是传递的)。
如果不能满足这些要求,可能会在分类程序中造成许多问题,包括无限循环的可能性。
关于将随机数字值与每个条目相关联,然后按该值进行sorting的解决scheme,这些会导致输出中存在内在偏见,因为任何时候两个条目都被赋予相同的数值,输出的随机性将受到损害。 (在一个“稳定的”sorting例程中,input中的第一个将是输出中的第一个.Array.Sort并不稳定,但仍然存在基于Quicksortalgorithm分区的偏差)。
你需要考虑一下你需要的随机性水平。 如果您正在运行一个需要encryption级别随机性的扑克站点来防止确定的攻击者,那么对于只想随机化歌曲播放列表的用户有着非常不同的要求。
对于歌曲列表混排,使用种子PRNG(如System.Random)没有问题。 对于一个扑克网站来说,这甚至不是一个选项,你需要考虑这个问题比任何人在你的计算器上都要困难得多。 (使用密码RNG只是一个开始,你需要确保你的algorithm不会引入偏差,你有足够的熵源,并且你不暴露任何内部状态,这将危及随后的随机性)。
好吧,这显然是我的一个障碍(道歉…),但我经常使用一个相当一般和密码强大的方法。
public static class EnumerableExtensions { static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider(); public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable) { var randomIntegerBuffer = new byte[4]; Func<int> rand = () => { RngCryptoServiceProvider.GetBytes(randomIntegerBuffer); return BitConverter.ToInt32(randomIntegerBuffer, 0); }; return from item in enumerable let rec = new {item, rnd = rand()} orderby rec.rnd select rec.item; } }
Shuffle()是任何IEnumerable的扩展,所以在列表中以随机顺序从0到1000的数字可以用
Enumerable.Range(0,1000).Shuffle().ToList()
这个方法在sorting时也不会带来任何意外,因为sorting值是按序列中的每个元素生成和记忆的。
你不需要复杂的algorithm。
只需简单的一行:
Random random = new Random(); array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();
请注意,如果首先不使用List
,则需要先将Array
转换为List
。
另外,请注意,这对于非常大的数组是无效的! 否则,它是干净和简单的。
这是一个基于此处提供的示例的完整工作控制台解决scheme:
class Program { static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" }; static void Main() { var result = Shuffle(words1); foreach (var i in result) { Console.Write(i + " "); } Console.ReadKey(); } static string[] Shuffle(string[] wordArray) { Random random = new Random(); for (int i = wordArray.Length - 1; i > 0; i--) { int swapIndex = random.Next(i + 1); string temp = wordArray[i]; wordArray[i] = wordArray[swapIndex]; wordArray[swapIndex] = temp; } return wordArray; } }
int[] numbers = {0,1,2,3,4,5,6,7,8,9}; List<int> numList = new List<int>(); numList.AddRange(numbers); Console.WriteLine("Original Order"); for (int i = 0; i < numList.Count; i++) { Console.Write(String.Format("{0} ",numList[i])); } Random random = new Random(); Console.WriteLine("\n\nRandom Order"); for (int i = 0; i < numList.Capacity; i++) { int randomIndex = random.Next(numList.Count); Console.Write(String.Format("{0} ", numList[randomIndex])); numList.RemoveAt(randomIndex); } Console.ReadLine();
这段代码在数组中混洗数字。
using System; // ... static void Main(string[] args) { Console.ForegroundColor = ConsoleColor.Cyan; int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; Shuffle(numbers); for (int i = 0; i < numbers.Length; i++) Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null)); Console.WriteLine(); string[] words = { "this", "is", "a", "string", "of", "words" }; Shuffle(words); for (int i = 0; i < words.Length; i++) Console.Write(words[i] + (i < words.Length - 1 ? ", " : null)); Console.WriteLine(); Console.ForegroundColor = ConsoleColor.Gray; Console.Write("Press any key to quit . . . "); Console.ReadKey(true); } static void Shuffle<T>(T[] array) { Random random = new Random(); for (int i = 0; i < array.Length; i++) { T temporary = array[i]; int intrandom = random.Next(array.Length); array[i] = array[intrandom]; array[intrandom] = temporary; } }
这是使用OLINQ的简单方法:
// Input array List<String> lst = new List<string>(); for (int i = 0; i < 500; i += 1) lst.Add(i.ToString()); // Output array List<String> lstRandom = new List<string>(); // Randomize Random rnd = new Random(); lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);
这是我的algorithm。 我们想随机化一个名为“ pole ”的数组,
List<int> vylosovane = new List<int>(); List<string> docasny = new List<string>(); int a = 0; for (int i = 0; i < pole.Length; i++) { a = nahoda.Next(0, pole.Length); if (vylosovane.Contains(a)) i--; else { docasny.Add(pole[a]); vylosovane.Add(a); } } pole = docasny.ToArray();
private ArrayList ShuffleArrayList(ArrayList source) { ArrayList sortedList = new ArrayList(); Random generator = new Random(); while (source.Count > 0) { int position = generator.Next(source.Count); sortedList.Add(source[position]); source.RemoveAt(position); } return sortedList; }