c# - 二维数组搜索优化

Question

我写了一段代码，以便在二维数组的行/列中找到 3 个重复的元素。

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 或其他东西(我为此将方法拆分为 cols 和 rows)。

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 的元素时，我们已经在前一个元素中对前两个元素进行了比较迭代。

我修改了上面的代码以跳过这些比较，这给我们留下了更多的代码，但在技术上比较更少(不确定它是否真的更高效)。在此示例中，bool _skipNextRowCheck 在蓝色框中进行比较后将为真，这将完全跳过检查橙色框中的 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;
        }
    }
}

这里是一个带有图片二维数组的主函数，只需将主函数和所有其他函数复制到一个 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);
}