根据编辑，主要意图是找到第一个非零条目。这很有道理。一旦找到了这个，你可以轻松地使用梯度上升法来找到最大值: 只需从当前条目走向每一步中具有最高值的邻居，直到到达顶部。
然而，一些可能重要的细节缺失了。例如，知道波的形状可能很重要。在原始问题中，它似乎具有一定的高斯形式。它也可能更加“平坦”吗? 也就是说，同样的最大值是否会导致填充了更大的矩阵区域与非零条目?
关键点在于-对于第一个简单的优化-要知道包含非零条目的区域的直径。如果你知道带有非零条目的区域的直径是，例如，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();
}
}
