algorithm - 如何最有效地在矩阵中找到给定大小的等值矩形区域？

Question

我的问题很简单，但是我还没有找到有效的实现方法。

假设有一个像这样的矩阵A:

0 0 0 0 0 0 0
4 4 2 2 2 0 0
4 4 2 2 2 0 0
0 0 2 2 2 1 1
0 0 0 0 0 1 1

现在，我想找到此矩阵中具有给定大小的矩形区域的所有起始位置。区域是A的子集，其中所有数字均相同。

假设width = 2和height = 3。有3个区域具有此大小:

2 2   2 2   0 0
2 2   2 2   0 0
2 2   2 2   0 0

函数调用的结果将是这些区域的起始位置(x，y以0开头)的列表。

List((2,1),(3,1),(5,0))

以下是我当前的实现。 “区域”在这里称为“表面”。

case class Dimension2D(width: Int, height: Int)
case class Position2D(x: Int, y: Int)

def findFlatSurfaces(matrix: Array[Array[Int]], surfaceSize: Dimension2D): List[Position2D] = {

    val matrixWidth = matrix.length
    val matrixHeight = matrix(0).length
    var resultPositions: List[Position2D] = Nil

    for (y <- 0 to matrixHeight - surfaceSize.height) {
        var x = 0
        while (x <= matrixWidth - surfaceSize.width) {
            val topLeft = matrix(x)(y)
            val topRight = matrix(x + surfaceSize.width - 1)(y)
            val bottomLeft = matrix(x)(y + surfaceSize.height - 1)
            val bottomRight = matrix(x + surfaceSize.width - 1)(y + surfaceSize.height - 1)
            // investigate further if corners are equal
            if (topLeft == bottomLeft && topLeft == topRight && topLeft == bottomRight) {
                breakable {
                    for (sx <- x until x + surfaceSize.width;
                         sy <- y until y + surfaceSize.height) {
                        if (matrix(sx)(sy) != topLeft) {
                            x = if (x == sx) sx + 1 else sx 
                            break
                        }
                    }
                    // found one!       
                    resultPositions ::= Position2D(x, y)
                    x += 1
                }
            } else if (topRight != bottomRight) {
                // can skip x a bit as there won't be a valid match in current row in this area
                x += surfaceSize.width 
            } else {
                x += 1
            }
        }   
    }
    return resultPositions
}

我已经尝试在其中进行一些优化，但是我确信有更好的解决方案。我可以移植一个matlab函数吗？我也想知道这个问题是否有自己的名字，因为我不知道该怎么做。

感谢您的考虑!我很高兴看到您的建议或解决方案:)

编辑:我的应用程序中的矩阵尺寸范围大约为300x300至3000x3000。同样，对于同一矩阵，该算法将仅被调用一次。原因是矩阵之后总是会更改(大约是矩阵的1-20％)。

结果

我实现了Kevin，Nikita和Daniel的算法，并在我的应用程序环境中对它们进行了基准测试，即这里没有孤立的综合基准测试，但是要特别注意以其最高性能的方式集成所有算法，这对于Kevin的方法使用泛型而言尤其重要。 (见下文)。

首先，使用Scala 2.8和jdk 1.6.0_23，获得原始结果。作为解决特定于应用程序的问题的一部分，算法被执行了数百次。 “持续时间”表示直到应用程序算法完成(当然没有jvm启动等)所需的总时间。我的机器是一个2.8GHz Core 2 Duo，具有2个内核和2gig的内存，-Xmx800M被分配给了JVM。

重要说明:我认为我的基准测试设置对于像Daniel那样的并行算法并不十分公平。这是因为应用程序已经在计算多线程。因此，这里的结果可能仅显示与单线程速度相当的结果。

矩阵大小233x587:

                  duration | JVM memory | avg CPU utilization
original O(n^4) | 3000s      30M          100%  
original/-server| 840s       270M         100%
Nikita O(n^2)   | 5-6s       34M          70-80%
Nikita/-server  | 1-2s       300M         100%
Kevin/-server   | 7400s      800M         96-98%
Kevin/-server** | 4900s      800M         96-99%
Daniel/-server  | 240s       360M         96-99%

