数组包含性能

我有一个与数组一起工作的程序,在某些时候我必须检查一个值是否在数组中,这个函数占用了大约70%的程序CPU时间,所以我想知道是否有办法更有效地做到这一点。

这些是我的function:

private static int[] GenerateRow(int length, Random RNG) { int[] row = InitalizeRow(length); int index = 0; while (!AreAllNumbersGenerated(row)) { int value = RNG.Next(0, length); if (!RowContains(row, value)) { row[index] = value; index++; } } return row; } private static bool AreAllNumbersGenerated(int[] row) { for (int i = 0; i < row.Length; i++) if(!RowContains(row, i)) return false; return true; } private static bool RowContains(int[] row, int value) { for (int i = 0; i < row.Length; i++) if (row[i] == value) return true; return false; } 

所有的工作都是由AreAllNumbersGenerated() ,然后是RowContains() ,最后是这一行:

if (row[i] == value)

这个function大部分时间都是正常的,因为他们做了大量的工作,但我想知道是否有更好的方法来做到这一点。

编辑:

  private static int[] InitalizeRow(int length) { int[] row = new int[length]; for (int i = 0; i < length; i++) row[i] = -1; return row; } 

通过对整个arrays中的每个数字进行线性扫描,你会浪费大量的工作。 你应该做的是走一次数组并开始观察你看过的最后一个数字。 如果您看到任何间隙,则返回false。 如果到达数组的末尾,则返回true。 这是O(N)而不是O(N ^ 2),就像你现在拥有它一样。

像这样:

 public static bool AreAllNumbersGenerated(int[] row) { var last = 0; return row.Aggregate(true, (l, r) => l && r == last++); } 

您可以进行一些额外的优化,这些优化不会影响您的大O复杂性,例如使用适当的循环和早期退出。

编辑:我在这里假设您期望项目按顺序发生。 如果不是这种情况,您可以轻松地将数组转换为O(N)中具有~O(1)查找的结构,然后也检查O(N)。 对于大输入,这仍然比上面的O(N ^ 2)方法更好

像这样:

 public static bool AreAllNumbersGenerated2(int[] row) { var available = row.ToDictionary(x => x); return Enumerable.Range(0, row.Length).All(i => available.ContainsKey(i)); } 

编辑:从我在评论中看到的,看起来这个代码的目标是以随机顺序填充具有连续数字序列的数组。 我没有意识到这是目标,如果是这样的话,改组肯定比重新尝试一遍又一遍地更好。 但是,比生成数组更好的是,然后改组(再次,对于足够大的输入)是通过将每个数字分配给随机采样的索引而不进行替换来简单地生成数组。 LINQ并不容易,但你可以搞清楚。

正如评论中的其他人指出的那样,最有效的方法是生成一个包含所需值的数组并将其随机化:

 public static void Shuffle(T[] arr, Random r) { for (int i = arr.Length - 1; i > 0; --i) { int j = r.Next(i + 1); T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } public static int[] Generate(int length, Random r) { var arr = new int[length]; for(int i = 0; i < length; ++i) { arr[i] = i; } Shuffle(arr, r); return arr; } 

然后

 var arr = Generate(10, new Random()); foreach (int i in arr) { Console.WriteLine(i); } 

我找到了一个方法,感谢@ sous2817评论,这对我来说非常有用

 public static int[] GetRandomNumbers(int count, Random RNG) { HashSet randomNumbers = new HashSet(); for (int i = 0; i < count; i++) while (!randomNumbers.Add(RNG.Next(count))) ; return randomNumbers.ToArray(); } 

这比我正在做的工作快10倍,并且与我的程序的其余部分很好地配合。我需要代码是“线性的”,所以其他解决方案会弄乱我的程序。 无论如何,感谢所有帮助过的人:)

您可以在列表中生成可能的值,并在随机位置获取值,而不是随机播放。 这样,您甚至可以在生成整行之前开始使用这些项:

  IEnumerable RandomRange(int count) { var random = new Random(); var list = new int[count]; for (int i = 0; i < count; i++) list[i] = i; while (count > 0) { var i = random.Next(count); yield return list[i] ; list[i] = list[--count]; } } 

样品使用:

 foreach(var item in RandomRange(10)) // ...