二维数组搜索优化

Question

我编写了一段代码，用于查找二维数组中连续出现三个重复元素的行或列。

private static bool SearchInRows(int[,] matrix)
{
    int count = 1;
    int repeatElement = int.MaxValue;

    //Search in rows
    for (int i = 0; i < matrix.GetLength(0); i++)
    {
        repeatElement = matrix[i, 0];

        for (int j = 1; j < matrix.GetLength(1); j++)
        {
            if (repeatElement == matrix[i, j])
            {
                count++;
                if (count >= 3)
                {
                    Console.WriteLine($"Repeated elements are in positions i:{i}, j:{j - 2}, {j - 1}, {j}");
                    return true;
                }
            }
            else
            {
                repeatElement = matrix[i, j];
                count = 1;
            }
        }
    }
    return false;
}
private static bool SearchInCols(int[,] matrix)
{
    int count = 1;
    int repeatElement = int.MaxValue;

    //Search in cols
    for (int j = 0; j < matrix.GetLength(1); j++)
    {
        repeatElement = matrix[0, j];

        for (int i = 1; i < matrix.GetLength(0); i++)
        {
            if (repeatElement == matrix[i, j])
            {
                count++;
                if (count >= 3)
                {
                    Console.WriteLine($"Repeated elements are in positions j:{j}, i:{i-2}, {i-1}, {i}");
                    return true;
                }
            }
            else
            {
                repeatElement = matrix[i, j];
                count = 1;
            }
        }
    }
    return false;
}

这个功能可以正常工作，但我会做如下修改：

while (!SearchInRows(matrix) && !SearchInCols(matrix))
{
    SearchInRows(matrix);
    SearchInCols(matrix);
    //modify the matrix
}

我正在思考是否可以采用某种方式来提高代码的性能，比如在每个方法上添加Task.Run之类的操作（我已将该方法分割成列和行）。

- Palamar66

---

一个巨大的性能提升可以通过“缓存”结果来实现，目前在每次迭代中您都会调用 SearchInRows 和 SearchInCols 两次，而您只需要调用每个一次并将结果保存在本地变量中以便重复使用。 - MindSwipe

你可以将它们合并为一个方法，并比较二维数组中每个选定元素的右侧和底部的元素，如果它们匹配，则再次执行。由于您当前正在对每个元素进行两次迭代，因此可以减少要迭代的元素数量一半... - dan-kli

@dan-kli 不用了，我想我不应该删除它们，因为它们可以形成一行重复，抱歉打扰了，谢谢你的帮助。 - Palamar66

啊，那很有道理。你可以使用两个数组SkippedColumnCells和SkippedRowCells，其中包含这些单元格的数组位置，并跳过它们的比较，但这几乎不会提高性能，因为现在你将进行额外的数组比较并跳过某些单元格的比较。尽管如此，我认为我描述的实现方式更加高效，即使你检查某些单元格两次，因为你要对每个单元格进行两次迭代（而且根据你使用while函数调用方法的方式，实际上是4次）。 - dan-kli

回复您之前的评论。我认为您之前所说的是正确的，理论上可以跳过对已经有两个重复数字且第三个数字不匹配的情况进行检查，但这些信息也必须存储并从某处调用，这又会降低性能... - dan-kli

Answer 1

您的问题有更高效的解决方案，因为您的函数实质上需要对每个元素进行两次迭代（一次用于列，一次用于行）。而且，根据您调用函数的方式，您甚至还需要更多的迭代。

以下是我想出的更有效的解决方案，但可能还有更好的解决方案。基本上，我只对每个元素迭代一次，并检查列和行中下两个元素是否匹配。例如，让我们看下面这个8x8的二维数组。我只迭代红色框中的每个元素，并检查行/列中接下来的两个元素是否匹配。这留下了两行和两列未经检查，我必须单独检查它们。

这是代码：

private static void FindThreeRepeatedElements(int[,] matrix)
{
    // iterate once trough each element (red box) and check
    // if the next 2 elements in the row / column match
    for(int row = 0; row < matrix.GetLength(0) - 2; row++)
    {
        for (int column = 0; column < matrix.GetLength(1) - 2; column++)
        {
            CheckRow(matrix, row, column);
            CheckColumn(matrix, row, column);
        }
    }

    // check the last remaining 2 rows
    CheckRow(matrix, matrix.GetLength(0) - 2, matrix.GetLength(0) - 3);
    CheckRow(matrix, matrix.GetLength(0) - 1, matrix.GetLength(0) - 3);

    // check the last remaining 2 columns
    CheckColumn(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 2);
    CheckColumn(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 1);
}

