根据编辑,主要意图是找到第一个非零条目。这很有道理。一旦找到了这个,你可以轻松地使用梯度上升法来找到最大值: 只需从当前条目走向每一步中具有最高值的邻居,直到到达顶部。
然而,一些可能重要的细节缺失了。例如,知道波的形状可能很重要。在原始问题中,它似乎具有一定的高斯形式。它也可能更加“平坦”吗? 也就是说,同样的最大值是否会导致填充了更大的矩阵区域与非零条目?
关键点在于-对于第一个简单的优化-要知道包含非零条目的区域的直径。如果你知道带有非零条目的区域的直径是,例如,n,则你可以以步长为n-1遍历矩阵,并确信你不会错过波。
如果关于波可能位置的信息完全没有,那么我怀疑改进的空间将会非常有限。如果它可以出现在任何地方,那么你就必须到处搜索。
但是,即使是对于微不足道的搜索(无论步长是1还是n-1
),也可能会有影响整体性能的决策,其中最突出的是缓存效应。以下是一个示例,它将“波”放入各种大小的矩阵中。(请注意,“波”实际上是基于具有最大值条目的摩尔邻域的矩形,为简单起见)。
它使用三种方法查找第一个非零条目:
findNonZeroSimpleA
:按列依次遍历矩阵
findNonZeroSimpleB
:按行依次遍历矩阵
findNonZeroSkipping
:按列依次遍历矩阵,步长为n-1
这不是“基准测试”
它只能大致表明性能差异。以下是我的PC的一些结果(不透露设置情况,因为这不是基准测试):对于一个8000x8000矩阵,最大值为10,在(6000,6000)处,三种方法的运行时间如下:
- findNonZeroSimpleA: 28.783毫秒
- findNonZeroSimpleB: 831.323毫秒
- findNonZeroSkipping: 2.203毫秒
可以看出,最大的差异由遍历顺序暗示(只需交换两行 - 确保在此使用正确的行!)。“跳过”方法将运行时间大致减少了与波浪大小相对应的因子。(结果也可能被扭曲,这取决于缓存效应,当波浪大小较大时 - 但幸运的是,这些恰好是跳过方法尤其有益的情况)。
import java.awt.Point;
public class WaveMatrixTest
{
public static void main(String[] args)
{
speedTest();
}
private static void basicTest()
{
int size = 30;
int maxValue = 10;
int array[][] = new int[size][size];
placeValue(array, maxValue, 15, 15);
System.out.println(toString2D(array));
}
private static void speedTest()
{
int maxValue = 10;
int runs = 10;
for (int size=2000; size<=8000; size*=2)
{
for (int run=0; run<runs; run++)
{
int x = size/2+size/4;
int y = size/2+size/4;
runTestSimpleA(size, maxValue, x, y);
runTestSimpleB(size, maxValue, x, y);
runTestSkipping(size, maxValue, x, y);
}
}
}
private static void runTestSimpleA(int size, int maxValue, int x, int y)
{
int array[][] = new int[size][size];
placeValue(array, maxValue, x, y);
long before = System.nanoTime();
Point p = findNonZeroSimpleA(array, maxValue);
long after = System.nanoTime();
System.out.printf("SimpleA, size %5d max at %5d,%5d took %.3f ms, result %s\n",
size, x, y, (after-before)/1e6, p);
}
private static void runTestSimpleB(int size, int maxValue, int x, int y)
{
int array[][] = new int[size][size];
placeValue(array, maxValue, x, y);
long before = System.nanoTime();
Point p = findNonZeroSimpleB(array, maxValue);
long after = System.nanoTime();
System.out.printf("SimpleB, size %5d max at %5d,%5d took %.3f ms, result %s\n",
size, x, y, (after-before)/1e6, p);
}
private static void runTestSkipping(int size, int maxValue, int x, int y)
{
int array[][] = new int[size][size];
placeValue(array, maxValue, x, y);
long before = System.nanoTime();
Point p = findNonZeroSkipping(array, maxValue);
long after = System.nanoTime();
System.out.printf("Skipping, size %5d max at %5d,%5d took %.3f ms, result %s\n",
size, x, y, (after-before)/1e6, p);
}
private static void placeValue(int array[][], int maxValue, int x, int y)
{
int sizeX = array.length;
int sizeY = array[0].length;
int n = maxValue;
for (int dx=-n; dx<=n; dx++)
{
for (int dy=-n; dy<=n; dy++)
{
int cx = x+dx;
int cy = y+dy;
if (cx >= 0 && cx < sizeX &&
cy >= 0 && cy < sizeY)
{
int v = maxValue - Math.max(Math.abs(dx), Math.abs(dy));
array[cx][cy] = v;
}
}
}
}
private static Point findNonZeroSimpleA(int array[][], int maxValue)
{
int sizeX = array.length;
int sizeY = array[0].length;
for (int x=0; x<sizeX; x++)
{
for (int y=0; y<sizeY; y++)
{
if (array[x][y] != 0)
{
return new Point(x,y);
}
}
}
return null;
}
private static Point findNonZeroSimpleB(int array[][], int maxValue)
{
int sizeX = array.length;
int sizeY = array[0].length;
for (int y=0; y<sizeY; y++)
{
for (int x=0; x<sizeX; x++)
{
if (array[x][y] != 0)
{
return new Point(x,y);
}
}
}
return null;
}
private static Point findNonZeroSkipping(int array[][], int maxValue)
{
int size = maxValue * 2 - 1;
int sizeX = array.length;
int sizeY = array[0].length;
for (int x=0; x<sizeX; x+=size)
{
for (int y=0; y<sizeY; y+=size)
{
if (array[x][y] != 0)
{
return new Point(x,y);
}
}
}
return null;
}
private static String toString2D(int array[][])
{
StringBuilder sb = new StringBuilder();
int sizeX = array.length;
int sizeY = array[0].length;
for (int x=0; x<sizeX; x++)
{
for (int y=0; y<sizeY; y++)
{
sb.append(String.format("%3d", array[x][y]));
}
sb.append("\n");
}
return sb.toString();
}
}