数组包含性能

本文关键字：性能 包含 数组 | 更新日期: 2023-09-27 18:05:02

我有一个与数组一起工作的程序，在某些时候我必须检查值的列表是否在数组内，这样做的函数大约需要70%的程序CPU时间，所以我想知道是否有一种方法可以更有效地做到这一点。

这些是我的功能:

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)

这些函数占用大部分时间是正常的，因为它们做了大量的工作，但是我想知道是否有更好的方法来做到这一点。

编辑:

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

数组包含性能

对整个数组中的每个数字进行线性扫描会浪费大量的工作。您应该做的是遍历数组一次，并开始观察您看到的最后一个数字。如果看到任何空白，则返回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>(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<int> randomNumbers = new HashSet<int>();
        for (int i = 0; i < count; i++)
            while (!randomNumbers.Add(RNG.Next(count))) ;
        return randomNumbers.ToArray();
    }

这比我所做的快10倍，并且与我的程序的其余部分一起工作得很好。我需要代码是"线性的"，这样其他解决方案就会扰乱我的程序。无论如何，感谢每个人的帮助:)

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

    IEnumerable<int> 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))
    // ...
相关文章：