**使用@specialized，通过避免类型擦除来制作generics faster

矩阵尺寸2000x3000:

                  duration | JVM memory | avg CPU utilization
original O(n^4) | too long   100M         100%  
Nikita O(n^2)   | 150s       760M         70%
Nikita/-server  | 295s (!)   780M         100%
Kevin/-server   | too long, didn't try

首先，请注意一下内存。 -server JVM选项使用大量内存，这是因为可以进行更多优化，并且通常可以更快地执行。从第二张表可以看出，使用-server选项，Nikita的算法速度较慢，这显然是由于达到了内存限制。我认为即使对于较小的矩阵，这也会减慢Kevin的算法的速度，因为函数方法无论如何都会使用更多的内存。为了消除内存因素，我还使用50x50矩阵尝试了一次，然后Kevin花费了5秒，Nikita花费了0秒(嗯，几乎为0)。因此，无论如何，它仍然较慢，而不仅仅是内存。

从数字中可以看出，我显然会使用Nikita的算法，因为它的运算速度非常快，在我的情况下这是绝对必要的。正如Daniel所指出的，它也可以很容易地并行化。唯一的缺点是，这并不是真正的标尺方式。

目前，凯文(Kevin)的算法总体上可能有点过于复杂，因此速度很慢，但是我敢肯定还有更多的优化可能(请参见他的回答中的最新评论)。

为了将Nikita的算法直接转换为功能样式，Daniel提出了一个已经非常快的解决方案，并且他说如果可以使用scanRight甚至会更快(请参阅答案中的最后评论)。

接下来做什么？

在技​​术方面:WAITINGScala 2.9，ScalaCL并进行综合基准测试以获取原始速度。

我所有这些的目标是拥有功能代码，但是只有在不牺牲太多速度的情况下才可以。

选择答案:

至于选择答案，我想将Nikita和Daniel的算法标记为答案，但我必须选择一个。我的问题的标题包括“最有效”，一个是命令式命令中最快的，另一个是功能样式。尽管这个问题被标记为Scala，但我还是选择Nikita的命令式算法，因为2s vs. 240s对于我来说仍然相差太大。我敢肯定，两者之间的差异还是可以缩小的，有什么想法吗？

因此，非常感谢大家!尽管我不会使用函数算法，但是我对Scala有了很多新的见解，并且我认为我慢慢地了解了所有的函数疯狂及其潜力。 (当然，即使不做太多函数式编程，Scala也比Java更令人愉悦……这是学习它的另一个原因)

Answer 1

您可以使用O(n^2)相对容易地做到这一点。
首先，一些预先计算。对于矩阵中的每个单元格，计算其下面有多少个连续的单元格具有相同的数目。
对于您的示例，结果矩阵a(无法想到更好的名称:/)将如下所示

0 0 0 0 0 2 2
1 1 2 2 2 1 1
0 0 1 1 1 0 0
1 1 0 0 0 1 1
0 0 0 0 0 0 0

可以用O(n^2)轻松生成。

现在，对于每行i，让我们找到所有在i行中具有上侧(在i + height - 1行中具有下侧)的矩形。
这是i = 1的插图

0 0 0 0 0 0 0
-------------
4 4 2 2 2 0 0
4 4 2 2 2 0 0
0 0 2 2 2 1 1
-------------
0 0 0 0 0 1 1

现在，主要思想

int current_width = 0;
for (int j = 0; j < matrix.width; ++j) {
    if (a[i][j] < height - 1) {
        // this column has different numbers in it, no game
        current_width = 0;
        continue;
    }

    if (current_width > 0) {
        // this column should consist of the same numbers as the one before
        if (matrix[i][j] != matrix[i][j - 1]) {
            current_width = 1; // start streak anew, from the current column
            continue;
        }
    }

    ++current_width;
    if (current_width >= width) {
        // we've found a rectangle!
    }
}

在上面的示例(i = 1)中，每次迭代后的current_width将是0, 0, 1, 2, 3, 0, 0。

现在，我们需要遍历所有可能的i，并且有一个解决方案。