我的问题很简单，但我还没有找到高效的实现方法。
假设有一个像这样的矩阵A：
现在我想找到这个矩阵中所有给定大小的矩形区域的起始位置。一个区域是A的子集，其中所有数字都相同。
假设宽度为2，高度为3。有3个具有此大小的区域：
该函数调用的结果将是一个起始位置列表（x、y从0开始）的列表，表示那些区域。
以下是我的当前实现。这里称为“区域”的是“表面”。
我已经尝试过对其进行一些优化，但我相信还有更好的解决方案。是否存在matlab函数可供移植？我也想知道这个问题是否有自己的名称，因为我不确定该搜索什么。
谢谢你考虑这个问题！期待看到您的提议或解决方案 :)
编辑：我的应用程序中矩阵的维度大约在300x300到3000x3000之间。此外，该算法将仅针对同一矩阵调用一次。原因是矩阵之后将始终更改（大约为其的1-20％）。
结果: 我实现了Kevin、Nikita和Daniel的算法，并在我的应用环境中对它们进行了基准测试，即没有孤立的合成基准测试，而是特别注意将所有算法集成到它们最有效的方式中，这对于Kevin的方法尤其重要，因为它使用泛型（请参见下文）。
首先是原始结果，使用Scala 2.8和jdk 1.6.0_23。作为解决特定应用程序问题的一部分，算法被执行了数百次。“Duration”表示需要的总时间，直到应用程序算法完成（当然不包括jvm启动等）。我的机器是一台2.8GHz Core 2 Duo，有2个核心和2gig内存，JVM分配了-Xmx800M。
重要提示：我认为我的基准测试设置对于像Daniel的并行化算法这样的算法并不公平。这是因为应用程序已经在计算多线程。因此，这里的结果可能仅显示等效于单线程速度。
矩阵大小233x587:
使用@specialized，避免类型擦除，使泛型更快。
矩阵大小为2000x3000：
首先，有关内存的一点说明。-server JVM选项在更多优化和更快执行的优势下使用了相当多的内存。正如您从第二个表中可以看出，尼基塔的算法使用-server选项较慢，这显然是由于达到内存限制所致。我认为，即使对于小矩阵，这也会减慢凯文的算法，因为函数式方法本质上使用了更多的内存。为了消除内存因素，我还用50x50矩阵试过一次，然后凯文的需要5秒钟，而尼基塔的只需0秒钟（嗯，几乎为0）。无论如何，它仍然比较缓慢，而不仅仅是因为内存。
假设有一个像这样的矩阵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的子集，其中所有数字都相同。
假设宽度为2，高度为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。作为解决特定应用程序问题的一部分，算法被执行了数百次。“Duration”表示需要的总时间，直到应用程序算法完成（当然不包括jvm启动等）。我的机器是一台2.8GHz Core 2 Duo，有2个核心和2gig内存，JVM分配了-Xmx800M。
重要提示：我认为我的基准测试设置对于像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，避免类型擦除，使泛型更快。
矩阵大小为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选项较慢，这显然是由于达到内存限制所致。我认为，即使对于小矩阵，这也会减慢凯文的算法，因为函数式方法本质上使用了更多的内存。为了消除内存因素，我还用50x50矩阵试过一次，然后凯文的需要5秒钟，而尼基塔的只需0秒钟（嗯，几乎为0）。无论如何，它仍然比较缓慢，而不仅仅是因为内存。
从数字上可以看出，显然我会使用尼基塔的算法，因为它非常快，而这在我的情况下绝对必要。正如丹尼尔指出的那样，它也很容易并行化。唯一的缺点是它不是真正的Scala方式。
目前，凯文的算法可能总体上有点过于复杂，因此速度比较慢，但我相信还有更多的优化可能性（请参见他答案中的最后评论）。
为了直接将尼基塔的算法转换为函数式风格，丹尼尔提出了一个解决方案，它已经相当快了，正如他在答案中所说，如果他可以使用scanRight，这个解决方案甚至会更快。
下一步是什么？
在技术方面：等待Scala 2.9，ScalaCL，并进行合成基准测试以获得原始速度。
我在所有这些中的目标是拥有功能性代码，但前提是不要牺牲太多速度。
答案选择：
至于选择答案，我想把尼基塔和丹尼尔的算法都标记为答案，但我必须选择一个。我的问题标题包括“最有效”，一个是命令式的最快，另一个是函数式风格的最快。尽管这个问题被标记为Scala，但我选择了尼基塔的命令式算法，因为2秒与240秒的差别对我来说仍然太大了。我相信差距仍然可以降低一点，您有什么想法吗？
非常非常感谢你们所有人！虽然我现在不会使用函数式算法，但我对Scala有了许多新的见解，我认为我慢慢地理解了所有的函数疯狂和它的潜力。（当然，即使没有做太多的函数式编程，Scala比Java更令人愉快……这就是学习它的另一个原因）
T=(Int, Int)。 - Kevin Wright