private static void CheckRow(int[,] matrix, int row, int column)
{
    int element = matrix[row, column];
    if (element == matrix[row, column + 1] && element == matrix[row, column + 2])
    {
        Console.WriteLine($"Three repeated elements with value {element} are found in row {row} at the positions: [{row}, {column}], [{row}, {column + 1}], [{row}, {column + 2}]");
    }
}

private static void CheckColumn(int[,] matrix, int row, int column)
{
    int element = matrix[row, column];
    if(element == matrix[row + 1, column] && element == matrix[row + 2, column])
    {
        Console.WriteLine($"Three repeated elements with value {element} are found in column {column} at the positions: [{row}, {column}], [{row + 1}, {column}], [{row + 2}, {column}]");
    }
}

正如你在评论中指出的那样，有些情况下可以跳过某些元素的检查，因为它们已经在之前被检查过了。例如，如果我们再次看一下8x8二维数组，在比较蓝色框中的元素后，我们发现前两个元素匹配（都具有值7），因此我们检查第三个元素是否也具有值7，但是失败了（它具有值4）。现在我们已经知道可以跳过该行中接下来的三个元素的检查（橙色框），因为当我们到达具有值7、4和5的元素时，我们已经在上一次迭代中比较了前两个元素。

我修改了上面的代码，跳过了那些比较，这样留下了更多的代码但技术上少了比较（不确定它实际上是否更具性能）。在这个例子中，在蓝色框中进行比较后，布尔值 _skipNextRowCheck 将变为 true，这将完全跳过检查橙色框中的 3 个元素是否具有相等的值。

以下是修改后的代码：

private static bool _skipNextRowCheck = false;
private static bool _skipNextColumnCheck = false;

private static void FindThreeRepeatedElementsWithSkips(int[,] matrix)
{
    // iterate trough each element and check
    // if the next 2 elements in the row / column match
    for (int row = 0; row < matrix.GetLength(0) - 2; row++)
    {
        for (int column = 0; column < matrix.GetLength(1) - 2; column++)
        {
            CheckRowWithSkips(matrix, row, column);
            CheckColumnWithSkips(matrix, row, column);
        }
    }

    // check the last remaining 2 rows
    CheckRowWithSkips(matrix, matrix.GetLength(0) - 2, matrix.GetLength(0) - 3);
    CheckRowWithSkips(matrix, matrix.GetLength(0) - 1, matrix.GetLength(0) - 3);

    // check the last remaining 2 columns
    CheckColumnWithSkips(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 2);
    CheckColumnWithSkips(matrix, matrix.GetLength(0) - 3, matrix.GetLength(0) - 1);
}

private static void CheckRowWithSkips(int[,] matrix, int row, int column)
{
    if(_skipNextRowCheck)
    {
        _skipNextRowCheck = false;
        return;
    }

    int element = matrix[row, column];
    if (element == matrix[row, column + 1])
    {
        if(element == matrix[row, column + 2])
        {
            Console.WriteLine($"Three repeated elements with value {element} are found in row {row} at the positions: [{row}, {column}], [{row}, {column + 1}], [{row}, {column + 2}]");
        }
        else
        {
            _skipNextRowCheck = true;
        }
    }
}

private static void CheckColumnWithSkips(int[,] matrix, int row, int column)
{
    if (_skipNextColumnCheck)
    {
        _skipNextColumnCheck = false;
        return;
    }

    int element = matrix[row, column];
    if (element == matrix[row + 1, column])
    {
        if(element == matrix[row + 2, column])
        {
            Console.WriteLine($"Three repeated elements with value {element} are found in column {column} at the positions: [{row}, {column}], [{row + 1}, {column}], [{row + 2}, {column}]");
        }
        else
        {
            _skipNextColumnCheck = true;
        }
    }
}

这里是一个包含图片的2D数组的主函数，只需将主函数和所有其他函数复制到一个Program类中尝试它：

static void Main(string[] args)
{
    int[,] matrix = new int[8, 8] 
    { 
        { 7, 7, 7, 4, 5, 6, 1, 8 },
        { 1, 4, 3, 4, 3, 9, 3, 8 },
        { 1, 2, 3, 4, 3, 6, 7, 8 },
        { 1, 4, 7, 4, 5, 4, 7, 8 },
        { 1, 2, 3, 4, 5, 5, 3, 5 },
        { 1, 1, 1, 7, 5, 9, 9, 9 },
        { 1, 2, 7, 6, 5, 9, 9, 9 },
        { 1, 2, 3, 4, 5, 9, 9, 9 },
    };

    Console.WriteLine("\nSearching for three repeated elements in the 2d array:");
    FindThreeRepeatedElements(matrix);

    Console.WriteLine("\nSearching for three repeated elements in the 2d array, and skipping unneccessary comparisons:");
    FindThreeRepeatedElementsWithSkips(matrix);
}

- dan-kli