如何最有效地找到以矩阵给定大小的相同值的矩形区域？ [英] How to find same-value rectangular areas of a given size in a matrix most efficiently?
问题描述
我的问题很简单，但我还没有找到一个有效的实现呢。
My problem is very simple but I haven't found an efficient implementation yet.
假设有一个矩阵A是这样的：
Suppose there is a matrix A like this:
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的一个子集，其中所有的数字都是一样的。
Now I want to find all starting positions of rectangular areas in this matrix which have a given size. An area is a subset of A where all numbers are the same.
让我们说宽度= 2和高度= 3。有3个区域具有这种规模：
Let's say width=2 and height=3. There are 3 areas which have this size:
2 2 2 2 0 0
2 2 2 2 0 0
2 2 2 2 0 0
函数调用的结果将是起始位置的列表（X，Y从0开始）的那些区域。
The result of the function call would be a list of starting positions (x,y starting with 0) of those areas.
List((2,1),(3,1),(5,0))
以下是我目前的执行情况。 区域被称为表面在这里。
The following is my current implementation. "Areas" are called "surfaces" here.
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函数？我也想知道这个问题是否有自己的名字，因为我不知道要到谷歌的东西。
I already tried to include some optimizations in it but I am sure that there are far better solutions. Is there a matlab function existing for it which I could port? I'm also wondering whether this problem has its own name as I didn't exactly know what to google for.
感谢您考虑这个问题！我很高兴看到您的建议或解决方案：）
Thanks for thinking about it! I'm excited to see your proposals or solutions :)
编辑：在我的应用范围从300×300到3000x3000约矩阵的尺寸。此外，该算法将只被称为的一旦的为同一矩阵。其原因是，基质将始终事后改变（大约为1〜20％的话）。
Matrix dimensions in my application range from 300x300 to 3000x3000 approximately. Also, the algorithm will only be called once for the same matrix. The reason is that the matrix will always be changed afterwards (approx. 1-20% of it).
我实现了凯文，尼基塔和丹尼尔的算法和基准测试他们在我的应用环境中，即没有孤立的合成基准测试在这里，但需要特别小心对所有的算法集成到他们这对凯文的做法特别重要最高效的方式它使用泛型（见下文）。
I implemented the algorithms of Kevin, Nikita and Daniel and benchmarked them in my application environment, i.e. no isolated synthetic benchmark here, but special care was taken to integrate all algorithms in their most performant way which was especially important for Kevin's approach as it uses generics (see below).
第一，原始结果，使用Scala 2.8和JDK 1.6.0_23。该算法被执行几百倍作为解决应用程序特定的问题的一部分。 持续时间是指根据需要，直到应用程序结束算法（当然不JVM启动等）的总时间。我的机器是2.8GHz的酷睿2与2核心和内存2gig，-Xmx800M都给了JVM。
First, the raw results, using Scala 2.8 and jdk 1.6.0_23. The algorithms were executed several hundred times as part of solving an application-specific problem. "Duration" denotes the total time needed until the application algorithm finished (of course without jvm startup etc.). My machine is a 2.8GHz Core 2 Duo with 2 cores and 2gig of memory, -Xmx800M were given to the JVM.
重要提示：我觉得我的基准设置是不公平的并行算法，如从丹尼尔之一。这是因为应用程序已经计算多线程。所以这里的结果可能只显示一个相当于单线程速度。
IMPORTANT NOTE: I think my benchmark setup is not really fair for parallelized algorithms like the one from Daniel. This is because the application is already calculating multi-threaded. So the results here probably only show an equivalent to single-threaded speed.
矩阵大小233x587：
Matrix size 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：
Matrix size 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选项，这显然是因为碰到内存限制。我认为这也减缓了凯文的算法，即使是小的矩阵作为功能的方法是使用更多的内存反正。为了消除记忆的因素我也试了一次，用50×50的矩阵，然后凯文的了5secs和尼基塔的0secs（当然，几乎为0）。因此，在任何情况下，它仍然较慢，不只是因为内存。
First, a small note on memory. The -server JVM option uses considerably more memory at the advantage of more optimizations and in general faster execution. As you can see from the 2nd table Nikita's algorithm is slower with the -server option which is obviously due to hitting the memory limit. I assume that this also slows down Kevin's algorithm even for the small matrix as the functional approach is using much more memory anyways. To eliminate the memory factor I also tried it once with a 50x50 matrix and then Kevin's took 5secs and Nikita's 0secs (well, nearly 0). So in any case it's still slower and not just because of memory.
正如你从数字看，我显然会使用Nikita的算法，因为它是该死的快，这是绝对必要的，我的情况。它也可以容易地并行丹尼尔指出。唯一的缺点是，它是不是真正的斯卡拉路。
As you can see from the numbers, I will obviously use Nikita's algorithm because it's damn fast and this is absolutely necessary in my case. It can also be parallelized easily as Daniel pointed out. The only downside is that it's not really the scala-way.
目前，凯文的算法大概是一般有点过于复杂，因此缓慢的，但我敢肯定有更多的优化可能的（见他的回答最后的注释）。
At the moment Kevin's algorithm is probably in general a bit too complex and therefore slow, but I'm sure there are more optimizations possible (see last comments in his answer).
通过直接转化尼基塔的算法函数式的目标，丹尼尔想出了一个解决方案，这已经是相当快，因为他说，即使会更快，如果他可以利用scanRight（见他的回答最后评论）
With the goal of directly transforming Nikita's algorithm to functional style Daniel came up with a solution which is already quite fast and as he says would even be faster if he could use scanRight (see last comments in his answer).
下一步是什么？
在技术方面：等待斯卡拉2.9，ScalaCL，做综合测试得到的原始速度
At the technological side: waiting for Scala 2.9, ScalaCL, and doing synthetic benchmarks to get raw speeds.
我在这一切的目标是有功能code，但只有当它没有牺牲太多的速度。
My goal in all this is to have functional code, BUT only if it's not sacrificing too much speed.
答案选择：
至于选择一个答案，我想，以纪念尼基塔的和丹尼尔的算法为答案，但我必须选择一个。我的问题的标题包括最有效，一个是最快的当务之急和其他功能性的风格。虽然这个问题被标记斯卡拉我选择了尼基塔的当务之急算法为2s与240S仍相差太多，我接受。我敢肯定的差异仍然可以推了一点，任何想法？
As for choosing an answer, I would want to mark Nikita's and Daniel's algorithms as answers but I have to choose one. The title of my question included "most efficiently", and one is the fastest in imperative and the other in functional style. Although this question is tagged Scala I chose Nikita's imperative algorithm as 2s vs. 240s is still too much difference for me to accept. I'm sure the difference can still be pushed down a bit, any ideas?
那么，谢谢大家非常非常感谢！虽然我不会用的功能算法的但的，我得到了许多新的见解Scala和我想我慢慢的得到的所有功能crazyness和潜力的理解。 （当然，即使没有做太多的函数式编程，Scala是更讨人喜欢比Java ...这是另一个原因，以了解它）
So, thank you all very very much! Although I won't use the functional algorithms yet, I got many new insights into Scala and I think I slowly get an understanding of all the functional crazyness and its potential. (of course, even without doing much functional programming, Scala is much more pleasing than Java... that's another reason to learn it)
推荐答案
您可以做到这一点在为O（n ^ 2）相对容易。
首先，some- precalculations。对于在基质每个单元，计算许多连续的细胞下面它如何具有相同的数目。
对于你的榜样，结果矩阵 A （也想不出更好的名字：/）看起来像这样
You can do it in O(n^2) relatively easy.
First, some-precalculations. For each cell in matrix, calculate how many consecutive cells below it have the same number.
For your example, resulting matrix a (couldn't think of better name :/) will look like this
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）容易。
现在，对于每一行我，让我们找到顶部所有的矩形行我（和底部行 1 +高度 - 1 ）
下面是一个例子 I = 1
Now, for each row i, let's find all rectangles with top side in row i (and bottom side in row i + height - 1).
Here's an illustration for 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 。
In the example above (i = 1) current_width after each iteration will be 0, 0, 1, 2, 3, 0, 0.
现在，我们需要遍历所有可能的我，我们有一个解决方案。
Now, we need to iterate over all possible i and we have a solution.
这篇关于如何最有效地找到以矩阵给定大小的相同值的矩形区域？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
