c# - 数组包含性能

Question

我有一个使用数组的程序，在某些时候我必须检查数组中是否有 lsit 值，执行此操作的函数大约占用了程序 CPU 时间的 70%，所以我想知道是否有一种更有效地做到这一点的方法。

这些是我的功能:

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;
    }

Answer 1

对整个数组中的每个数字进行线性扫描会浪费大量工作。相反，您应该做的是遍历数组一次并开始观察您看到的最后一个数字。如果您看到任何差距，请返回 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 不太容易解决，但您可以解决。